घन ग्राफ

From Vigyanwiki
पीटरसन ग्राफ़ एक घन ग्राफ़ है।
संपूर्ण द्विदलीय ग्राफ बाइक्यूबिक ग्राफ़ का एक उदाहरण है

ग्राफ़ सिद्धांत के गणित क्षेत्र में एक घन ग्राफ़ एक ग्राफ़ (असतत गणित) है जिसमें सभी शीर्षों (ग्राफ़ सिद्धांत) की डिग्री (ग्राफ़ सिद्धांत) तीन होती है। दूसरे शब्दों में एक घन ग्राफ़ एक 3-नियमित ग्राफ है। घन ग्राफ़ को त्रिसंयोजक ग्राफ़ भी कहा जाता है।

बाइक्यूबिक ग्राफ़ एक क्यूबिक द्विदलीय ग्राफ है।

समरूपता

1932 में आर. एम. फोस्टर या रोनाल्ड एम. फोस्टर जनगणना घन सममित ग्राफ के उदाहरण एकत्र करना प्रारंभ किया जिससे फोस्टर जनगणना की प्रारंभ हुई।[1] कई प्रसिद्ध व्यक्तिगत ग्राफ घन और सममित हैं जिनमें जल गैस और बिजली, पीटरसन ग्राफ, हेवुड ग्राफ, मोबियस-कांटोर ग्राफ, पप्पस ग्राफ, देसरगेस ग्राफ, नाउरू सम्मिलित हैं। ग्राफ़, कॉक्सेटर ग्राफ, टुटे-कॉक्सेटर ग्राफ़, डाइक ग्राफ, फोस्टर ग्राफ और बिग्स-स्मिथ ग्राफ़ डब्ल्यू. टी. टुटे ने सममित घन ग्राफ़ को सबसे छोटे पूर्णांक संख्या s द्वारा वर्गीकृत किया है, जिससे लंबाई s के प्रत्येक दो उन्मुख पथों को ग्राफ़ की बिल्कुल एक समरूपता द्वारा एक दूसरे से मैप किया जा सकता है। उन्होंने दिखाया कि s अधिकतम 5 है, और 1 से 5 तक s के प्रत्येक संभावित मान वाले ग्राफ़ के उदाहरण प्रदान किए जाते है। </ref>[2]

अर्ध-सममितीय ग्राफ या अर्ध-सममितीय घन ग्राफ़ में ग्रे ग्राफ (सबसे छोटा अर्ध-सममित घन ग्राफ़), ज़ुब्लज़ाना ग्राफ़ और सभी 12-केज सम्मिलित हैं।

फल ग्राफ बिना किसी समरूपता वाले पांच सबसे छोटे घन ग्राफों में से एक है:</ref>[3]

इसमें केवल एक ग्राफ ऑटोमोर्फिज्म, पहचान ऑटोमोर्फिज्म है। </ref>[4]






रंग और स्वतंत्र सेट

ब्रूक्स प्रमेय के अनुसार पूर्ण ग्राफ K4 के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ अधिकतम तीन रंगों के साथ एक शीर्ष रंग है। इसलिए K4 के अतिरिक्त प्रत्येक जुड़ा हुआ घन ग्राफ़ इसमें कम से कम n/3 शीर्षों का एक स्वतंत्र सेट (ग्राफ सिद्धांत) है, जहां n ग्राफ़ में शीर्षों की संख्या है: उदाहरण के लिए 3-रंग में सबसे बड़े रंग वर्ग में कम से कम इतने शीर्ष होते हैं।

विज़िंग के प्रमेय के अनुसार प्रत्येक घन ग्राफ़ को किनारे के रंग के लिए तीन या चार रंगों की आवश्यकता होती है। 3-किनारों वाले रंग को टैट रंग के रूप में जाना जाता है और यह ग्राफ़ के किनारों को तीन पूर्ण मिलानों में विभाजित करता है। कोनिग के प्रमेय (ग्राफ सिद्धांत) द्वारा या कोनिग की रेखा रंग प्रमेय के अनुसार प्रत्येक बाइक्यूबिक ग्राफ में एक टैट रंग होता है।

ब्रिजलेस क्यूबिक ग्राफ जिनमें टैट रंग नहीं होता है उन्हें स्नार्क (ग्राफ सिद्धांत) के रूप में जाना जाता है। इनमें पीटरसन ग्राफ, टिट्ज़ का ग्राफ, ब्लानुसा स्नार्क, फूल स्नार्क , डबल-स्टार स्नार्क, निराला व्यंग्य और वॉटकिंस स्नार्क सम्मिलित हैं। अलग-अलग व्यंग्यों की अनंत संख्या है।[5]

