मोजर धुरी
| Moser spindle | |
|---|---|
 | |
| Named after | Leo Moser, William Moser |
| Vertices | 7 |
| Edges | 11 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 3 |
| Automorphisms | 8 |
| Chromatic number | 4 |
| Chromatic index | 4 |
| Properties | planar unit distance Laman graph |
| Table of graphs and parameters | |
ग्राफ सिद्धांत में, गणित की एक शाखा, मोजर स्पिंडल (जिसे मोजर्स स्पिंडल या मोजर ग्राफ भी कहा जाता है) एक अप्रत्यक्ष ग्राफ है, जिसका नाम गणितज्ञ लियो मोजर और उनके भाई विलियम के नाम पर रखा गया है।[1] सात शीर्षों और ग्यारह किनारों वाला। यह एक इकाई दूरी ग्राफ है जिसमें किसी भी ग्राफ़ रंग में चार रंगों की आवश्यकता होती है, और इसके अस्तित्व का उपयोग यह साबित करने के लिए किया जा सकता है कि हैडविगर-नेल्सन समस्या कम से कम चार है।[2] ग्योर्गी हाजोस के बाद मोजर स्पिंडल को हाजोस ग्राफ भी कहा गया है, क्योंकि इसे हाजोस निर्माण के एक उदाहरण के रूप में देखा जा सकता है।[3] हालाँकि, हाजोस ग्राफ़ नाम को एक षट्भुज के भीतर अंकित त्रिकोण के रूप में, एक अलग ग्राफ़ पर भी लागू किया गया है।[4]
निर्माण
एक इकाई दूरी ग्राफ के रूप में, मोजर स्पिंडल 60 और 120 डिग्री कोण वाले दो समचतुर्भुजों द्वारा निर्मित होता है, जिससे कि समचतुर्भुज की भुजाएँ और छोटे विकर्ण समबाहु त्रिभुज बनाते हैं। दोनों रम्बियों को उनके एक न्यून कोण वाले शीर्ष को साझा करते हुए समतल में इस प्रकार रखा गया है कि शेष दो न्यून कोण वाले शीर्ष एक दूसरे से एक इकाई की दूरी पर हैं। ग्राफ़ के ग्यारह किनारे आठ समचतुर्भुज भुजाएँ, समचतुर्भुज के दो छोटे विकर्ण और तीव्र-कोण शीर्षों की इकाई-दूरी जोड़ी के बीच का किनारा हैं।
मोजर स्पिंडल का निर्माण ज्यामितीय एम्बेडिंग के संदर्भ के बिना, चार शीर्षों पर दो पूर्ण ग्राफ़ के साथ शुरू होने वाले हाजोस निर्माण का उपयोग करके ग्राफ-सैद्धांतिक रूप से भी किया जा सकता है। यह निर्माण प्रत्येक पूर्ण ग्राफ़ से एक किनारे को हटा देता है, हटाए गए किनारों के दो अंतिम बिंदुओं को दोनों गुटों द्वारा साझा किए गए एक एकल शीर्ष में विलय कर देता है, और हटाए गए किनारे के शेष दो समापन बिंदुओं को जोड़ते हुए एक नया किनारा जोड़ता है।[5]
मोजर स्पिंडल के निर्माण का दूसरा तरीका उपयोगिता ग्राफ K से बने ग्राफ का पूरक ग्राफ है3,3 इसके एक किनारे को उपविभाजित करके।[6]
हैडविगर-नेल्सन समस्या का अनुप्रयोग
हैडविगर-नेल्सन समस्या पूछती है कि यूक्लिडियन विमान के बिंदुओं को इस तरह से रंगने के लिए कितने रंगों की आवश्यकता है कि एक दूसरे से इकाई दूरी पर बिंदुओं के प्रत्येक जोड़े को अलग-अलग रंग दिए जाएं। अर्थात्, यह अनंत ग्राफ़ की वर्णिक संख्या मांगता है जिसके शीर्ष तल के सभी बिंदु हैं और जिसके किनारे इकाई दूरी पर बिंदुओं के सभी जोड़े हैं।[2]
मोजर स्पिंडल को किसी भी ग्राफ़ को रंगने में चार रंगों की आवश्यकता होती है: दो रम्बियों में से किसी एक के तीन-रंग में, जिससे यह बना है, रम्बी के दो तीव्र-कोण वाले शीर्षों में आवश्यक रूप से एक दूसरे के समान रंग होगा। लेकिन यदि दो रोम्बियों के साझा शीर्ष का रंग दो विपरीत तीव्र-कोण वाले शीर्षों के समान है, तो इन दोनों शीर्षों का रंग एक-दूसरे के समान है, जो इस आवश्यकता का उल्लंघन करता है कि उन्हें जोड़ने वाले किनारे पर अलग-अलग रंग के समापन बिंदु हैं। यह विरोधाभास दर्शाता है कि तीन रंग असंभव हैं, इसलिए कम से कम चार रंग आवश्यक हैं। मोजर स्पिंडल को रंगने के लिए चार रंग भी पर्याप्त हैं, उदाहरण के लिए एक तथ्य यह है कि इसकी विकृति (ग्राफ सिद्धांत) तीन है।
एक वैकल्पिक प्रमाण कि मोजर स्पिंडल को चार रंगों की आवश्यकता होती है, हाजोस निर्माण से मिलता है। दोनों पूर्ण ग्राफ़ जिनसे मोजर स्पिंडल बनता है, के लिए चार रंगों की आवश्यकता होती है, और हाजोस निर्माण इस संपत्ति को संरक्षित करता है।[5] इससे भी अधिक सीधे तौर पर, मोजर स्पिंडल में प्रत्येक स्वतंत्र सेट (ग्राफ़ सिद्धांत) में अधिकतम दो शीर्ष होते हैं,[7]इसलिए सभी सात शीर्षों को कवर करने के लिए कम से कम चार स्वतंत्र सेट लगते हैं।
चूंकि मोजर स्पिंडल विमान के अनंत इकाई दूरी ग्राफ का एक उपग्राफ है, इसलिए विमान के ग्राफ को किसी भी रंग में कम से कम चार रंगों की आवश्यकता होती है। डी ब्रुजन-एर्डोस प्रमेय (ग्राफ सिद्धांत) द्वारा | डी ब्रुजन-एर्डोस प्रमेय (इस धारणा के साथ कि पसंद का स्वयंसिद्ध सत्य है), विमान की रंगीन संख्या इसके किसी भी परिमित उपग्राफ की सबसे बड़ी रंगीन संख्या के समान है ; 2018 में 5-क्रोमैटिक इकाई दूरी ग्राफ़ के परिवार की खोज तक, अनंत इकाई दूरी ग्राफ़ का कोई उपग्राफ़ नहीं पाया गया था जिसके लिए मोजर स्पिंडल की तुलना में बड़ी संख्या में रंगों की आवश्यकता होती है। हालाँकि, विमान की रंगीन संख्या के लिए सबसे अच्छी ऊपरी सीमा सात है, जो मोजर स्पिंडल के लिए आवश्यक रंगों की संख्या से काफी अधिक है।[2]
अन्य गुण और अनुप्रयोग
मोजर स्पिंडल एक समतलीय ग्राफ है, जिसका अर्थ है कि इसे समतल में क्रॉसिंग के बिना खींचा जा सकता है। हालाँकि, सीधी रेखा के किनारों के साथ ऐसा चित्र बनाना संभव नहीं है जो एक इकाई दूरी का चित्र भी हो; अर्थात्, यह माचिस की तीली का ग्राफ नहीं है। मोजर स्पिंडल भी एक लमान ग्राफ है, जिसका अर्थ है कि यह विमान में एम्बेडेड होने पर न्यूनतम कठोर प्रणाली बनाता है।[8]एक समतल लैमन ग्राफ के रूप में, यह एक नुकीले छद्मत्रिकोण का ग्राफ है, जिसका अर्थ है कि इसे विमान में इस तरह से एम्बेड किया जा सकता है कि असीमित चेहरा एम्बेडिंग का उत्तल पतवार है और प्रत्येक घिरा हुआ चेहरा केवल तीन उत्तल के साथ एक छद्मत्रिकोण है शिखर.[9] मोजर ग्राफ का पूरक ग्राफ एक त्रिकोण-मुक्त ग्राफ है। इस प्रकार, मोजर ग्राफ की इकाई दूरी एम्बेडिंग का उपयोग विमान में सात बिंदुओं को इस तरह से रखने की समस्या को हल करने के लिए किया जा सकता है कि प्रत्येक त्रिक बिंदु में एक दूसरे से इकाई दूरी पर कम से कम एक जोड़ी हो।[2][10] मोजर स्पिंडल में किसी भी किनारे को जोड़ने पर एक ग्राफ बनता है जिसे एक इकाई दूरी ग्राफ के रूप में विमान में एम्बेड नहीं किया जा सकता है, और मोजर स्पिंडल से किसी भी छोटी इकाई दूरी ग्राफ में कोई ग्राफ समरूपता मौजूद नहीं है। मोजर स्पिंडल के इन दो गुणों का उपयोग किया गया था Horvat, Kratochvíl & Pisanski (2011) परीक्षण की एनपी-पूर्ण|एनपी-कठोरता दिखाने के लिए कि क्या किसी दिए गए ग्राफ़ में द्वि-आयामी इकाई दूरी प्रतिनिधित्व है; प्रमाण 3SAT से एक कटौती का उपयोग करता है जिसमें मोजर स्पिंडल का उपयोग कटौती में केंद्रीय सत्य-सेटिंग गैजेट (कंप्यूटर विज्ञान) के रूप में किया जाता है।[8] मोजर स्पिंडल का उपयोग यूक्लिडियन रैमसे सिद्धांत में परिणाम साबित करने के लिए भी किया जा सकता है: यदि टी विमान में कोई त्रिकोण है, और विमान के बिंदु दो रंग के काले और सफेद हैं, तो या तो टी का काला अनुवाद है या ए एक दूसरे से इकाई दूरी पर सफेद बिंदुओं की जोड़ी। मान लीजिए कि M, मोजर स्पिंडल की एक इकाई-दूरी एम्बेडिंग है, और M+T, M और T का मिन्कोव्स्की योग है। यदि M+T में कोई सफेद इकाई-दूरी जोड़ी नहीं है, तो मोजर की तीन प्रतियों में से प्रत्येक एम+टी में स्पिंडल में अधिकतम दो सफेद बिंदु होने चाहिए, क्योंकि प्रत्येक प्रतिलिपि में सफेद बिंदुओं को एक स्वतंत्र सेट (ग्राफ सिद्धांत) बनाना चाहिए और मोजर स्पिंडल में सबसे बड़े स्वतंत्र सेट का आकार दो है। इसलिए, मोजर स्पिंडल के सात शीर्षों में से, अधिकतम छह ऐसे हैं जिनकी एम + टी में एक सफेद प्रतिलिपि है, इसलिए उन सात शीर्षों में से एक होना चाहिए जिनकी सभी प्रतियां काली हैं। लेकिन फिर इस शीर्ष की तीन प्रतियाँ T का अनुवाद बनाती हैं।[7]
यह भी देखें
संदर्भ
- ↑ Moser, L.; Moser, W. (1961), "Solution to problem 10", Can. Math. Bull., 4: 187–189, doi:10.1017/S0008439500025753, S2CID 246244722.
- ↑ 2.0 2.1 2.2 2.3 Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, pp. 14–15, ISBN 978-0-387-74640-1.
- ↑ Bondy, J. A.; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 358, doi:10.1007/978-1-84628-970-5, ISBN 978-1-84628-969-9.
- ↑ Berge, C. (1989), "Minimax relations for the partial q-colorings of a graph", Discrete Mathematics, 74 (1–2): 3–14, doi:10.1016/0012-365X(89)90193-3, MR 0989117.
- ↑ 5.0 5.1 Hajós, G. (1961), "Über eine Konstruktion nicht n-färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117.
- ↑ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics, 308 (10): 1973–1984, doi:10.1016/j.disc.2007.04.050, MR 2394465.
- ↑ 7.0 7.1 Burkert, Jeffrey; Johnson, Peter (2011), "Szlam's lemma: mutant offspring of a Euclidean Ramsey problem from 1973, with numerous applications", Ramsey theory, Progr. Math., vol. 285, Birkhäuser/Springer, New York, pp. 97–113, doi:10.1007/978-0-8176-8092-3_6, MR 2759046. See also Soifer (2008), Problem 40.26, p. 496.
- ↑ 8.0 8.1 Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011), "On the Computational Complexity of Degenerate Unit Distance Representations of Graphs", Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6460, pp. 274–285, arXiv:1001.0886, Bibcode:2011LNCS.6460..274H, doi:10.1007/978-3-642-19222-7_28, ISBN 978-3-642-19221-0, S2CID 17585590.
- ↑ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802.
- ↑ Winkler, Peter (November 2011), "Puzzled: Distances Between Points on the Plane", Communications of the ACM, 54 (11): 120, doi:10.1145/2018396.2018422, S2CID 195633418. Solution, issue 12, December 2011, doi:10.1145/2043174.2043200.