हैमिल्टनियन पथ
ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, हैमिल्टनियन पथ (या अनुरेखणीय पथ) अप्रत्यक्ष या निर्देशित ग्राफ़ में एक पथ है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन चक्र (या हैमिल्टनियन परिपथ) एक ऐसा चक्र है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन पथ जो निकटवर्ती शीर्षों पर प्रारम्भ और समाप्त होता है, हैमिल्टनियन चक्र बनाने के लिए एक और किनारा जोड़कर पूरा किया जा सकता है, और हैमिल्टनियन चक्र से किसी भी किनारे को हटाने से हैमिल्टनियन पथ का निर्माण होता है। यह निर्धारित करना कि क्या ऐसे पथ और चक्र ग्राफ़ में उपस्थित हैं (हैमिल्टनियन पथ समस्या और हैमिल्टनियन चक्र समस्या) एनपी (NP)-पूर्ण हैं।
हैमिल्टन के पथों और चक्रों का नाम विलियम रोवन हैमिल्टन के नाम पर रखा गया है, जिन्होंने आइकोसियन गेम का आविष्कार किया था, जिसे अब हैमिल्टन की पहेली के रूप में भी जाना जाता है, जिसमें द्वादशफ़लक के किनारे के ग्राफ में हैमिल्टनियन चक्र को खोजना सम्मिलित है। हैमिल्टन ने आइकोसियन गणना का उपयोग करके इस समस्या को हल किया, बीजगणितीय संरचना जो एकता की जड़ों पर आधारित है जिसमें चतुष्कोणों (हैमिल्टन द्वारा आविष्कृत भी) की कई समानताएं हैं। यह समाधान यादृच्छिक रेखांकन के लिए सामान्यीकृत नहीं है।
हैमिल्टन के नाम पर होने के बावजूद, बहुकोणीय आकृति में हैमिल्टनियन चक्रों का एक साल पहले थॉमस किर्कमैन ने भी अध्ययन किया था, जिन्होंने विशेष रूप से, हैमिल्टनियन चक्रों के बिना बहुफलक का उदाहरण दिया था।[1] इससे पहले भी, शतरंज की बिसात के नाइट के ग्राफ में हैमिल्टनियन चक्र और पथ, नाइट के दौरे का अध्ययन 9वीं शताब्दी में रुद्रता द्वारा भारतीय गणित में किया गया था, और लगभग उसी समय इस्लामिक गणित में अल-अदली अर-रूमी द्वारा किया गया था। 18वीं सदी के यूरोप में नाइट के दौरों को अब्राहम डी मोइवर और लियोनहार्ड यूलर द्वारा प्रकाशित किया गया था।[2]
परिभाषाएँ
हैमिल्टनियन पथ या अनुरेखणीय पथ एक पथ है जो ग्राफ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन पथ सम्मिलित है, अनुरेखणीय ग्राफ कहलाता है। ग्राफ हैमिल्टनियन-जुड़ा हुआ है यदि शीर्षों के प्रत्येक युग्म के लिए दो शीर्षों के बीच एक हैमिल्टोनीय पथ है।
हैमिल्टनियन चक्र, हैमिल्टनियन परिपथ, शीर्ष दौरा या ग्राफ़ चक्र एक ऐसा चक्र है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन चक्र होता है उसे हैमिल्टनियन ग्राफ कहा जाता है।
इसी तरह की धारणाओं को निर्देशित ग्राफ के लिए परिभाषित किया जा सकता है, जहां पथ या चक्र के प्रत्येक किनारे (चाप) को केवल एक ही दिशा (अर्थात, कोने तीरों से जुड़े होते हैं और किनारों को " पश्चभाग से शीर्ष" का पता लगाया जाता है) में खोजा जा सकता है।
हैमिल्टनियन अपघटन ग्राफ का हैमिल्टनियन परिपथ में एक बढ़त अपघटन है।
हैमिल्टन भूलभुलैया एक प्रकार की तर्क पहेली है जिसमें दिए गए ग्राफ में अद्वितीय हैमिल्टनियन चक्र को खोजने का लक्ष्य है।[3][4]
उदाहरण
- दो से अधिक शीर्षों वाला एक पूर्ण ग्राफ़ हैमिल्टनियन होता है।
- प्रत्येक चक्र ग्राफ हैमिल्टनियन है
- प्रत्येक टूर्नामेंट में हेमिल्टनियन पथों (रेदेई 1934) की एक विषम संख्या होती है
- ग्राफ के रूप में माना जाने वाला प्रत्येक प्लेटोनिक ठोस हैमिल्टनियन है[5]
- परिमित कॉक्सेटर समूह का केली ग्राफ हैमिल्टनियन है (केली ग्राफ में हैमिल्टनियन पथों के बारे में अधिक जानकारी के लिए, लोवाज़ अनुमान देखें।)
- चक्रीय क्रमविनिमेयक उपसमूह के साथ निलपोटेंट समूहों पर केली ग्राफ हैमिल्टनियन हैं।[6]
- उत्तल बहुभुज का प्रतिवर्न ग्राफ या समकक्ष, बाइनरी ट्री का घूर्णन ग्राफ हैमिल्टनियन है।[7][8]
गुण
किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है, जब उसके समापन बिंदु आसन्न हों।
सभी हैमिल्टनियन ग्राफ द्विसंबद्ध हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, पीटरसन ग्राफ देखें)।[9]
यूलेरियन ग्राफ G (सम्बद्ध ग्राफ जिसमें प्रत्येक शीर्ष की डिग्री समान होती है) में आवश्यक रूप से यूलर दौरा होता है, बंद पथ जो G के प्रत्येक किनारे से ठीक एक बार गुजरता है। यह दौरा लाइन ग्राफ L(G) में हैमिल्टनियन चक्र से मेल खाता है, इसलिए प्रत्येक यूलेरियन ग्राफ का लाइन ग्राफ हैमिल्टनियन है। लाइन ग्राफ़ में अन्य हैमिल्टनियन चक्र हो सकते हैं जो यूलर दौरे के अनुरूप नहीं होते हैं, और विशेष रूप से प्रत्येक हैमिल्टनियन ग्राफ G का रेखा ग्राफ L(G) स्वयं हैमिल्टनियन होता है, भले ही ग्राफ G यूलेरियन है या नहीं।[10]
टूर्नामेंट (दो से अधिक शीर्षों के साथ) हैमिल्टनियन है यदि और केवल यदि यह दृढ़ता से सम्बद्ध है।
n शीर्षों पर पूर्ण अप्रत्यक्ष ग्राफ़ में विभिन्न हैमिल्टनियन चक्रों की संख्या (n – 1)!/2 है और n शीर्षों पर एक पूर्ण निर्देशित ग्राफ़ में (n – 1)! है। ये गणनाएं मानती हैं कि चक्र जो अपने प्रारम्भिक बिंदु के अलावा समान हैं हैं, उन्हें अलग से नहीं गिना जाता है।
बॉन्डी-च्वाटल प्रमेय
1972 में बॉन्डी-च्वाटल प्रमेय द्वारा हैमिल्टन के रेखांकन का सबसे अच्छा शीर्ष डिग्री लक्षण वर्णन प्रदान किया गया था, जो जी ए डिराक (1952) और ऑयस्टीन अयस्क द्वारा पहले के परिणामों का सामान्यीकरण करता है। डिराक और ओरे की प्रमेय दोनों को पोसा की प्रमेय (1962) से भी प्राप्त किया जा सकता है। विभिन्न मापदंडों जैसे ग्राफ घनत्व, सुदृढ़ता, निषिद्ध सबग्राफ और अन्य मापदंडों के बीच दूरी के संबंध में हेमिल्टनिसिटी का व्यापक रूप से अध्ययन किया गया है।[11] डिराक और ओरे की प्रमेय मूल रूप से कहती हैं कि ग्राफ हैमिल्टनियन है यदि उसके पास पर्याप्त किनारे हैं।
बॉन्डी-च्वाटल प्रमेय n शीर्ष के साथ ग्राफ G के समापन cl(G) पर काम करता है, जो बार-बार एक नया किनारा uv जोड़कर प्राप्त किया जाता है जो u और v के गैर-निकटवर्ती युग्म को deg(v) + deg(u) ≥ n के साथ जोड़ता है। जब तक कि इस गुण के साथ और युग्म नहीं मिल जाते है।
बॉन्डी-च्वाटल प्रमेय (1976) — एक ग्राफ हैमिल्टनियन है यदि और केवल अगर इसका समापन हैमिल्टनियन है।
जैसा कि पूर्ण ग्राफ़ हैमिल्टनियन हैं, सभी ग्राफ़ जिनका समापन पूर्ण है, हैमिल्टनियन हैं, जो कि डिराक और ओरे द्वारा निम्नलिखित पहले के प्रमेय की सामग्री है।
Dirac's Theorem (1952) — A simple graph with n vertices () is Hamiltonian if every vertex has degree or greater.
Ore's Theorem (1960) — A simple graph with n vertices () is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater.
निम्नलिखित प्रमेयों को निर्देशित संस्करणों के रूप में माना जा सकता है:
Ghouila–Houiri (1960) — A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n.
Meyniel (1973) — A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to
शीर्षों की संख्या दोगुनी होनी चाहिए क्योंकि प्रत्येक अप्रत्यक्ष किनारा दो निर्देशित चापों से मेल खाता है और इस प्रकार निर्देशित ग्राफ़ में शीर्ष की डिग्री अप्रत्यक्ष ग्राफ़ में डिग्री की दोगुनी होती है।
Rahman–Kaykobad (2005) — A simple graph with n vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than n.[12]
उपरोक्त प्रमेय केवल हैमिल्टनियन पथ के एक ग्राफ में अस्तित्व को पहचान सकता है और हैमिल्टनियन चक्र को नहीं।
इनमें से कई परिणामों में संतुलित द्विदलीय रेखांकन के अनुरूप हैं, जिसमें शीर्ष डिग्री की तुलना पूरे ग्राफ में शीर्षों की संख्या के बजाय द्विदलीय के एक तरफ के शीर्षों की संख्या से की जाती है।[13]
प्लेनर ग्राफ में हैमिल्टनियन चक्रों का अस्तित्व
Theorem — A 4-connected planar triangulation has a Hamiltonian cycle.[14]
Theorem — A 4-connected planar graph has a Hamiltonian cycle.[15]
हैमिल्टनियन चक्र बहुपद
दिए गए भारित डिग्राफ के हैमिल्टनियन चक्रों का एक बीजगणितीय प्रतिनिधित्व (जिनके चापों को एक निश्चित जमीनी क्षेत्र से वजन सौंपा गया है) हैमिल्टनियन चक्र बहुपद है, इसके भारित आसन्न मैट्रिक्स को डिग्राफ के हैमिल्टनियन चक्रों के चाप भार के उत्पादों के योग के रूप में परिभाषित किया गया है। . चाप भार में एक फ़ंक्शन के रूप में यह बहुपद समान रूप से शून्य नहीं है यदि और केवल यदि डिग्राफ हैमिल्टनियन है। इसकी गणना करने की कम्प्यूटेशनल जटिलताओं और स्थायी कंप्यूटिंग के बीच संबंध ग्रिगोरी कोगन द्वारा दिखाया गया था।[16]
यह भी देखें
- बार्नेट का अनुमान, घन द्विदलीय ग्राफ पॉलीहेड्रल ग्राफ की हैमिल्टनसिटी पर एक खुली समस्या
- यूलेरियन पथ, एक ग्राफ में सभी किनारों के माध्यम से पथ
- फ़्लिशनर की प्रमेय, ग्राफ की हैमिल्टनियन शक्ति पर
- ग्रे कोड
- ग्रिनबर्ग का प्रमेय एक हैमिल्टनियन चक्र होने के लिए प्लेनर ग्राफ ़ के लिए एक आवश्यक शर्त देता है
- हैमिल्टनियन पथ समस्या, हैमिल्टनियन पथ खोजने की कम्प्यूटेशनल समस्या
- हाइपोसुभामिल्टोनियन ग्राफ, एक गैर-हैमिल्टनियन ग्राफ जिसमें प्रत्येक शीर्ष-हटाए गए सबग्राफ हैमिल्टनियन हैं
- नाइट का दौरा, नाइट के ग्राफ में हैमिल्टनियन चक्र
- हैमिल्टनियन क्यूबिक ग्राफ के लिए एलसीएफ संकेतन ।
- लोवाज़ का अनुमान है कि शीर्ष-सकर्मक ग्राफ हैमिल्टनियन हैं
- पैनसाइक्लिक ग्राफ, हैमिल्टनियन चक्र सहित सभी लंबाई के चक्रों के साथ ग्राफ
- कोनिग्सबर्ग के सात पुल
- लघुता प्रतिपादक, एक परिवार में ग्राफ हैमिल्टनियन से कितनी दूर हो सकता है इसका एक संख्यात्मक माप
- सांप-इन-द-बॉक्स, हाइपरक्यूब में सबसे लंबा प्रेरित पथ
- स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम एक permutohedron में हैमिल्टनियन पथ खोजने के लिए
- Subhamiltonian ग्राफ, एक प्लानर ग्राफ हैमिल्टनियन ग्राफ का एक सबग्राफ
- टैट का अनुमान (अब झूठा है) कि 3-नियमित बहुफलकीय रेखांकन हैमिल्टनियन हैं
- ट्रैवलिंग सेल्समैन की समस्या
टिप्पणियाँ
- ↑ Biggs, N. L. (1981), "T. P. Kirkman, mathematician", The Bulletin of the London Mathematical Society, 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 0608093.
- ↑ Watkins, John J. (2004), "Chapter 2: Knight's Tours", Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, pp. 25–38, ISBN 978-0-691-15498-5.
- ↑ de Ruiter, Johan (2017). Hamilton Mazes – The Beginner's Guide.
- ↑ Friedman, Erich (2009). "हैमिल्टनियन मेज़". Erich's Puzzle Palace. Archived from the original on 16 April 2016. Retrieved 27 May 2017.
- ↑ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957
- ↑ Ghaderpour, E.; Morris, D. W. (2014). "चक्रीय कम्यूटेटर उपसमूह के साथ निलपोटेंट समूहों पर केली ग्राफ हैमिल्टनियन हैं". Ars Mathematica Contemporanea (in English). 7 (1): 55–72. arXiv:1111.6216. doi:10.26493/1855-3974.280.8d3. S2CID 57575227.
- ↑ Lucas, Joan M. (1987), "The rotation graph of binary trees is Hamiltonian", Journal of Algorithms, 8 (4): 503–535, doi:10.1016/0196-6774(87)90048-4
- ↑ Hurtado, Ferran; Noy, Marc (1999), "Graph of triangulations of a convex polygon and tree of triangulations", Computational Geometry, 13 (3): 179–188, doi:10.1016/S0925-7721(99)00016-4
- ↑ Eric Weinstein. "बाइकनेक्टेड ग्राफ". Wolfram MathWorld.
- ↑ Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296.
- ↑ Gould, Ronald J. (July 8, 2002). "Advances on the Hamiltonian Problem – A Survey" (PDF). Emory University. Retrieved 2012-12-10.
- ↑ Rahman, M. S.; Kaykobad, M. (April 2005). "On Hamiltonian cycles and Hamiltonian paths". Information Processing Letters. 94: 37–41. doi:10.1016/j.ipl.2004.12.002.
- ↑ Moon, J.; Moser, L. (1963), "On Hamiltonian bipartite graphs", Israel Journal of Mathematics, 1 (3): 163–165, doi:10.1007/BF02759704, MR 0161332, S2CID 119358798
- ↑ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003
- ↑ Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8
- ↑ Kogan, Grigoriy (1996), "Computing permanents over fields of characteristic 3: where and why it becomes difficult", 37th Annual Symposium on Foundations of Computer Science (FOCS '96): 108–114, doi:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2, S2CID 39024286
संदर्भ
- Berge, Claude; Ghouila-Houiri, A. (1962), Programming, games and transportation networks, New York: Sons, Inc.
- DeLeon, Melissa (2000), "A study of sufficient conditions for Hamiltonian cycles" (PDF), Rose-Hulman Undergraduate Math Journal, 1 (1), archived from the original (PDF) on 2012-12-22, retrieved 2005-11-28.
- Dirac, G. A. (1952), "Some theorems on abstract graphs", Proceedings of the London Mathematical Society, 3rd Ser., 2: 69–81, doi:10.1112/plms/s3-2.1.69, MR 0047308.
- Hamilton, William Rowan (1856), "Memorandum respecting a new system of roots of unity", Philosophical Magazine, 12: 446.
- Hamilton, William Rowan (1858), "Account of the Icosian Calculus", Proceedings of the Royal Irish Academy, 6: 415–416.
- Meyniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté", Journal of Combinatorial Theory, Series B, 14 (2): 137–147, doi:10.1016/0095-8956(73)90057-9, MR 0317997.
- Ore, Øystein (1960), "Note on Hamilton circuits", The American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928, MR 0118683.
- Pósa, L. (1962), "A theorem concerning Hamilton lines", Magyar Tud. Akad. Mat. Kutató Int. Közl., 7: 225–226, MR 0184876.