टोपोलॉजी और ज्यामिति

क्यूबिक ग्राफ़ टोपोलॉजी में कई तरह से स्वाभाविक रूप से उत्पन्न होते हैं। उदाहरण के लिए यदि कोई ग्राफ़ (असतत गणित) को 1-आयामी सीडब्ल्यू कॉम्प्लेक्स मानता है, तो क्यूबिक ग्राफ़ सामान्य संपत्ति है, जिसमें अधिकांश 1-सेल संलग्न मानचित्र ग्राफ़ के 0-स्केलेटन से अलग होते हैं। क्यूबिक ग्राफ़ भी तीन आयामों में बहुतल के ग्राफ़ के रूप में बनाए जाते हैं, पॉलीहेड्रा जैसे कि नियमित डोडेकेहेड्रॉन की गुण के साथ कि प्रत्येक शीर्ष पर तीन चेहरे मिलते हैं।

ग्राफ़-एन्कोडेड मानचित्र के रूप में एक समतल एम्बेडिंग का प्रतिनिधित्व

द्वि-आयामी सतह पर एम्बेड किए गए एक इच्छानुसार ग्राफ को एक क्यूबिक ग्राफ संरचना के रूप में दर्शाया जा सकता है जिसे ग्राफ़-एन्कोडेड मानचित्र के रूप में जाना जाता है। इस संरचना में एक घन ग्राफ का प्रत्येक शीर्ष एम्बेडिंग के एक ध्वज (ज्यामिति) का प्रतिनिधित्व करता है एक शीर्ष किनारे और सतह के चेहरे का परस्पर घटना त्रिगुण प्रत्येक ध्वज के तीन निकट तीन ध्वज हैं जो इस परस्पर घटना के सदस्यों में से एक को तीन बार बदलकर और अन्य दो सदस्यों को अपरिवर्तित छोड़कर प्राप्त किए जा सकते हैं।[6]


हैमिल्टोनिसिटी

क्यूबिक ग्राफ़ के हैमिल्टनियन चक्र पर बहुत शोध हुआ है। 1880 में पीटर गुथरी टैट या पी.जी. टैट ने अनुमान लगाया कि प्रत्येक घन बहुफलकीय ग्राफ में एक हैमिल्टनियन परिपथ होता है। विलियम थॉमस ऑल ने 1946 में टैट के अनुमान, 46-वर्टेक्स सभी ग्राफ का एक प्रति-उदाहरण प्रदान किया था । 1971 में, टुट्टे ने अनुमान लगाया कि सभी बाइक्यूबिक ग्राफ हैमिल्टनियन हैं। चूँकि, जोसेफ हॉर्टन ने हॉर्टन ग्राफ, 96 शीर्षों पर एक प्रति-उदाहरण प्रदान किया था।[7] इसके बाद में, मार्क एलिंघम ने दो और प्रतिउदाहरण बनाए: एलिंगहैम-हॉर्टन ग्राफ़[8][9] बार्नेट का अनुमान, टैट और टुट्टे के अनुमान का एक अभी भी खुला संयोजन, बताता है कि प्रत्येक बाइबिक पॉलीहेड्रल ग्राफ हैमिल्टनियन है। जब एक घन ग्राफ हैमिल्टनियन होता है, तो एलसीएफ संकेतन इसे संक्षिप्त रूप से प्रस्तुत करने की अनुमति देता है।

यदि एक क्यूबिक ग्राफ को सभी एन-वर्टेक्स क्यूबिक ग्राफ़ के बीच यादृच्छिक ग्राफ चुना जाता है, तो यह हैमिल्टनियन होने की बहुत संभावना है: एन-वर्टेक्स क्यूबिक ग्राफ़ का अनुपात जो हैमिल्टनियन है, सीमा में एक हो जाता है क्योंकि एन अनंत तक जाता है। [10]</nowiki></ref>

डेविड एप्सटीन ने अनुमान लगाया कि प्रत्येक एन-वर्टेक्स क्यूबिक ग्राफ में अधिकतम 2n/3 होते हैं (लगभग 1.260n) अलग-अलग हैमिल्टनियन चक्र, और इतने सारे चक्रों के साथ घन ग्राफ़ के उदाहरण प्रदान किए गए।[11] अलग-अलग हैमिल्टनियन चक्रों की संख्या के लिए सबसे अच्छा सिद्ध अनुमान है [12]


