हैमिल्टनियन पथ: Difference between revisions

Revision as of 17:57, 21 March 2023

छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र

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

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

हैमिल्टन के नाम पर होने के बावजूद, बहुकोणीय आकृति में हैमिल्टनियन चक्रों का एक साल पहले थॉमस किर्कमैन ने भी अध्ययन किया था, जिन्होंने विशेष रूप से, हैमिल्टनियन चक्रों के बिना बहुफलक का उदाहरण दिया था।^[1] इससे पहले भी, शतरंज की बिसात के नाइट के ग्राफ में हैमिल्टनियन चक्र और पथ, नाइट के दौरे का अध्ययन 9वीं शताब्दी में रुद्रता द्वारा भारतीय गणित में किया गया था, और लगभग उसी समय इस्लामिक गणित में अल-अदली अर-रूमी द्वारा किया गया था। 18वीं सदी के यूरोप में नाइट के दौरों को अब्राहम डी मोइवर और लियोनहार्ड यूलर द्वारा प्रकाशित किया गया था।^[2]

परिभाषाएँ

हैमिल्टनियन पथ या अनुरेखणीय पथ एक पथ है जो ग्राफ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन पथ सम्मिलित है, अनुरेखणीय ग्राफ कहलाता है। ग्राफ हैमिल्टनियन-जुड़ा हुआ है यदि शीर्षों के प्रत्येक युग्म के लिए दो शीर्षों के बीच एक हैमिल्टोनीय पथ है।

हैमिल्टनियन चक्र, हैमिल्टनियन परिपथ, शीर्ष दौरा या ग्राफ़ चक्र एक ऐसा चक्र है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन चक्र होता है उसे हैमिल्टनियन ग्राफ कहा जाता है।

इसी तरह की धारणाओं को निर्देशित ग्राफ के लिए परिभाषित किया जा सकता है, जहां पथ या चक्र के प्रत्येक किनारे (चाप) को केवल एक ही दिशा (अर्थात, कोने तीरों से जुड़े होते हैं और किनारों को " पश्चभाग से शीर्ष" का पता लगाया जाता है) में खोजा जा सकता है।

हैमिल्टनियन अपघटन ग्राफ का हैमिल्टनियन परिपथ में एक बढ़त अपघटन है।

हैमिल्टन भूलभुलैया एक प्रकार की तर्क पहेली है जिसमें दिए गए ग्राफ में अद्वितीय हैमिल्टनियन चक्र को खोजने का लक्ष्य है।^[3]^[4]

उदाहरण

Orthographic projections and Schlegel diagrams with Hamiltonian cycles of the vertices of the five platonic solids – only the octahedron has an Eulerian path or cycle, by extending its path with the dotted one

दो से अधिक शीर्षों वाला एक पूर्ण ग्राफ़ हैमिल्टनियन होता है।
प्रत्येक चक्र ग्राफ हैमिल्टनियन है
प्रत्येक टूर्नामेंट में हेमिल्टनियन पथों (रेदेई 1934) की एक विषम संख्या होती है
ग्राफ के रूप में माना जाने वाला प्रत्येक प्लेटोनिक ठोस हैमिल्टनियन है^[5]
परिमित कॉक्सेटर समूह का केली ग्राफ हैमिल्टनियन है (केली ग्राफ में हैमिल्टनियन पथों के बारे में अधिक जानकारी के लिए, लोवाज़ अनुमान देखें।)
चक्रीय क्रमविनिमेयक उपसमूह के साथ निलपोटेंट समूहों पर केली ग्राफ हैमिल्टनियन हैं।^[6]
उत्तल बहुभुज का प्रतिवर्न ग्राफ या समकक्ष, बाइनरी ट्री का घूर्णन ग्राफ हैमिल्टनियन है।^[7]^[8]

गुण

हर्शल ग्राफ सबसे छोटा संभव बहुफलकीय ग्राफ है जिसमें हैमिल्टनियन चक्र नहीं है। एक संभावित हैमिल्टनियन पथ दिखाया गया है।

किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है, जब उसके समापन बिंदु आसन्न हों।

सभी हैमिल्टनियन ग्राफ द्विसंबद्ध हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, पीटरसन ग्राफ देखें)।^[9]

