टॉरॉयडल ग्राफ
ग्राफ सिद्धांत के गणितीय क्षेत्र में, एक टोरॉयडल ग्राफ एक ग्राफ (असतत गणित) है जो एक टोरस पर ग्राफ एम्बेडिंग हो सकता है। दूसरे शब्दों में, ग्राफ के शीर्ष (ग्राफ सिद्धांत) को एक टोरस पर रखा जा सकता है जैसे कि कोई किनारा पार नहीं करता।
उदाहरण
कोई भी ग्राफ़ जिसे एक समतल में एम्बेड किया जा सकता है, एक टोरस में भी एम्बेड किया जा सकता है। जीनस (गणित) 1 का एक टॉरॉयडल ग्राफ एक टोरस में एम्बेड किया जा सकता है लेकिन एक विमान में नहीं। हीवुड ग्राफ, पूरा ग्राफ के7 (और इसलिए के5 और के6), पीटरसन ग्राफ (और इसलिए पूर्ण द्विदलीय ग्राफ K3,3, चूंकि पीटरसन ग्राफ में इसका एक उपखंड शामिल है), ब्लानुसा स्नार्क्स में से एक,[1] और सभी मोबियस लैडर टॉरॉयडल हैं। अधिक आम तौर पर, पार संख्या (ग्राफ सिद्धांत) 1 वाला कोई भी ग्राफ टॉरॉयडल होता है। अधिक क्रॉसिंग नंबर वाले कुछ ग्राफ़ भी टोरॉयडल हैं: मोबियस-कैंटर ग्राफ़, उदाहरण के लिए, क्रॉसिंग नंबर 4 है और टोरॉयडल है।[2]
गुण
किसी भी टोरॉयडल ग्राफ में अधिक से अधिक 7 रंगीन संख्या होती है।[3] पूरा ग्राफ K7 रंगीन संख्या 7 के साथ टोरॉयडल ग्राफ का एक उदाहरण प्रदान करता है।[4]
किसी भी त्रिभुज-मुक्त ग्राफ़|त्रिकोण-मुक्त टॉरॉयडल ग्राफ़ में अधिकतम 4 वर्णिक संख्या होती है।[5]
फेरी के प्रमेय के अनुरूप परिणाम से, किसी भी टोरॉयडल ग्राफ को आवधिक सीमा शर्तों के साथ एक आयत में सीधे किनारों के साथ ग्राफ ड्राइंग हो सकता है।[6] इसके अलावा, टुट्टे के वसंत प्रमेय का एनालॉग इस मामले में लागू होता है।[7] टॉरॉयडल ग्राफ़ में अधिकतम 7 पृष्ठों के साथ पुस्तक एम्बेडिंग भी होती है।[8]
रुकावटें
रॉबर्टसन-सीमोर प्रमेय के अनुसार, न्यूनतम गैर-टोरॉयडल ग्राफ का एक परिमित सेट एच मौजूद है, जैसे कि एक ग्राफ टॉरॉयडल है अगर और केवल अगर एच में कोई ग्राफ माइनर नहीं है। यही है, एच टोरॉयडल ग्राफ के लिए वर्जित ग्राफ लक्षण वर्णन का सेट बनाता है। पूरा सेट एच ज्ञात नहीं है, लेकिन इसमें कम से कम 17,523 ग्राफ हैं। वैकल्पिक रूप से, कम से कम 250,815 गैर-टोरॉयडल ग्राफ़ हैं जो टोपोलॉजिकल माइनर ऑर्डरिंग में न्यूनतम हैं। एक ग्राफ़ टोरॉयडल है अगर और केवल अगर इसमें इन ग्राफ़ों में से कोई भी टोपोलॉजिकल माइनर के रूप में नहीं है।[9]
गैलरी
- Cayley graphs of the quaternion group.png
चतुष्कोणीय समूह के दो आइसोमोर्फिक केली ग्राफ।
- Cayley graph of quaternion group on torus.png
टॉरस में एम्बेडेड चतुर्धातुक समूह का केली ग्राफ।
- Quaternion group.webm
टोरस में एम्बेड किए गए चतुर्धातुक समूह के केली ग्राफ का वीडियो।
टोरस में एम्बेड किया गया हीवुड ग्राफ और संबंधित नक्शा।
- Pappus-graph-on-torus.png
टोरस में सन्निहित पप्पू ग्राफ और संबद्ध मानचित्र।
यह भी देखें
- प्लेनर ग्राफ
- सामयिक ग्राफ सिद्धांत
- सम्राट पॉलीहेड्रॉन
टिप्पणियाँ
संदर्भ
- Chartrand, Gary; Zhang, Ping (2008), Chromatic graph theory, CRC Press, ISBN 978-1-58488-800-0.
- Endo, Toshiki (1997), "The pagenumber of toroidal graphs is at most seven", Discrete Mathematics, 175 (1–3): 87–96, doi:10.1016/S0012-365X(96)00144-6, MR 1475841.
- Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization" (PDF), Computer Aided Geometric Design, 23 (2): 83–112, doi:10.1016/j.cagd.2005.05.002, MR 2189438, S2CID 135438.
- Heawood, P. J. (1890), "Map colouring theorems", Quarterly Journal of Mathematics, First Series, 24: 322–339.
- Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF), Ars Combinatoria, 59: 259–277, MR 1832459, archived from the original (PDF) on 2004-12-24, retrieved 2018-09-06.
- Kronk, Hudson V.; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", Proceedings of the American Mathematical Society, American Mathematical Society, 34 (1): 83–86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
- Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca, 50: 117–121, CiteSeerX 10.1.1.28.7183, hdl:10338.dmlcz/133137, MR 1763113, Zbl 0984.05044.
- Myrvold, Wendy; Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics, 25 (1): P1.16, doi:10.37236/3797
- Neufeld, Eugene; Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–580, ISBN 978-0-89871-390-9.
- Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte (2004), "Blanuša double" (PDF), Math. Commun., 9 (1): 91–103, CiteSeerX 10.1.1.361.2772.