अन्य गुण

Unsolved problem in mathematics:

What is the largest possible pathwidth of an -vertex cubic graph?

(more unsolved problems in mathematics)

किसी भी n-वर्टेक्स क्यूबिक ग्राफ़ की पथ चौड़ाई अधिकतम n/6 है। घन ग्राफ़ की पथ-चौड़ाई पर सबसे अच्छी ज्ञात निचली सीमा 0.082n है। यह ज्ञात नहीं है कि इस निचली सीमा और n/6 ऊपरी सीमा के बीच इस अंतर को कैसे कम किया जाए।[13]

ग्राफ सिद्धांत पर पहले पेपर के भाग के रूप में 1736 में लियोनहार्ड यूलर द्वारा सिद्ध की गई हेन्डशेकिंग लेम्मा से यह पता चलता है कि प्रत्येक घन ग्राफ में शीर्षों की संख्या सम होती है।

पीटरसन के प्रमेय में कहा गया है कि प्रत्येक क्यूबिक ब्रिज (ग्राफ़ सिद्धांत) ग्राफ़ का पूर्ण मिलान होता है।[14] लास्ज़लो लोवाज़|लोवाज़ और माइकल डी. प्लमर ने अनुमान लगाया कि प्रत्येक क्यूबिक ब्रिजलेस ग्राफ़ में पूर्ण मिलान की एक घातीय संख्या होती है। अनुमान हाल ही में सिद्ध हुआ था, जिसमें दिखाया गया था कि n शीर्षों वाले प्रत्येक घन ब्रिजलेस ग्राफ में कम से कम 2 n/3656 पूर्ण मिलान होता है।[15]


एल्गोरिदम और जटिलता

कई शोधकर्ताओं ने घन ग्राफ़ तक सीमित घातीय समय एल्गोरिदम की जटिलता का अध्ययन किया है। उदाहरण के लिए, ग्राफ़ के पथ अपघटन के लिए गतिशील प्रोग्रामिंग प्रयुक्त करके फ़ोमिन और होई ने दिखाया कि समय 2n/6 + o(n) में अपने अधिकतम स्वतंत्र सेट कैसे खोजे सकते है.[13] क्यूबिक ग्राफ़ में ट्रैवलिंग सेल्समैन की समस्या को समय O(1.2312n) और बहुपद स्थान में हल किया जा सकता है।[16][17]

कई महत्वपूर्ण ग्राफ अनुकूलन समस्याएं एपीएक्स हैं, जिसका अर्थ है कि, चूँकि उनके पास सन्निकटन एल्गोरिदम हैं जिनका सन्निकटन अनुपात एक स्थिरांक से घिरा है, उनके पास बहुपद समय सन्निकटन योजनाएं नहीं हैं जिनका सन्निकटन अनुपात 1 तक जाता है जब तक कि P=NP इनमें न्यूनतम वर्टेक्स कवर, अधिकतम स्वतंत्र सेट, न्यूनतम डोमिनेटिंग सेट और अधिकतम कट खोजने की समस्याएं सम्मिलित हैं।[18] क्यूबिक ग्राफ का क्रॉसिंग नंबर (ग्राफ सिद्धांत) (किनारों की न्यूनतम संख्या जो किसी भी ग्राफ ड्राइंग में क्रॉस करती है) भी क्यूबिक ग्राफ के लिए एनपी कठिन है किन्तु अनुमानित किया जा सकता है।[19] क्यूबिक ग्राफ़ पर ट्रैवलिंग सेल्समैन की समस्या 1153/1152 से कम किसी भी कारक के अंदर अनुमानित करने के लिए एनपी-कठिन सिद्ध हुई है।[20]

यह भी देखें

Wikimedia Commons has media related to 3-regular graphs.

