टॉरॉयडल ग्राफ: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Graph able to be embedded on a torus}} thumb|एक [[ टोरस्र्स पर सन्निहित 14 श...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Graph able to be embedded on a torus}} | {{Short description|Graph able to be embedded on a torus}} | ||
[[File:Toroidal graph sample.gif|thumb|एक [[ टोरस्र्स ]] पर सन्निहित 14 शीर्षों वाला एक घनीय | [[File:Toroidal graph sample.gif|thumb|एक [[ टोरस्र्स |टोरस्र्स]] पर सन्निहित 14 शीर्षों वाला एक घनीय लेखाचित्र]] | ||
[[File:Heawood graph and map on torus.png|thumb| | [[File:Heawood graph and map on torus.png|thumb|स्थूलक में सन्निहित किया गया [[हीवुड ग्राफ|हीवुड लेखाचित्र]] और संबंधित मानचित्र।]][[ग्राफ सिद्धांत|आलेख सिद्धांत]] के [[गणितीय]] क्षेत्र में, टोरॉयडल लेखाचित्र एक [[ग्राफ (असतत गणित)|लेखाचित्र (असतत गणित)]] है जो स्थूलक पर [[ग्राफ एम्बेडिंग|लेखाचित्र सन्निहित]] हो सकता है। दूसरे शब्दों में, लेखाचित्र के [[ शीर्ष (ग्राफ सिद्धांत) |शीर्ष (आलेख सिद्धांत)]] को एक स्थूलक पर रखा जा सकता है कि कोई किनारा पार न हो। | ||
== उदाहरण == | == उदाहरण == | ||
कोई भी | कोई भी लेखाचित्र जिसे एक समतल में सन्निहित किया जा सकता है, एक स्थूलक में भी सन्निहित किया जा सकता है। [[जीनस (गणित)|श्रेणी (गणित)]] 1 का टॉरॉयडल लेखाचित्र एक स्थूलक में सन्निहित है लेकिन एक समतल में नहीं किया जा सकता। हीवुड लेखाचित्र, [[पूरा ग्राफ|पुर्ण लेखाचित्र]] K<sub>7</sub> (और इसलिए K<sub>5</sub> और K<sub>6</sub>), [[पीटरसन ग्राफ|पीटरसन लेखाचित्र]] (और इसलिए [[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय लेखाचित्र]] K<sub>3,3</sub>, चूंकि पीटरसन लेखाचित्र में इसका एक उपखंड सम्मिलित है), ब्लानुसा स्नार्क्स में से एक,{{sfnp|Orbanić|Pisanski|Randić|Servatius|2004}} और सभी मोबियस सोपान टॉरॉयडल हैं। अधिक सामान्यतः,[[ पार संख्या (ग्राफ सिद्धांत) |पारगमन संख्या (आलेख सिद्धांत)]] 1 वाला कोई भी लेखाचित्र टॉरॉयडल होता है। अधिक पारगमन अंक वाले कुछ लेखाचित्र भी टोरॉयडल हैं: मोबियस-कैंटर लेखाचित्र, उदाहरण के लिए, पारगमन अंक 4 और टोरॉयडल है।{{sfnp|Marušič|Pisanski|2000}} | ||
== गुण == | == गुण == | ||
किसी भी टोरॉयडल | किसी भी टोरॉयडल लेखाचित्र में अधिक से अधिक 7 [[रंगीन संख्या]] होती है।{{sfnp|Heawood|1890}} पूरा लेखाचित्र K<sub>7</sub> रंगीन संख्या 7 के साथ टोरॉयडल लेखाचित्र का एक उदाहरण प्रदान करता है।{{sfnp|Chartrand|Zhang|2008}} | ||
किसी भी | किसी भी त्रिकोण-मुक्त टॉरॉयडल लेखाचित्र में अधिकतम 4 वर्णिक संख्या होती है।{{sfnp|Kronk|White|1972}} | ||
फेरी के प्रमेय के अनुरूप परिणाम से, किसी भी टोरॉयडल | फेरी के प्रमेय के अनुरूप परिणाम से, किसी भी टोरॉयडल लेखाचित्र को आवधिक सीमा परिस्थिति के साथ एक आयत में सीधे किनारों के साथ [[ग्राफ ड्राइंग|लेखाचित्र आरेखण]] हो सकता है।{{sfnp|Kocay|Neilson|Szypowski|2001}} इसके अलावा, टुट्टे के वसंत प्रमेय का समधर्मी इस स्तिथि में लागू होता है।{{sfnp|Gortler|Gotsman|Thurston|2006}} | ||
टॉरॉयडल | |||
टॉरॉयडल लेखाचित्र में अधिकतम 7 पृष्ठों के साथ [[पुस्तक एम्बेडिंग|पुस्तक अंत: स्थापन]] भी होती है।{{sfnp|Endo|1997}} | |||
== रुकावटें == | == रुकावटें == | ||
रॉबर्टसन-सीमोर प्रमेय के अनुसार, न्यूनतम गैर-टोरॉयडल | रॉबर्टसन-सीमोर प्रमेय के अनुसार, न्यूनतम गैर-टोरॉयडल लेखाचित्र का एक परिमित सम्मुच्चय H उपस्थित है, जैसे कि एक लेखाचित्र टॉरॉयडल है यदि और केवल यदि H में कोई [[ग्राफ माइनर|लेखाचित्र लघु]] नहीं है। अर्थात्, H टोरॉयडल लेखाचित्र के लिए वर्जित लेखाचित्र लक्षण वर्णन का सम्मुच्चय बनाता है। पूरा सम्मुच्चय H ज्ञात नहीं है, लेकिन इसमें कम से कम 17,523 लेखाचित्र हैं। वैकल्पिक रूप से, कम से कम 250,815 गैर-टोरॉयडल लेखाचित्र हैं जो [[टोपोलॉजिकल माइनर|सांस्थितिक अल्प]] क्रमण में न्यूनतम हैं। एक लेखाचित्र टोरॉयडल है यदि और केवल यदि इसमें इन लेखाचित्र में से कोई भी सांस्थितिक अल्प के रूप में नहीं है।{{sfnp|Myrvold|Woodcock|2018}} | ||
पूरा | |||
एक | |||
== गैलरी == | == गैलरी == | ||
<gallery> | <gallery> | ||
File:Cayley graphs of the quaternion group.png|चतुष्कोणीय समूह के दो | File:Index.php?title=File:Cayley graphs of the quaternion group.png|चतुष्कोणीय समूह के दो समरूपी [[केली ग्राफ]]। | ||
File:Cayley graph of quaternion group on torus.png|टॉरस में | File:Index.php?title=File:Cayley graph of quaternion group on torus.png|टॉरस में अंतः स्थापित चतुर्धातुक समूह का केली लेखाचित्र। | ||
File:Quaternion group.webm| | File:Index.php?title=File:Quaternion group.webm|स्थूलक में सन्निहित किए गए चतुर्धातुक समूह के केली लेखाचित्र का वीडियो। | ||
File:Heawood graph and map on torus.png| | File:Index.php?title=File:Heawood graph and map on torus.png|स्थूलक में सन्निहित किया गया हीवुड लेखाचित्र और संबंधित मानचित्र। | ||
File:Pappus-graph-on-torus.png| | File:Index.php?title=File:Pappus-graph-on-torus.png|स्थूलक में सन्निहित [[पप्पू ग्राफ]] और संबद्ध मानचित्र। | ||
</gallery> | </gallery> | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ प्लेनर ग्राफ ]] | * [[ प्लेनर ग्राफ |समतली आलेख]] | ||
* [[ सामयिक ग्राफ सिद्धांत ]] | * [[ सामयिक ग्राफ सिद्धांत |सांस्थितिक आलेख सिद्धांत]] | ||
* | * क्सास्ज़र बहुतल | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
| Line 136: | Line 134: | ||
}} | }} | ||
*{{citation | *{{citation | ||
| last1 = | | last1 = न्यूफेल्ड | first1 = यूजीन | ||
| last2 = | | last2 = मायर्वोल्ड | first2 = वेंडी | author2-link = वेंडी मायरवॉल्ड | ||
| chapter = | | chapter = प्रैक्टिकल टोरोइडैलिटी परीक्षण | ||
| pages = 574–580 |isbn=978-0-89871-390-9 | | pages = 574–580 |isbn=978-0-89871-390-9 | ||
| title = | | title = असतत एल्गोरिदम पर आठवीं वार्षिक एसीएम-सियाम संगोष्ठी की कार्यवाही | ||
| chapter-url = https://dl.acm.org/doi/10.5555/314161.314392 | | chapter-url = https://dl.acm.org/doi/10.5555/314161.314392 | ||
| year = 1997}}. | | year = 1997}}. | ||
Revision as of 00:52, 27 April 2023
एक टोरस्र्स पर सन्निहित 14 शीर्षों वाला एक घनीय लेखाचित्र
स्थूलक में सन्निहित किया गया हीवुड लेखाचित्र और संबंधित मानचित्र।
आलेख सिद्धांत के गणितीय क्षेत्र में, टोरॉयडल लेखाचित्र एक लेखाचित्र (असतत गणित) है जो स्थूलक पर लेखाचित्र सन्निहित हो सकता है। दूसरे शब्दों में, लेखाचित्र के शीर्ष (आलेख सिद्धांत) को एक स्थूलक पर रखा जा सकता है कि कोई किनारा पार न हो।
उदाहरण
कोई भी लेखाचित्र जिसे एक समतल में सन्निहित किया जा सकता है, एक स्थूलक में भी सन्निहित किया जा सकता है। श्रेणी (गणित) 1 का टॉरॉयडल लेखाचित्र एक स्थूलक में सन्निहित है लेकिन एक समतल में नहीं किया जा सकता। हीवुड लेखाचित्र, पुर्ण लेखाचित्र K7 (और इसलिए K5 और K6), पीटरसन लेखाचित्र (और इसलिए पूर्ण द्विदलीय लेखाचित्र K3,3, चूंकि पीटरसन लेखाचित्र में इसका एक उपखंड सम्मिलित है), ब्लानुसा स्नार्क्स में से एक,[1] और सभी मोबियस सोपान टॉरॉयडल हैं। अधिक सामान्यतः,पारगमन संख्या (आलेख सिद्धांत) 1 वाला कोई भी लेखाचित्र टॉरॉयडल होता है। अधिक पारगमन अंक वाले कुछ लेखाचित्र भी टोरॉयडल हैं: मोबियस-कैंटर लेखाचित्र, उदाहरण के लिए, पारगमन अंक 4 और टोरॉयडल है।[2]
गुण
किसी भी टोरॉयडल लेखाचित्र में अधिक से अधिक 7 रंगीन संख्या होती है।[3] पूरा लेखाचित्र K7 रंगीन संख्या 7 के साथ टोरॉयडल लेखाचित्र का एक उदाहरण प्रदान करता है।[4]
किसी भी त्रिकोण-मुक्त टॉरॉयडल लेखाचित्र में अधिकतम 4 वर्णिक संख्या होती है।[5]
फेरी के प्रमेय के अनुरूप परिणाम से, किसी भी टोरॉयडल लेखाचित्र को आवधिक सीमा परिस्थिति के साथ एक आयत में सीधे किनारों के साथ लेखाचित्र आरेखण हो सकता है।[6] इसके अलावा, टुट्टे के वसंत प्रमेय का समधर्मी इस स्तिथि में लागू होता है।[7]
टॉरॉयडल लेखाचित्र में अधिकतम 7 पृष्ठों के साथ पुस्तक अंत: स्थापन भी होती है।[8]
रुकावटें
रॉबर्टसन-सीमोर प्रमेय के अनुसार, न्यूनतम गैर-टोरॉयडल लेखाचित्र का एक परिमित सम्मुच्चय H उपस्थित है, जैसे कि एक लेखाचित्र टॉरॉयडल है यदि और केवल यदि H में कोई लेखाचित्र लघु नहीं है। अर्थात्, H टोरॉयडल लेखाचित्र के लिए वर्जित लेखाचित्र लक्षण वर्णन का सम्मुच्चय बनाता है। पूरा सम्मुच्चय H ज्ञात नहीं है, लेकिन इसमें कम से कम 17,523 लेखाचित्र हैं। वैकल्पिक रूप से, कम से कम 250,815 गैर-टोरॉयडल लेखाचित्र हैं जो सांस्थितिक अल्प क्रमण में न्यूनतम हैं। एक लेखाचित्र टोरॉयडल है यदि और केवल यदि इसमें इन लेखाचित्र में से कोई भी सांस्थितिक अल्प के रूप में नहीं है।[9]
गैलरी
- Index.php?title=File:Cayley graphs of the quaternion group.png
चतुष्कोणीय समूह के दो समरूपी केली ग्राफ।
- Index.php?title=File:Cayley graph of quaternion group on torus.png
टॉरस में अंतः स्थापित चतुर्धातुक समूह का केली लेखाचित्र।
- Index.php?title=File:Quaternion group.webm
स्थूलक में सन्निहित किए गए चतुर्धातुक समूह के केली लेखाचित्र का वीडियो।
- Index.php?title=File:Heawood graph and map on torus.png
स्थूलक में सन्निहित किया गया हीवुड लेखाचित्र और संबंधित मानचित्र।
- Index.php?title=File: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
- न्यूफेल्ड, यूजीन; मायर्वोल्ड, वेंडी (1997), "प्रैक्टिकल टोरोइडैलिटी परीक्षण", असतत एल्गोरिदम पर आठवीं वार्षिक एसीएम-सियाम संगोष्ठी की कार्यवाही, 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.