यूलेरियन ग्राफ $G$ (सम्बद्ध ग्राफ जिसमें प्रत्येक शीर्ष की डिग्री समान होती है) में आवश्यक रूप से यूलर दौरा होता है, बंद पथ जो $G$ के प्रत्येक किनारे से ठीक एक बार गुजरता है। यह दौरा लाइन ग्राफ $L (G)$ में हैमिल्टनियन चक्र से मेल खाता है, इसलिए प्रत्येक यूलेरियन ग्राफ का लाइन ग्राफ हैमिल्टनियन है। लाइन ग्राफ़ में अन्य हैमिल्टनियन चक्र हो सकते हैं जो यूलर दौरे के अनुरूप नहीं होते हैं, और विशेष रूप से प्रत्येक हैमिल्टनियन ग्राफ $G$ का रेखा ग्राफ $L (G)$ स्वयं हैमिल्टनियन होता है, भले ही ग्राफ $G$ यूलेरियन है या नहीं।^[10]

टूर्नामेंट (दो से अधिक शीर्षों के साथ) हैमिल्टनियन है यदि और केवल यदि यह दृढ़ता से सम्बद्ध है।

$n$ शीर्षों पर पूर्ण अप्रत्यक्ष ग्राफ़ में विभिन्न हैमिल्टनियन चक्रों की संख्या $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}(n – 1)!/2$ है और $n$ शीर्षों पर एक पूर्ण निर्देशित ग्राफ़ में $(n - 1)!$ है। ये गणनाएं मानती हैं कि चक्र जो अपने प्रारम्भिक बिंदु के अलावा समान हैं हैं, उन्हें अलग से नहीं गिना जाता है।

बॉन्डी-च्वाटल प्रमेय

1972 में बॉन्डी-च्वाटल प्रमेय द्वारा हैमिल्टन के रेखांकन का सबसे अच्छा शीर्ष डिग्री लक्षण वर्णन प्रदान किया गया था, जो जी ए डिराक (1952) और ऑयस्टीन अयस्क द्वारा पहले के परिणामों का सामान्यीकरण करता है। डिराक और ओरे की प्रमेय दोनों को पोसा की प्रमेय (1962) से भी प्राप्त किया जा सकता है। विभिन्न मापदंडों जैसे ग्राफ घनत्व, सुदृढ़ता, निषिद्ध सबग्राफ और अन्य मापदंडों के बीच दूरी के संबंध में हेमिल्टनिसिटी का व्यापक रूप से अध्ययन किया गया है।^[11] डिराक और ओरे की प्रमेय मूल रूप से कहती हैं कि ग्राफ हैमिल्टनियन है यदि उसके पास पर्याप्त किनारे हैं।

बॉन्डी-च्वाटल प्रमेय $n$ शीर्ष के साथ ग्राफ $G$ के समापन $cl(G)$ पर काम करता है, जो बार-बार एक नया किनारा $uv$ जोड़कर प्राप्त किया जाता है जो $u$ और $v$ के गैर-निकटवर्ती युग्म को $deg(v) + deg(u) \geq n$ के साथ जोड़ता है। जब तक कि इस गुण के साथ और युग्म नहीं मिल जाते है।

Bondy–Chvátal Theorem (1976) — A graph is Hamiltonian if and only if its closure is Hamiltonian.

जैसा कि पूर्ण ग्राफ़ हैमिल्टनियन हैं, सभी ग्राफ़ जिनका समापन पूर्ण है, हैमिल्टनियन हैं, जो कि डायराक और अयस्क द्वारा निम्नलिखित पिछले प्रमेयों की सामग्री है।

Dirac's Theorem (1952) — A simple graph with $n$ vertices ( $n\geq 3$ ) is Hamiltonian if every vertex has degree ${\tfrac {n}{2}}$ or greater.

Ore's Theorem (1960) — A simple graph with $n$ vertices ( $n\geq 3$ ) 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 $2n-1$

शीर्षों की संख्या दोगुनी होनी चाहिए क्योंकि प्रत्येक अप्रत्यक्ष किनारा दो निर्देशित चापों से मेल खाता है और इस प्रकार निर्देशित ग्राफ़ में शीर्ष की डिग्री अप्रत्यक्ष ग्राफ़ में डिग्री की दोगुनी होती है।

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.

बाहरी संबंध

[1] 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.

[2] 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.

[3] Ruiter, Johan (2017). Hamilton Mazes – The Beginner's Guide.

[4] Friedman, Erich (2009). "हैमिल्टनियन मेज़". Erich's Puzzle Palace. Archived from the original on 16 April 2016. Retrieved 27 May 2017.

[5] Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957

[6] 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.

[7] 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

[8] 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

[9] Eric Weinstein. "बाइकनेक्टेड ग्राफ". Wolfram MathWorld.

[10] Balakrishnan, R.; Ranganathan, K. (2012), "Corollary 6.5.5", A Textbook of Graph Theory, Springer, p. 134, ISBN 9781461445296.