संदर्भ

  1. ↑ Foster, R. M. (1932), "Geometrical Circuits of Electrical Networks", Transactions of the American Institute of Electrical Engineers, 51 (2): 309–317, doi:10.1109/T-AIEE.1932.5056068, S2CID 51638449.
  2. ↑ Tutte, W. T. (1959), "On the symmetry of cubic graphs", Can. J. Math., 11: 621–624, doi:10.4153/CJM-1959-057-2, S2CID 124273238.
  3. ↑ Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), Computer investigation of cubic graphs, EUT report, vol. 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
  4. ↑ Frucht, R. (1949), "Graphs of degree three with a given abstract group", Canadian Journal of Mathematics, 1 (4): 365–378, doi:10.4153/CJM-1949-033-6, ISSN 0008-414X, MR 0032987, S2CID 124723321.
  5. ↑ Isaacs, R. (1975), "Infinite families of nontrivial trivalent graphs which are not Tait colorable", American Mathematical Monthly, 82 (3): 221–239, doi:10.2307/2319844, JSTOR 2319844.
  6. ↑ Bonnington, C. Paul; Little, Charles H. C. (1995), The Foundations of Topological Graph Theory, Springer-Verlag.
  7. ↑ बॉन्डी, जे.ए. और मूर्ति, यू.एस.आर. ग्राफ सिद्धांत अनुप्रयोगों के साथ। न्यूयॉर्क: नॉर्थ हॉलैंड, पी. 240, 1976।
  8. ↑ एलिंघम, एम.एन. नॉन-हैमिल्टनियन 3-कनेक्टेड क्यूबिक पार्टाइट ग्राफ़। अनुसंधान रिपोर्ट संख्या 28, गणित विभाग, विश्वविद्यालय। मेलबर्न, मेलबर्न, 1981.
  9. ↑ Ellingham, M. N.; Horton, J. D. (1983), "Non-Hamiltonian 3-connected cubic bipartite graphs", Journal of Combinatorial Theory, Series B, 34 (3): 350–353, doi:10.1016/0095-8956(83)90046-1.
  10. ↑ रेफरी>Robinson, R.W.; Wormald, N.C. (1994), "Almost all regular graphs are Hamiltonian", Random Structures and Algorithms, 5 (2): 363–374, doi:10.1002/rsa.3240050209.<nowiki>
  11. ↑ Eppstein, David (2007), "The traveling salesman problem for cubic graphs" (PDF), Journal of Graph Algorithms and Applications, 11 (1): 61–81, arXiv:cs.DS/0302030, doi:10.7155/jgaa.00137.
  12. ↑ Gebauer, H. (2008), "On the number of Hamilton cycles in bounded degree graphs", Proc. 4th Workshop on Analytic Algorithmics and Combinatorics (ANALCO '08), pp. 241–248, doi:10.1137/1.9781611972986.8, ISBN 9781611972986.
  13. ↑ 13.0 13.1 Fomin, Fedor V.; Høie, Kjartan (2006), "Pathwidth of cubic graphs and exact algorithms", Information Processing Letters, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012.
  14. ↑ Petersen, Julius Peter Christian (1891), "Die Theorie der regulären Graphs (The theory of regular graphs)", Acta Mathematica, 15 (15): 193–220, doi:10.1007/BF02392606, S2CID 123779343.
  15. ↑ Esperet, Louis; Kardoš, František; King, Andrew D.; Kráľ, Daniel; Norine, Serguei (2011), "Exponentially many perfect matchings in cubic graphs", Advances in Mathematics, 227 (4): 1646–1664, arXiv:1012.2878, doi:10.1016/j.aim.2011.03.015, S2CID 4401537.
  16. ↑ Xiao, Mingyu; Nagamochi, Hiroshi (2013), "An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure", Theory and Applications of Models of Computation, Lecture Notes in Computer Science, vol. 7876, Springer-Verlag, pp. 96–107, arXiv:1212.6831, doi:10.1007/978-3-642-38236-9_10, ISBN 978-3-642-38236-9.
  17. ↑ Xiao, Mingyu; Nagamochi, Hiroshi (2012), "An Exact Algorithm for TSP in Degree-3 Graphs Via Circuit Procedure and Amortization on Connectivity Structure", Algorithmica, 74 (2): 713–741, arXiv:1212.6831, Bibcode:2012arXiv1212.6831X, doi:10.1007/s00453-015-9970-4, S2CID 7654681.
  18. ↑ Alimonti, Paola; Kann, Viggo (2000), "Some APX-completeness results for cubic graphs", Theoretical Computer Science, 237 (1–2): 123–134, doi:10.1016/S0304-3975(98)00158-3.
  19. ↑ Hliněný, Petr (2006), "Crossing number is hard for cubic graphs", Journal of Combinatorial Theory, Series B, 96 (4): 455–471, doi:10.1016/j.jctb.2005.09.009.
  20. ↑ Karpinski, Marek; Schmied, Richard (2013), Approximation Hardness of Graphic TSP on Cubic Graphs, arXiv:1304.6800, Bibcode:2013arXiv1304.6800K.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=घन_ग्राफ&oldid=214581’