घन ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Graph with all vertices of degree 3}}[[File:Petersen1 tiny.svg|thumb|right|[[पीटरसन ग्राफ]]़ एक घन ग्राफ़ है।]] | {{Short description|Graph with all vertices of degree 3}}[[File:Petersen1 tiny.svg|thumb|right|[[पीटरसन ग्राफ]]़ एक घन ग्राफ़ है।]] | ||
[[File:Biclique K 3 3.svg|thumb|180px|right|सं[[पूर्ण द्विदलीय ग्राफ]] <math>K_{3,3}</math> बाइक्यूबिक ग्राफ़ का एक उदाहरण है]]ग्राफ़ सिद्धांत के गणित क्षेत्र में एक घन ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें सभी शीर्षों (ग्राफ़ सिद्धांत) की डिग्री (ग्राफ़ सिद्धांत) तीन होती है। दूसरे शब्दों में एक घन ग्राफ़ एक 3-[[नियमित ग्राफ]] | [[File:Biclique K 3 3.svg|thumb|180px|right|सं[[पूर्ण द्विदलीय ग्राफ]] <math>K_{3,3}</math> बाइक्यूबिक ग्राफ़ का एक उदाहरण है]]ग्राफ़ सिद्धांत के गणित क्षेत्र में एक घन ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें सभी शीर्षों (ग्राफ़ सिद्धांत) की डिग्री (ग्राफ़ सिद्धांत) तीन होती है। दूसरे शब्दों में एक घन ग्राफ़ एक 3-[[नियमित ग्राफ]] है। घन ग्राफ़ को त्रिसंयोजक ग्राफ़ भी कहा जाता है। | ||
बाइक्यूबिक ग्राफ़ एक क्यूबिक [[द्विदलीय ग्राफ]] | बाइक्यूबिक ग्राफ़ एक क्यूबिक [[द्विदलीय ग्राफ]] है। | ||
==समरूपता== | ==समरूपता== | ||
1932 में आर. एम. फोस्टर | 1932 में आर. एम. फोस्टर या रोनाल्ड एम. [[पालक जनगणना|फोस्टर जनगणना]] घन [[सममित ग्राफ]] के उदाहरण एकत्र करना प्रारंभ किया जिससे फोस्टर जनगणना की प्रारंभ हुई।<ref name="Ref_Foster">{{Citation|first1=R. M.|last1=Foster|title=Geometrical Circuits of Electrical Networks|journal=[[Transactions of the American Institute of Electrical Engineers]]|volume=51|pages=309–317|year=1932|doi=10.1109/T-AIEE.1932.5056068|issue=2|s2cid=51638449}}.</ref> कई प्रसिद्ध व्यक्तिगत ग्राफ घन और सममित हैं जिनमें जल गैस और बिजली, पीटरसन ग्राफ, [[हेवुड ग्राफ]], मोबियस-कांटोर ग्राफ, [[पप्पस ग्राफ]], [[Desargues ग्राफ|देसरगेस ग्राफ]], नाउरू सम्मिलित हैं। ग्राफ़, [[कॉक्सेटर ग्राफ]], टुटे-कॉक्सेटर ग्राफ़, [[डाइक ग्राफ]], [[पालक ग्राफ|फोस्टर ग्राफ]] और बिग्स-स्मिथ ग्राफ़ डब्ल्यू. टी. टुटे ने सममित घन ग्राफ़ को सबसे छोटे पूर्णांक संख्या s द्वारा वर्गीकृत किया है, जिससे लंबाई s के प्रत्येक दो उन्मुख पथों को ग्राफ़ की बिल्कुल एक समरूपता द्वारा एक दूसरे से मैप किया जा सकता है। उन्होंने दिखाया कि s अधिकतम 5 है, और 1 से 5 तक s के प्रत्येक संभावित मान वाले ग्राफ़ के उदाहरण प्रदान किए जाते है। <ref>रेफरी>{{Citation | ||
| doi = 10.4153/CJM-1959-057-2 | | doi = 10.4153/CJM-1959-057-2 | ||
| last = Tutte | first = W. T. | | last = Tutte | first = W. T. | ||
| Line 15: | Line 15: | ||
| volume = 11 | | volume = 11 | ||
| year = 1959| s2cid = 124273238 | doi-access = free | | year = 1959| s2cid = 124273238 | doi-access = free | ||
}}.</ref> | }}.<nowiki></ref></nowiki></ref> | ||
[[अर्ध-सममितीय ग्राफ]] या अर्ध-सममितीय घन ग्राफ़ में [[ग्रे ग्राफ]] (सबसे छोटा अर्ध-सममित घन ग्राफ़), [[ज़ुब्लज़ाना ग्राफ़]] और [[सभी 12-पिंजरे|सभी 12-केज]] सम्मिलित हैं। | |||
[[ | [[फल ग्राफ]] बिना किसी समरूपता वाले पांच सबसे छोटे घन ग्राफों में से एक है:<ref>रेफरी>{{citation|last1=Bussemaker|first1=F. C.|last2=Cobeljic|first2=S.|last3=Cvetkovic|first3=D. M.|last4=Seidel|first4=J. J.|publisher=Dept. of Mathematics and Computing Science, Eindhoven University of Technology|series=EUT report|title=Computer investigation of cubic graphs|url=https://research.tue.nl/en/publications/computer-investigation-of-cubic-graphs|volume=76-WSK-01|year=1976}}<nowiki></ref></nowiki></ref> | ||
इसमें केवल एक [[ग्राफ ऑटोमोर्फिज्म]], पहचान ऑटोमोर्फिज्म है। <ref>रेफरी>{{Citation | last1=Frucht | first1=R. | title=Graphs of degree three with a given abstract group | doi = 10.4153/CJM-1949-033-6 | mr=0032987 | year=1949 | journal=[[Canadian Journal of Mathematics]] | issn=0008-414X | volume=1 | issue=4 | pages=365–378| s2cid=124723321 }}.<nowiki></ref></nowiki></ref> | |||
==रंग और स्वतंत्र सेट== | ==रंग और स्वतंत्र सेट== | ||
ब्रूक्स प्रमेय के अनुसार पूर्ण ग्राफ K | ब्रूक्स प्रमेय के अनुसार पूर्ण ग्राफ ''K''<sub>4</sub> के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ अधिकतम तीन रंगों के साथ एक [[शीर्ष रंग]] है। इसलिए ''K''<sub>4</sub> के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ़ इसमें कम से कम n/3 शीर्षों का एक स्वतंत्र सेट (ग्राफ सिद्धांत) है, जहां n ग्राफ़ में शीर्षों की संख्या है: उदाहरण के लिए 3-रंग में सबसे बड़े रंग वर्ग में कम से कम इतने शीर्ष होते हैं। | ||
विज़िंग के प्रमेय के अनुसार प्रत्येक घन ग्राफ़ को किनारे के रंग के लिए तीन या चार रंगों की आवश्यकता होती है। 3-किनारों वाले रंग को टैट रंग के रूप में जाना जाता है और यह ग्राफ़ के किनारों को तीन पूर्ण मिलानों में विभाजित करता है। कोनिग के प्रमेय (ग्राफ सिद्धांत) द्वारा | विज़िंग के प्रमेय के अनुसार प्रत्येक घन ग्राफ़ को किनारे के रंग के लिए तीन या चार रंगों की आवश्यकता होती है। 3-किनारों वाले रंग को टैट रंग के रूप में जाना जाता है और यह ग्राफ़ के किनारों को तीन पूर्ण मिलानों में विभाजित करता है। कोनिग के प्रमेय (ग्राफ सिद्धांत) द्वारा या कोनिग की रेखा रंग प्रमेय के अनुसार प्रत्येक बाइक्यूबिक ग्राफ में एक टैट रंग होता है। | ||
ब्रिजलेस क्यूबिक ग्राफ जिनमें टैट रंग नहीं होता है उन्हें [[स्नार्क (ग्राफ सिद्धांत)]] के रूप में जाना जाता है। इनमें पीटरसन ग्राफ, टिट्ज़ का ग्राफ, ब्लानुसा स्नार्क, [[ फूल स्नार्क ]], [[डबल-स्टार स्नार्क]], [[निराला व्यंग्य]] और [[वॉटकिंस स्नार्क]] सम्मिलित हैं। अलग-अलग व्यंग्यों की अनंत संख्या है।<ref>{{citation | ब्रिजलेस क्यूबिक ग्राफ जिनमें टैट रंग नहीं होता है उन्हें [[स्नार्क (ग्राफ सिद्धांत)]] के रूप में जाना जाता है। इनमें पीटरसन ग्राफ, टिट्ज़ का ग्राफ, ब्लानुसा स्नार्क, [[ फूल स्नार्क ]], [[डबल-स्टार स्नार्क]], [[निराला व्यंग्य]] और [[वॉटकिंस स्नार्क]] सम्मिलित हैं। अलग-अलग व्यंग्यों की अनंत संख्या है।<ref>{{citation | ||
| Line 41: | Line 42: | ||
==[[टोपोलॉजी]] और ज्यामिति== | ==[[टोपोलॉजी]] और ज्यामिति== | ||
क्यूबिक ग्राफ़ टोपोलॉजी में कई तरह से स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए यदि कोई ग्राफ़ (असतत गणित) को 1-आयामी [[सीडब्ल्यू कॉम्प्लेक्स]] मानता है, तो क्यूबिक ग्राफ़ [[सामान्य संपत्ति]] है, जिसमें अधिकांश 1-सेल संलग्न मानचित्र ग्राफ़ के 0- | क्यूबिक ग्राफ़ टोपोलॉजी में कई तरह से स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए यदि कोई ग्राफ़ (असतत गणित) को 1-आयामी [[सीडब्ल्यू कॉम्प्लेक्स]] मानता है, तो क्यूबिक ग्राफ़ [[सामान्य संपत्ति]] है, जिसमें अधिकांश 1-सेल संलग्न मानचित्र ग्राफ़ के 0-स्केलेटन से अलग होते हैं। क्यूबिक ग्राफ़ भी तीन आयामों में [[ बहुतल ]] के ग्राफ़ के रूप में बनाए जाते हैं, पॉलीहेड्रा जैसे कि नियमित डोडेकेहेड्रॉन की गुण के साथ कि प्रत्येक शीर्ष पर तीन चेहरे मिलते हैं। | ||
[[File:Graph-encoded map.svg|thumb|upright=1.8|ग्राफ़-एन्कोडेड मानचित्र के रूप में एक समतल एम्बेडिंग का प्रतिनिधित्व]]द्वि-आयामी सतह पर एम्बेड किए गए एक | [[File:Graph-encoded map.svg|thumb|upright=1.8|ग्राफ़-एन्कोडेड मानचित्र के रूप में एक समतल एम्बेडिंग का प्रतिनिधित्व]]द्वि-आयामी सतह पर एम्बेड किए गए एक इच्छानुसार ग्राफ को एक क्यूबिक ग्राफ संरचना के रूप में दर्शाया जा सकता है जिसे [[ग्राफ़-एन्कोडेड मानचित्र]] के रूप में जाना जाता है। इस संरचना में एक घन ग्राफ का प्रत्येक शीर्ष एम्बेडिंग के एक ध्वज (ज्यामिति) का प्रतिनिधित्व करता है एक शीर्ष किनारे और सतह के चेहरे का परस्पर घटना त्रिगुण प्रत्येक ध्वज के तीन निकट तीन ध्वज हैं जो इस परस्पर घटना के सदस्यों में से एक को तीन बार बदलकर और अन्य दो सदस्यों को अपरिवर्तित छोड़कर प्राप्त किए जा सकते हैं।<ref>{{citation | ||
| last1 = Bonnington | first1 = C. Paul | | last1 = Bonnington | first1 = C. Paul | ||
| last2 = Little | first2 = Charles H. C. | | last2 = Little | first2 = Charles H. C. | ||
| Line 52: | Line 53: | ||
==हैमिल्टोनिसिटी== | ==हैमिल्टोनिसिटी== | ||
क्यूबिक ग्राफ़ के [[हैमिल्टनियन चक्र]] पर बहुत शोध हुआ है। 1880 में | क्यूबिक ग्राफ़ के [[हैमिल्टनियन चक्र]] पर बहुत शोध हुआ है। 1880 में पीटर गुथरी टैट या पी.जी. टैट ने अनुमान लगाया कि प्रत्येक घन [[बहुफलकीय ग्राफ]] में एक [[हैमिल्टनियन सर्किट|हैमिल्टनियन परिपथ]] होता है। [[ विलियम थॉमस ऑल ]] ने 1946 में टैट के अनुमान, 46-वर्टेक्स [[ सभी ग्राफ ]] का एक प्रति-उदाहरण प्रदान किया था । 1971 में, टुट्टे ने अनुमान लगाया कि सभी बाइक्यूबिक ग्राफ हैमिल्टनियन हैं। चूँकि, जोसेफ हॉर्टन ने [[हॉर्टन ग्राफ]], 96 शीर्षों पर एक प्रति-उदाहरण प्रदान किया था।<ref name="Ref_a">बॉन्डी, जे.ए. और मूर्ति, यू.एस.आर. ग्राफ सिद्धांत अनुप्रयोगों के साथ। न्यूयॉर्क: नॉर्थ हॉलैंड, पी. 240, 1976।</ref> इसके बाद में, [[मार्क एलिंघम]] ने दो और प्रतिउदाहरण बनाए: एलिंगहैम-हॉर्टन ग्राफ़<ref name="Ref_b">एलिंघम, एम.एन. नॉन-हैमिल्टनियन 3-कनेक्टेड क्यूबिक पार्टाइट ग्राफ़। अनुसंधान रिपोर्ट संख्या 28, गणित विभाग, विश्वविद्यालय। मेलबर्न, मेलबर्न, 1981.</ref><ref name="Ref_c">{{Citation|last1=Ellingham|first1=M. N.|last2=Horton|first2=J. D.|title= Non-Hamiltonian 3-connected cubic bipartite graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B| volume=34| pages=350–353| year=1983| doi=10.1016/0095-8956(83)90046-1|issue=3|doi-access=free}}.</ref> बार्नेट का अनुमान, टैट और टुट्टे के अनुमान का एक अभी भी खुला संयोजन, बताता है कि प्रत्येक बाइबिक पॉलीहेड्रल ग्राफ हैमिल्टनियन है। जब एक घन ग्राफ हैमिल्टनियन होता है, तो [[ एलसीएफ संकेतन ]] इसे संक्षिप्त रूप से प्रस्तुत करने की अनुमति देता है। | ||
यदि एक क्यूबिक ग्राफ को सभी एन-वर्टेक्स क्यूबिक ग्राफ़ के बीच [[यादृच्छिक ग्राफ]] चुना जाता है, तो यह हैमिल्टनियन होने की बहुत संभावना है: एन-वर्टेक्स क्यूबिक ग्राफ़ का अनुपात जो हैमिल्टनियन है, सीमा में एक हो जाता है क्योंकि एन अनंत तक जाता है। रेफरी>{{citation | यदि एक क्यूबिक ग्राफ को सभी एन-वर्टेक्स क्यूबिक ग्राफ़ के बीच [[यादृच्छिक ग्राफ]] चुना जाता है, तो यह हैमिल्टनियन होने की बहुत संभावना है: एन-वर्टेक्स क्यूबिक ग्राफ़ का अनुपात जो हैमिल्टनियन है, सीमा में एक हो जाता है क्योंकि एन अनंत तक जाता है। <ref>रेफरी>{{citation | ||
| last1 = Robinson | first1 = R.W. | | last1 = Robinson | first1 = R.W. | ||
| last2 = Wormald | first2 = N.C. | | last2 = Wormald | first2 = N.C. | ||
| Line 63: | Line 64: | ||
| title = Almost all regular graphs are Hamiltonian | | title = Almost all regular graphs are Hamiltonian | ||
| volume = 5 | | volume = 5 | ||
| year = 1994}}.</ref> | | year = 1994}}.<nowiki></ref></nowiki></ref> | ||
[[डेविड एप्सटीन]] ने अनुमान लगाया कि प्रत्येक एन-वर्टेक्स क्यूबिक ग्राफ में अधिकतम 2 | [[डेविड एप्सटीन]] ने अनुमान लगाया कि प्रत्येक एन-वर्टेक्स क्यूबिक ग्राफ में अधिकतम 2<sup>''n''/3</sup> होते हैं (लगभग 1.260<sup>n</sup>) अलग-अलग हैमिल्टनियन चक्र, और इतने सारे चक्रों के साथ घन ग्राफ़ के उदाहरण प्रदान किए गए।<ref>{{citation | ||
| last = Eppstein | first = David | author-link = David Eppstein | | last = Eppstein | first = David | author-link = David Eppstein | ||
| arxiv = cs.DS/0302030 | issue = 1 | | arxiv = cs.DS/0302030 | issue = 1 | ||
| Line 73: | Line 74: | ||
| url = http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf | | url = http://jgaa.info/accepted/2007/Eppstein2007.11.1.pdf | ||
| volume = 11 | | volume = 11 | ||
| year = 2007 | doi=10.7155/jgaa.00137}}.</ref> अलग-अलग हैमिल्टनियन चक्रों की संख्या के लिए सबसे अच्छा सिद्ध अनुमान | | year = 2007 | doi=10.7155/jgaa.00137}}.</ref> अलग-अलग हैमिल्टनियन चक्रों की संख्या के लिए सबसे अच्छा सिद्ध अनुमान <math> O({1.276}^n)</math> है <ref>{{citation | ||
| last = Gebauer | | last = Gebauer | ||
| first = H. | | first = H. | ||
| Line 98: | Line 99: | ||
| volume = 97 | | volume = 97 | ||
| year = 2006}}.</ref> | | year = 2006}}.</ref> | ||
ग्राफ सिद्धांत पर पहले पेपर के भाग के रूप में 1736 में [[लियोनहार्ड यूलर]] द्वारा सिद्ध की गई [[ हाथ मिलाना लेम्मा ]] से यह पता चलता है कि प्रत्येक घन ग्राफ में शीर्षों की संख्या सम होती है। | |||
ग्राफ सिद्धांत पर पहले पेपर के भाग के रूप में 1736 में [[लियोनहार्ड यूलर]] द्वारा सिद्ध की गई [[ हाथ मिलाना लेम्मा | हेन्डशेकिंग लेम्मा]] से यह पता चलता है कि प्रत्येक घन ग्राफ में शीर्षों की संख्या सम होती है। | |||
पीटरसन के प्रमेय में कहा गया है कि प्रत्येक क्यूबिक ब्रिज (ग्राफ़ सिद्धांत) ग्राफ़ का पूर्ण मिलान होता है।<ref name="Pet1891">{{Citation | पीटरसन के प्रमेय में कहा गया है कि प्रत्येक क्यूबिक ब्रिज (ग्राफ़ सिद्धांत) ग्राफ़ का पूर्ण मिलान होता है।<ref name="Pet1891">{{Citation | ||
| Line 111: | Line 113: | ||
| url = https://zenodo.org/record/2304433 | | url = https://zenodo.org/record/2304433 | ||
| doi-access = free | | doi-access = free | ||
}}.</ref> | }}.</ref> लास्ज़लो लोवाज़|लोवाज़ और माइकल डी. प्लमर ने अनुमान लगाया कि प्रत्येक क्यूबिक ब्रिजलेस ग्राफ़ में पूर्ण मिलान की एक घातीय संख्या होती है। अनुमान हाल ही में सिद्ध हुआ था, जिसमें दिखाया गया था कि n शीर्षों वाले प्रत्येक घन ब्रिजलेस ग्राफ में कम से कम 2 <sup>n/3656</sup> पूर्ण मिलान होता है।<ref name="EKKKN11">{{citation | ||
लास्ज़लो लोवाज़|लोवाज़ और माइकल डी. प्लमर ने अनुमान लगाया कि प्रत्येक क्यूबिक ब्रिजलेस ग्राफ़ में पूर्ण मिलान की एक घातीय संख्या होती है। अनुमान हाल ही में | |||
| last1 = Esperet | first1 = Louis | | last1 = Esperet | first1 = Louis | ||
| last2 = Kardoš | first2 = František | | last2 = Kardoš | first2 = František | ||
| Line 127: | Line 128: | ||
| s2cid = 4401537 | | s2cid = 4401537 | ||
}}.</ref> | }}.</ref> | ||
==एल्गोरिदम और जटिलता== | ==एल्गोरिदम और जटिलता== | ||
कई शोधकर्ताओं ने घन ग्राफ़ तक सीमित [[घातीय समय]] एल्गोरिदम की जटिलता का अध्ययन किया है। उदाहरण के लिए, ग्राफ़ के [[पथ अपघटन]] के लिए [[गतिशील प्रोग्रामिंग]] | कई शोधकर्ताओं ने घन ग्राफ़ तक सीमित [[घातीय समय]] एल्गोरिदम की जटिलता का अध्ययन किया है। उदाहरण के लिए, ग्राफ़ के [[पथ अपघटन]] के लिए [[गतिशील प्रोग्रामिंग]] प्रयुक्त करके फ़ोमिन और होई ने दिखाया कि समय 2<sup>''n''/6 + o(''n'')</sup> में अपने [[अधिकतम स्वतंत्र सेट]] कैसे खोजे सकते है.<ref name="fh06"/> क्यूबिक ग्राफ़ में [[ट्रैवलिंग सेल्समैन की समस्या]] को समय O(1.2312<sup>n</sup>) और बहुपद स्थान में हल किया जा सकता है।<ref name="XiaoNag13">{{citation | ||
|first1=Mingyu | |first1=Mingyu | ||
|last1=Xiao | |last1=Xiao | ||
| Line 156: | Line 158: | ||
|bibcode = 2012arXiv1212.6831X| s2cid = 7654681 | |bibcode = 2012arXiv1212.6831X| s2cid = 7654681 | ||
}}.</ref> | }}.</ref> | ||
कई महत्वपूर्ण ग्राफ अनुकूलन समस्याएं [[ APX ]] हैं, जिसका अर्थ है कि, | |||
कई महत्वपूर्ण ग्राफ अनुकूलन समस्याएं [[ APX | एपीएक्स]] हैं, जिसका अर्थ है कि, चूँकि उनके पास सन्निकटन एल्गोरिदम हैं जिनका [[सन्निकटन अनुपात]] एक स्थिरांक से घिरा है, उनके पास [[बहुपद समय सन्निकटन योजना]]एं नहीं हैं जिनका सन्निकटन अनुपात 1 तक जाता है जब तक कि P=NP इनमें न्यूनतम वर्टेक्स कवर, अधिकतम स्वतंत्र सेट, न्यूनतम डोमिनेटिंग सेट और अधिकतम कट खोजने की समस्याएं सम्मिलित हैं।<ref>{{citation | |||
| last1 = Alimonti | first1 = Paola | | last1 = Alimonti | first1 = Paola | ||
| last2 = Kann | first2 = Viggo | | last2 = Kann | first2 = Viggo | ||
| Line 166: | Line 169: | ||
| volume = 237 | | volume = 237 | ||
| year = 2000| doi-access = free | | year = 2000| doi-access = free | ||
}}.</ref> | }}.</ref> क्यूबिक ग्राफ का क्रॉसिंग नंबर (ग्राफ सिद्धांत) (किनारों की न्यूनतम संख्या जो किसी भी [[ग्राफ ड्राइंग]] में क्रॉस करती है) भी क्यूबिक ग्राफ के लिए [[ एनपी कठिन | एनपी कठिन]] है किन्तु अनुमानित किया जा सकता है।<ref name="Hlinny2006">{{citation|first=Petr|last=Hliněný|title=Crossing number is hard for cubic graphs|journal=[[Journal of Combinatorial Theory]]|series=Series B|volume=96|issue=4|pages=455–471|year=2006|doi=10.1016/j.jctb.2005.09.009|doi-access=free}}.</ref> क्यूबिक ग्राफ़ पर [[ट्रैवलिंग सेल्समैन की समस्या]] 1153/1152 से कम किसी भी कारक के अंदर अनुमानित करने के लिए एनपी-कठिन सिद्ध हुई है।<ref>{{citation | ||
क्यूबिक ग्राफ का क्रॉसिंग नंबर (ग्राफ सिद्धांत) (किनारों की न्यूनतम संख्या जो किसी भी [[ग्राफ ड्राइंग]] में क्रॉस करती है) भी क्यूबिक ग्राफ के लिए [[ एनपी कठिन ]] है | |||
क्यूबिक ग्राफ़ पर [[ट्रैवलिंग सेल्समैन की समस्या]] 1153/1152 से कम किसी भी कारक के | |||
| first1 = Marek | last1 = Karpinski | | first1 = Marek | last1 = Karpinski | ||
| first2 = Richard | last2 = Schmied | | first2 = Richard | last2 = Schmied | ||
| Line 174: | Line 175: | ||
| title = Approximation Hardness of Graphic TSP on Cubic Graphs | | title = Approximation Hardness of Graphic TSP on Cubic Graphs | ||
| year = 2013|bibcode = 2013arXiv1304.6800K}}.</ref> | | year = 2013|bibcode = 2013arXiv1304.6800K}}.</ref> | ||
==यह भी देखें== | ==यह भी देखें== | ||
{{commons category|3-regular graphs}} | {{commons category|3-regular graphs}} | ||
Revision as of 21:12, 6 July 2023
पीटरसन ग्राफ़ एक घन ग्राफ़ है।
ग्राफ़ सिद्धांत के गणित क्षेत्र में एक घन ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें सभी शीर्षों (ग्राफ़ सिद्धांत) की डिग्री (ग्राफ़ सिद्धांत) तीन होती है। दूसरे शब्दों में एक घन ग्राफ़ एक 3-नियमित ग्राफ है। घन ग्राफ़ को त्रिसंयोजक ग्राफ़ भी कहा जाता है।
बाइक्यूबिक ग्राफ़ एक क्यूबिक द्विदलीय ग्राफ है।
समरूपता
1932 में आर. एम. फोस्टर या रोनाल्ड एम. फोस्टर जनगणना घन सममित ग्राफ के उदाहरण एकत्र करना प्रारंभ किया जिससे फोस्टर जनगणना की प्रारंभ हुई।[1] कई प्रसिद्ध व्यक्तिगत ग्राफ घन और सममित हैं जिनमें जल गैस और बिजली, पीटरसन ग्राफ, हेवुड ग्राफ, मोबियस-कांटोर ग्राफ, पप्पस ग्राफ, देसरगेस ग्राफ, नाउरू सम्मिलित हैं। ग्राफ़, कॉक्सेटर ग्राफ, टुटे-कॉक्सेटर ग्राफ़, डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ़ डब्ल्यू. टी. टुटे ने सममित घन ग्राफ़ को सबसे छोटे पूर्णांक संख्या s द्वारा वर्गीकृत किया है, जिससे लंबाई s के प्रत्येक दो उन्मुख पथों को ग्राफ़ की बिल्कुल एक समरूपता द्वारा एक दूसरे से मैप किया जा सकता है। उन्होंने दिखाया कि s अधिकतम 5 है, और 1 से 5 तक s के प्रत्येक संभावित मान वाले ग्राफ़ के उदाहरण प्रदान किए जाते है। [2]</nowiki></ref>
अर्ध-सममितीय ग्राफ या अर्ध-सममितीय घन ग्राफ़ में ग्रे ग्राफ (सबसे छोटा अर्ध-सममित घन ग्राफ़), ज़ुब्लज़ाना ग्राफ़ और सभी 12-केज सम्मिलित हैं।
फल ग्राफ बिना किसी समरूपता वाले पांच सबसे छोटे घन ग्राफों में से एक है:[3]</nowiki></ref>
इसमें केवल एक ग्राफ ऑटोमोर्फिज्म, पहचान ऑटोमोर्फिज्म है। [4]</nowiki></ref>
रंग और स्वतंत्र सेट
ब्रूक्स प्रमेय के अनुसार पूर्ण ग्राफ K4 के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ अधिकतम तीन रंगों के साथ एक शीर्ष रंग है। इसलिए K4 के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ़ इसमें कम से कम n/3 शीर्षों का एक स्वतंत्र सेट (ग्राफ सिद्धांत) है, जहां n ग्राफ़ में शीर्षों की संख्या है: उदाहरण के लिए 3-रंग में सबसे बड़े रंग वर्ग में कम से कम इतने शीर्ष होते हैं।
विज़िंग के प्रमेय के अनुसार प्रत्येक घन ग्राफ़ को किनारे के रंग के लिए तीन या चार रंगों की आवश्यकता होती है। 3-किनारों वाले रंग को टैट रंग के रूप में जाना जाता है और यह ग्राफ़ के किनारों को तीन पूर्ण मिलानों में विभाजित करता है। कोनिग के प्रमेय (ग्राफ सिद्धांत) द्वारा या कोनिग की रेखा रंग प्रमेय के अनुसार प्रत्येक बाइक्यूबिक ग्राफ में एक टैट रंग होता है।
ब्रिजलेस क्यूबिक ग्राफ जिनमें टैट रंग नहीं होता है उन्हें स्नार्क (ग्राफ सिद्धांत) के रूप में जाना जाता है। इनमें पीटरसन ग्राफ, टिट्ज़ का ग्राफ, ब्लानुसा स्नार्क, फूल स्नार्क , डबल-स्टार स्नार्क, निराला व्यंग्य और वॉटकिंस स्नार्क सम्मिलित हैं। अलग-अलग व्यंग्यों की अनंत संख्या है।[5]
टोपोलॉजी और ज्यामिति
क्यूबिक ग्राफ़ टोपोलॉजी में कई तरह से स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए यदि कोई ग्राफ़ (असतत गणित) को 1-आयामी सीडब्ल्यू कॉम्प्लेक्स मानता है, तो क्यूबिक ग्राफ़ सामान्य संपत्ति है, जिसमें अधिकांश 1-सेल संलग्न मानचित्र ग्राफ़ के 0-स्केलेटन से अलग होते हैं। क्यूबिक ग्राफ़ भी तीन आयामों में बहुतल के ग्राफ़ के रूप में बनाए जाते हैं, पॉलीहेड्रा जैसे कि नियमित डोडेकेहेड्रॉन की गुण के साथ कि प्रत्येक शीर्ष पर तीन चेहरे मिलते हैं।
द्वि-आयामी सतह पर एम्बेड किए गए एक इच्छानुसार ग्राफ को एक क्यूबिक ग्राफ संरचना के रूप में दर्शाया जा सकता है जिसे ग्राफ़-एन्कोडेड मानचित्र के रूप में जाना जाता है। इस संरचना में एक घन ग्राफ का प्रत्येक शीर्ष एम्बेडिंग के एक ध्वज (ज्यामिति) का प्रतिनिधित्व करता है एक शीर्ष किनारे और सतह के चेहरे का परस्पर घटना त्रिगुण प्रत्येक ध्वज के तीन निकट तीन ध्वज हैं जो इस परस्पर घटना के सदस्यों में से एक को तीन बार बदलकर और अन्य दो सदस्यों को अपरिवर्तित छोड़कर प्राप्त किए जा सकते हैं।[6]
हैमिल्टोनिसिटी
क्यूबिक ग्राफ़ के हैमिल्टनियन चक्र पर बहुत शोध हुआ है। 1880 में पीटर गुथरी टैट या पी.जी. टैट ने अनुमान लगाया कि प्रत्येक घन बहुफलकीय ग्राफ में एक हैमिल्टनियन परिपथ होता है। विलियम थॉमस ऑल ने 1946 में टैट के अनुमान, 46-वर्टेक्स सभी ग्राफ का एक प्रति-उदाहरण प्रदान किया था । 1971 में, टुट्टे ने अनुमान लगाया कि सभी बाइक्यूबिक ग्राफ हैमिल्टनियन हैं। चूँकि, जोसेफ हॉर्टन ने हॉर्टन ग्राफ, 96 शीर्षों पर एक प्रति-उदाहरण प्रदान किया था।[7] इसके बाद में, मार्क एलिंघम ने दो और प्रतिउदाहरण बनाए: एलिंगहैम-हॉर्टन ग्राफ़[8][9] बार्नेट का अनुमान, टैट और टुट्टे के अनुमान का एक अभी भी खुला संयोजन, बताता है कि प्रत्येक बाइबिक पॉलीहेड्रल ग्राफ हैमिल्टनियन है। जब एक घन ग्राफ हैमिल्टनियन होता है, तो एलसीएफ संकेतन इसे संक्षिप्त रूप से प्रस्तुत करने की अनुमति देता है।
यदि एक क्यूबिक ग्राफ को सभी एन-वर्टेक्स क्यूबिक ग्राफ़ के बीच यादृच्छिक ग्राफ चुना ज