[11] Gould, Ronald J. (July 8, 2002). "Advances on the Hamiltonian Problem – A Survey" (PDF). Emory University. Retrieved 2012-12-10.

[12] 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.

[13] 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

[14] Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003

[15] Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8

[16] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 1: / Line 1: @@
 {{short description|Path in a graph that visits each vertex exactly once}}
-{{about|the nature of Hamiltonian paths|the question of the existence of a Hamiltonian path or cycle in a given graph|Hamiltonian path problem}}
+{{about|यह लेख हैमिल्टनियन पथों की प्रकृति के बारे में है।|किसी दिए गए ग्राफ में हैमिल्टनियन पथ या चक्र के अस्तित्व के प्रश्न के लिए|हैमिल्टनियन पथ समस्या देखें।}}
-[[File:Hamiltonian.png|thumb|छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, एक हैमिल्टनियन पथ (या पता लगाने योग्य पथ) एक अप्रत्यक्ष या निर्देशित ग्राफ में एक [[पथ (ग्राफ सिद्धांत)]] है जो प्रत्येक शीर्ष (ग्राफ सिद्धांत) पर ठीक एक बार जाता है। एक हैमिल्टनियन चक्र (या हैमिल्टनियन सर्किट) एक [[चक्र (ग्राफ सिद्धांत)]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। एक हैमिल्टनियन पथ जो निकटवर्ती शीर्षों पर शुरू और समाप्त होता है, एक हैमिल्टनियन चक्र बनाने के लिए एक और किनारा जोड़कर पूरा किया जा सकता है, और हैमिल्टनियन चक्र से किसी भी किनारे को हटाने से हैमिल्टनियन पथ उत्पन्न होता है। यह निर्धारित करना कि ऐसे पथ और चक्र ग्राफ़ में मौजूद हैं ([[हैमिल्टनियन पथ समस्या]] और [[हैमिल्टनियन चक्र समस्या]]) एनपी-पूर्ण हैं।
+[[File:Hamiltonian.png|thumb|छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र]][[ग्राफ सिद्धांत|ग्राफ़ सिद्धांत]] के गणितीय क्षेत्र में, हैमिल्टनियन पथ (या अनुरेखणीय पथ) अप्रत्यक्ष या निर्देशित ग्राफ़ में एक [[पथ (ग्राफ सिद्धांत)|पथ]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन चक्र (या हैमिल्टनियन परिपथ) एक ऐसा [[चक्र (ग्राफ सिद्धांत)|चक्र]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन पथ जो निकटवर्ती शीर्षों पर प्रारम्भ और समाप्त होता है, हैमिल्टनियन चक्र बनाने के लिए एक और किनारा जोड़कर पूरा किया जा सकता है, और हैमिल्टनियन चक्र से किसी भी किनारे को हटाने से हैमिल्टनियन पथ का निर्माण होता है। यह निर्धारित करना कि क्या ऐसे पथ और चक्र ग्राफ़ में उपस्थित हैं ([[हैमिल्टनियन पथ समस्या]]  और [[हैमिल्टनियन चक्र समस्या]]) एनपी (NP)-पूर्ण हैं।
-हैमिल्टन के रास्तों और चक्रों का नाम [[विलियम रोवन हैमिल्टन]] के नाम पर रखा गया है, जिन्होंने [[ Icosian खेल ]] का आविष्कार किया था, जिसे अब 'हैमिल्टन की पहेली' के रूप में भी जाना जाता है, जिसमें [[द्वादशफ़लक]] के किनारे के ग्राफ में हैमिल्टनियन चक्र को खोजना शामिल है। हैमिल्टन ने [[आइकोसियन कैलकुलस]] का उपयोग करके इस समस्या को हल किया, एक [[बीजगणितीय संरचना]] जो [[एकता की जड़]] पर आधारित है जिसमें चतुष्कोणों (हैमिल्टन द्वारा आविष्कृत) की कई समानताएँ हैं। यह समाधान मनमाने रेखांकन का सामान्यीकरण नहीं करता है।
+हैमिल्टन के पथों और चक्रों का नाम [[विलियम रोवन हैमिल्टन]] के नाम पर रखा गया है, जिन्होंने [[ Icosian खेल |आइकोसियन गेम]] का आविष्कार किया था, जिसे अब हैमिल्टन की पहेली के रूप में भी जाना जाता है, जिसमें [[द्वादशफ़लक]] के किनारे के ग्राफ में हैमिल्टनियन चक्र को खोजना सम्मिलित है। हैमिल्टन ने [[आइकोसियन कैलकुलस|आइकोसियन गणना]] का उपयोग करके इस समस्या को हल किया, [[बीजगणितीय संरचना]] जो [[एकता की जड़|एकता की जड़ों]] पर आधारित है जिसमें चतुष्कोणों (हैमिल्टन द्वारा आविष्कृत भी) की कई समानताएं हैं। यह समाधान यादृच्छिक रेखांकन के लिए सामान्यीकृत नहीं है।
-हैमिल्टन के नाम पर होने के बावजूद, पॉलीहेड्रा में हैमिल्टनियन चक्रों का एक साल पहले [[थॉमस किर्कमैन]] ने भी अध्ययन किया था, जिन्होंने विशेष रूप से, हैमिल्टनियन चक्रों के बिना पॉलीहेड्रॉन का उदाहरण दिया था।<ref>{{citation
+हैमिल्टन के नाम पर होने के बावजूद, बहुकोणीय आकृति में हैमिल्टनियन चक्रों का एक साल पहले [[थॉमस किर्कमैन]] ने भी अध्ययन किया था, जिन्होंने विशेष रूप से, हैमिल्टनियन चक्रों के बिना बहुफलक का उदाहरण दिया था।<ref>{{citation
   | last = Biggs | first = N. L.
   | doi = 10.1112/blms/13.2.97
@@ Line 14: / Line 14: @@
   | title = T. P. Kirkman, mathematician
   | volume = 13
-  | year = 1981}}.</ref> इससे पहले भी, शतरंज की [[बिसात]] के नाइट के ग्राफ में हैमिल्टनियन चक्र और पथ, नाइट के दौरे का अध्ययन 9वीं शताब्दी में [[रुद्रता]] द्वारा [[भारतीय गणित]] में किया गया था, और लगभग उसी समय [[मध्यकालीन इस्लाम में गणित]] में [[मांसल भुजा]] द्वारा किया गया था। 18वीं सदी के यूरोप में नाइट के दौरों को [[अब्राहम डी मोइवरे]] और [[लियोनहार्ड यूलर]] द्वारा प्रकाशित किया गया था।<ref>{{citation|title=Across the Board: The Mathematics of Chessboard Problems | first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|pages=25–38|chapter=Chapter 2: Knight's Tours | isbn=978-0-691-15498-5}}.</ref>
+  | year = 1981}}.</ref> इससे पहले भी, शतरंज की [[बिसात]] के नाइट के ग्राफ में हैमिल्टनियन चक्र और पथ, नाइट के दौरे का अध्ययन 9वीं शताब्दी में [[रुद्रता]] द्वारा [[भारतीय गणित]] में किया गया था, और लगभग उसी समय [[मध्यकालीन इस्लाम में गणित|इस्लामिक गणित]] में [[मांसल भुजा|अल-अदली अर-रूमी]] द्वारा किया गया था। 18वीं सदी के यूरोप में नाइट के दौरों को [[अब्राहम डी मोइवरे|अब्राहम डी मोइवर]] और [[लियोनहार्ड यूलर]] द्वारा प्रकाशित किया गया था।<ref>{{citation|title=Across the Board: The Mathematics of Chessboard Problems | first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|pages=25–38|chapter=Chapter 2: Knight's Tours | isbn=978-0-691-15498-5}}.</ref>
 == परिभाषाएँ ==
-एक हैमिल्टनियन पथ या पता लगाने योग्य पथ एक पथ (ग्राफ सिद्धांत) है जो ग्राफ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। एक ग्राफ जिसमें एक हैमिल्टनियन पथ होता है, उसे 'ट्रेसेबल ग्राफ' कहा जाता है। एक ग्राफ 'हैमिल्टनियन-कनेक्टेड' है यदि प्रत्येक जोड़ी के लिए दो शीर्षों के बीच एक हैमिल्टनियन पथ है।
+हैमिल्टनियन पथ या अनुरेखणीय पथ एक पथ है जो ग्राफ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन पथ सम्मिलित है, अनुरेखणीय ग्राफ कहलाता है। ग्राफ हैमिल्टनियन-जुड़ा हुआ है यदि शीर्षों के प्रत्येक युग्म के लिए दो शीर्षों के बीच एक हैमिल्टोनीय पथ है।
-एक हैमिल्टनियन चक्र, हैमिल्टनियन सर्किट, वर्टेक्स टूर या ग्राफ़ चक्र एक चक्र (ग्राफ़ सिद्धांत) है जो प्रत्येक शीर्ष पर एक बार जाता है। एक ग्राफ जिसमें हैमिल्टनियन चक्र होता है, उसे 'हैमिल्टनियन ग्राफ' कहा जाता है।
-इसी तरह की धारणाओं को [[निर्देशित ग्राफ]] के लिए परिभाषित किया जा सकता है, जहां पथ या चक्र के प्रत्येक किनारे (चाप) को केवल एक ही दिशा में खोजा जा सकता है (यानी, कोने तीरों से जुड़े हुए हैं और किनारों को पूंछ से सिर का पता लगाया जाता है)।
-एक [[हैमिल्टनियन अपघटन]] एक ग्राफ का हैमिल्टनियन सर्किट में किनारे का अपघटन है।
+हैमिल्टनियन चक्र, हैमिल्टनियन परिपथ, शीर्ष दौरा या ग्राफ़ चक्र एक ऐसा चक्र है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। ग्राफ जिसमें हैमिल्टनियन चक्र होता है उसे हैमिल्टनियन ग्राफ कहा जाता है।
-एक हैमिल्टन भूलभुलैया एक प्रकार की तर्क पहेली है जिसमें लक्ष्य किसी दिए गए ग्राफ में अद्वितीय हैमिल्टनियन चक्र को खोजना है।<ref>{{cite book |last=de Ruiter |first=Johan |date=2017 |title=Hamilton Mazes – The Beginner's Guide}}</ref><ref>{{cite web| url=http://www2.stetson.edu/~efriedma/puzzle/ham/ |title=हैमिल्टनियन मेज़|last=Friedman |first=Erich |date=2009 |website=Erich's Puzzle Palace |access-date=27 May 2017 |url-status=live |archive-url=https://web.archive.org/web/20160416235225/http://www2.stetson.edu/~efriedma/puzzle/ham/ |archive-date=16 April 2016 }}</ref>
+इसी तरह की धारणाओं को [[निर्देशित ग्राफ]] के लिए परिभाषित किया जा सकता है, जहां पथ या चक्र के प्रत्येक किनारे (चाप) को केवल एक ही दिशा (अर्थात, कोने तीरों से जुड़े होते हैं और किनारों को " पश्चभाग से शीर्ष" का पता लगाया जाता है) में खोजा जा सकता है।
+[[हैमिल्टनियन अपघटन]] ग्राफ का हैमिल्टनियन परिपथ में एक बढ़त अपघटन है।
+हैमिल्टन भूलभुलैया एक प्रकार की तर्क पहेली है जिसमें दिए गए ग्राफ में अद्वितीय हैमिल्टनियन चक्र को खोजने का लक्ष्य है।<ref>{{cite book |last=de Ruiter |first=Johan |date=2017 |title=Hamilton Mazes – The Beginner's Guide}}</ref><ref>{{cite web| url=http://www2.stetson.edu/~efriedma/puzzle/ham/ |title=हैमिल्टनियन मेज़|last=Friedman |first=Erich |date=2009 |website=Erich's Puzzle Palace |access-date=27 May 2017 |url-status=live |archive-url=https://web.archive.org/web/20160416235225/http://www2.stetson.edu/~efriedma/puzzle/ham/ |archive-date=16 April 2016 }}</ref>
 == उदाहरण ==
 {{Hamiltonian platonic graphs.svg}}
-* दो से अधिक शीर्षों वाला एक पूर्ण ग्राफ़ हैमिल्टनियन होता है
+* दो से अधिक शीर्षों वाला एक पूर्ण ग्राफ़ हैमिल्टनियन होता है।
-* हर चक्र का ग्राफ हैमिल्टनियन है
+* प्रत्येक चक्र ग्राफ हैमिल्टनियन है
-* हर [[ टूर्नामेंट (ग्राफ सिद्धांत) ]] में हेमिल्टनियन रास्तों की एक विषम संख्या होती है (लेस्ज़्लो रेडी|रेदेई 1934)
+* प्रत्येक [[ टूर्नामेंट (ग्राफ सिद्धांत) |टूर्नामेंट]] में हेमिल्टनियन पथों (रेदेई 1934) की एक विषम संख्या होती है
-* प्रत्येक [[प्लेटोनिक ठोस]], जिसे ग्राफ माना जाता है, हैमिल्टनियन है<ref>[http://www.scientificamerican.com/magazine/sa/1957/05-01/ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957]
+*ग्राफ के रूप में माना जाने वाला प्रत्येक [[प्लेटोनिक ठोस]] हैमिल्टनियन है<ref>[http://www.scientificamerican.com/magazine/sa/1957/05-01/ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150–156, May 1957]
 </ref>
-* एक परिमित [[कॉक्सेटर समूह]] का [[केली ग्राफ]] हैमिल्टनियन है (केली ग्राफ में हैमिल्टनियन पथों के बारे में अधिक जानकारी के लिए, लोवाज़ अनुमान देखें।)
+*परिमित [[कॉक्सेटर समूह]] का केली ग्राफ हैमिल्टनियन है ([[केली ग्राफ]] में हैमिल्टनियन पथों के बारे में अधिक जानकारी के लिए, लोवाज़ अनुमान देखें।)
-* चक्रीय [[कम्यूटेटर उपसमूह]] के साथ [[निलपोटेंट समूह]]ों पर केली ग्राफ हैमिल्टनियन हैं।<ref>{{Cite journal| last1=Ghaderpour|first1=E.|last2=Morris|first2=D. W.|date=2014|title=चक्रीय कम्यूटेटर उपसमूह के साथ निलपोटेंट समूहों पर केली ग्राफ हैमिल्टनियन हैं|journal=Ars Mathematica Contemporanea|language=en|volume=7|issue=1|pages=55–72| doi=10.26493/1855-3974.280.8d3| arxiv=1111.6216|s2cid=57575227 }}</ref>
+* चक्रीय [[कम्यूटेटर उपसमूह|क्रमविनिमेयक उपसमूह]] के साथ [[निलपोटेंट समूह|निलपोटेंट समूहों]] पर केली ग्राफ हैमिल्टनियन हैं।<ref>{{Cite journal| last1=Ghaderpour|first1=E.|last2=Morris|first2=D. W.|date=2014|title=चक्रीय कम्यूटेटर उपसमूह के साथ निलपोटेंट समूहों पर केली ग्राफ हैमिल्टनियन हैं|journal=Ars Mathematica Contemporanea|language=en|volume=7|issue=1|pages=55–72| doi=10.26493/1855-3974.280.8d3| arxiv=1111.6216|s2cid=57575227 }}</ref>
-* एक उत्तल बहुभुज का [[फ्लिप ग्राफ]] या समकक्ष, [[बाइनरी ट्री]] का [[ पेड़ का घूमना ]], हैमिल्टनियन है।<ref>{{citation
+*उत्तल बहुभुज का [[फ्लिप ग्राफ|प्रतिवर्न ग्राफ]] या समकक्ष, [[बाइनरी ट्री]] का [[ पेड़ का घूमना |घूर्णन ग्राफ]] हैमिल्टनियन है।<ref>{{citation
   | last = Lucas | first = Joan M.
   | doi = 10.1016/0196-6774(87)90048-4
@@ Line 56: / Line 52: @@
   | volume = 13
   | year = 1999}}</ref>
+== गुण ==
+[[Image:Herschel Hamiltonian path.svg|thumb|[[हर्शल ग्राफ]] सबसे छोटा संभव [[ बहुफलकीय ग्राफ ]] है जिसमें हैमिल्टनियन चक्र नहीं है। एक संभावित हैमिल्टनियन पथ दिखाया गया है।]]किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है, जब उसके समापन बिंदु आसन्न हों।
+सभी हैमिल्टनियन ग्राफ [[द्विसंबद्ध ग्राफ|द्विसंबद्ध]] हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, [[पीटरसन ग्राफ]] देखें)।<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=बाइकनेक्टेड ग्राफ|author=Eric Weinstein|publisher=Wolfram MathWorld}}</ref>
-== गुण ==
+[[यूलेरियन ग्राफ]] {{mvar|G}} ([[जुड़ा हुआ ग्राफ|सम्बद्ध ग्राफ]] जिसमें प्रत्येक शीर्ष की डिग्री समान होती है) में आवश्यक रूप से यूलर दौरा होता है, बंद पथ जो {{mvar|G}} के प्रत्येक किनारे से ठीक एक बार गुजरता है। यह दौरा [[लाइन ग्राफ]] {{math|''L''(''G'')}} में हैमिल्टनियन चक्र से मेल खाता है, इसलिए प्रत्येक यूलेरियन ग्राफ का लाइन ग्राफ हैमिल्टनियन है। लाइन ग्राफ़ में अन्य हैमिल्टनियन चक्र हो सकते हैं जो यूलर दौरे के अनुरूप नहीं होते हैं, और विशेष रूप से प्रत्येक हैमिल्टनियन ग्राफ {{mvar|G}} का रेखा ग्राफ {{math|''L''(''G'')}} स्वयं हैमिल्टनियन होता है, भले ही ग्राफ {{mvar|G}} यूलेरियन है या नहीं।<ref>{{citation|title=A Textbook of Graph Theory| first1=R.|last1=Balakrishnan| first2=K.|last2=Ranganathan| publisher=Springer| year=2012| isbn=9781461445296| contribution=Corollary 6.5.5|page=134|url=https://books.google.com/books?id=mpgu6wgnZgYC&pg=PA134}}.</ref>
-[[Image:Herschel Hamiltonian path.svg|thumb|[[हर्शल ग्राफ]] सबसे छोटा संभव [[ बहुफलकीय ग्राफ ]] है जिसमें हैमिल्टनियन चक्र नहीं है। एक संभावित हैमिल्टनियन पथ दिखाया गया है।]]किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है जब उसके अंत बिंदु आसन्न हों।
-सभी हैमिल्टनियन ग्राफ़ [[द्विसंबद्ध ग्राफ]]़ हैं, लेकिन एक द्विसंबद्ध ग्राफ़ हैमिल्टनियन नहीं होना चाहिए (उदाहरण के लिए, [[पीटरसन ग्राफ]]़ देखें)।<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=बाइकनेक्टेड ग्राफ|author=Eric Weinstein|publisher=Wolfram MathWorld}}</ref>
+टूर्नामेंट (दो से अधिक शीर्षों के साथ) हैमिल्टनियन है यदि और केवल यदि यह दृढ़ता से सम्बद्ध है।
-एक [[यूलेरियन ग्राफ]] {{mvar|G}} (एक [[जुड़ा हुआ ग्राफ]] जिसमें हर शीर्ष की डिग्री समान है) में आवश्यक रूप से एक यूलर दौरा होता है, जिसके प्रत्येक किनारे से गुजरने वाला एक बंद मार्ग होता है {{mvar|G}} ठीक एक बार। यह दौरा [[लाइन ग्राफ]]़ में हैमिल्टनियन चक्र से मेल खाता है {{math|''L''(''G'')}}, इसलिए प्रत्येक ऑयलरीय ग्राफ का रेखा आलेख हैमिल्टोनीय है। लाइन ग्राफ़ में अन्य हैमिल्टनियन चक्र हो सकते हैं जो यूलर टूर और विशेष रूप से लाइन ग्राफ़ के अनुरूप नहीं हैं {{math|''L''(''G'')}} हर हैमिल्टनियन ग्राफ का {{mvar|G}} खुद हैमिल्टनियन है, चाहे ग्राफ कुछ भी हो {{mvar|G}} ऑयलरीय है।<ref>{{citation|title=A Textbook of Graph Theory| first1=R.|last1=Balakrishnan| first2=K.|last2=Ranganathan| publisher=Springer| year=2012| isbn=9781461445296| contribution=Corollary 6.5.5|page=134|url=https://books.google.com/books?id=mpgu6wgnZgYC&pg=PA134}}.</ref>
-एक टूर्नामेंट (ग्राफ थ्योरी) (दो से अधिक सिरों के साथ) हैमिल्टनियन है अगर और केवल अगर यह मजबूत रूप से जुड़ा हुआ घटक है।
-पर एक पूर्ण अप्रत्यक्ष ग्राफ में विभिन्न हैमिल्टनियन चक्रों की संख्या {{mvar|n}} शिखर है {{math|{{sfrac|(''n'' – 1)!|2}}}} और एक पूर्ण निर्देशित ग्राफ में {{mvar|n}} शिखर है {{math|(''n'' – 1)!}}. ये गणनाएं मानती हैं कि चक्र जो अपने शुरुआती बिंदु के अलावा समान हैं, उन्हें अलग से नहीं गिना जाता है।
+{{mvar|n}} शीर्षों पर पूर्ण अप्रत्यक्ष ग्राफ़ में विभिन्न हैमिल्टनियन चक्रों की संख्या {{math|{{sfrac|(''n'' – 1)!|2}}}} है और {{mvar|n}} शीर्षों पर एक पूर्ण निर्देशित ग्राफ़ में {{math|(''n'' – 1)!}} है। ये गणनाएं मानती हैं कि चक्र जो अपने प्रारम्भिक बिंदु के अलावा समान हैं हैं, उन्हें अलग से नहीं गिना जाता है।
 == बॉन्डी-च्वाटल प्रमेय ==
-हेमिल्टनियन रेखांकन का सर्वश्रेष्ठ वर्टेक्स डिग्री (ग्राफ़ सिद्धांत) लक्षण वर्णन 1972 में जे.ए. बॉन्डी-वैक्लेव च्वाटल|च्वाटल प्रमेय द्वारा प्रदान किया गया था, जो गेब्रियल एंड्रयू डिराक|जी द्वारा पहले के परिणामों का सामान्यीकरण करता है। ए. डिराक (1952) और आइस्टीन ओर। डायराक और ओरे के दोनों प्रमेय भी पोसा प्रमेय|पोसा प्रमेय (1962) से प्राप्त किए जा सकते हैं। हेमिल्टनिसिटी का व्यापक रूप से विभिन्न मापदंडों जैसे ग्राफ [[ घना ग्राफ ]], [[ग्राफ क्रूरता]], [[निषिद्ध सबग्राफ समस्या]] और [[ दूरी (ग्राफ सिद्धांत) ]] जैसे अन्य मापदंडों के संबंध में अध्ययन किया गया है।<ref>{{Cite web|url = http://www.mathcs.emory.edu/~rg/advances.pdf|title = Advances on the Hamiltonian Problem – A Survey|date = July 8, 2002|access-date = 2012-12-10|publisher = Emory University|last = Gould|first = Ronald J.}}</ref> डिराक और अयस्क के प्रमेय मूल रूप से कहते हैं कि एक ग्राफ हैमिल्टनियन है यदि इसमें पर्याप्त किनार हैं।
+में बॉन्डी-च्वाटल प्रमेय द्वारा हैमिल्टन के रेखांकन का सबसे अच्छा शीर्ष डिग्री लक्षण वर्णन प्रदान किया गया था, जो जी ए डिराक (1952) और ऑयस्टीन अयस्क द्वारा पहले के परिणामों का सामान्यीकरण करता है। डिराक और ओरे की प्रमेय दोनों को पोसा की प्रमेय (1962) से भी प्राप्त किया जा सकता है। विभिन्न मापदंडों जैसे [[ घना ग्राफ |ग्राफ घनत्व]], [[ग्राफ क्रूरता|सुदृढ़ता]], [[निषिद्ध सबग्राफ समस्या|निषिद्ध सबग्राफ]] और अन्य मापदंडों के बीच [[ दूरी (ग्राफ सिद्धांत) |दूरी]] के संबंध में हेमिल्टनिसिटी का व्यापक रूप से अध्ययन किया गया है।<ref>{{Cite web|url = http://www.mathcs.emory.edu/~rg/advances.pdf|title = Advances on the Hamiltonian Problem – A Survey|date = July 8, 2002|access-date = 2012-12-10|publisher = Emory University|last = Gould|first = Ronald J.}}</ref> डिराक और ओरे की प्रमेय मूल रूप से कहती हैं कि ग्राफ हैमिल्टनियन है यदि उसके पास पर्याप्त किनारे हैं।
-बॉन्डी-च्वाटल प्रमेय 'क्लोजर' पर काम करता है {{math|cl(''G'')}} ग्राफ का {{math|''G''}} साथ {{mvar|n}} वर्टिकल, जो बार-बार एक नया किनारा जोड़कर प्राप्त किया जाता है {{math|''uv''}} किसी [[असन्निकट]] युग्म को जोड़ना {{math|''u''}} और {{math|''v''}} साथ {{math|deg(''v'') + deg(''u'') ≥ ''n''}} जब तक कि इस संपत्ति के साथ और जोड़े नहीं मिल सकते।
+बॉन्डी-च्वाटल प्रमेय {{mvar|n}} शीर्ष के साथ ग्राफ {{math|''G''}} के समापन {{math|cl(''G'')}} पर काम करता है, जो बार-बार एक नया किनारा {{math|''uv''}} जोड़कर प्राप्त किया जाता है जो {{math|''u''}} और {{math|''v''}} के गैर-[[असन्निकट|निकटवर्ती]] युग्म को {{math|deg(''v'') + deg(''u'') ≥ ''n''}} के साथ जोड़ता है। जब तक कि इस गुण के साथ और युग्म नहीं मिल जाते है।
 {{math theorem | name = Bondy–Chvátal Theorem (1976) | math_statement = A graph is Hamiltonian if and only if its closure is Hamiltonian.}}

Anonymous

Search

हैमिल्टनियन पथ: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:57, 21 March 2023

Contents

परिभाषाएँ

उदाहरण

गुण

बॉन्डी-च्वाटल प्रमेय

प्लेनर ग्राफ में हैमिल्टनियन चक्रों का अस्तित्व

हैमिल्टनियन चक्र बहुपद

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

हैमिल्टनियन पथ: Difference between revisions

Revision as of 17:57, 21 March 2023

परिभाषाएँ

उदाहरण

गुण

बॉन्डी-च्वाटल प्रमेय

प्लेनर ग्राफ में हैमिल्टनियन चक्रों का अस्तित्व

हैमिल्टनियन चक्र बहुपद

यह भी देखें

टिप्पणियाँ

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories