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

From Vigyanwiki
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{short description|Path in a graph that visits each vertex exactly once}}
{{short description|Path in a graph that visits each vertex exactly once}}
{{about|यह लेख हैमिल्टनियन पथों की प्रकृति के बारे में है।|किसी दिए गए ग्राफ में हैमिल्टनियन पथ या चक्र के अस्तित्व के प्रश्न के लिए|हैमिल्टनियन पथ समस्या देखें।}}
{{about|यह लेख हैमिल्टनियन पथों की प्रकृति के बारे में है।|किसी दिए गए ग्राफ में हैमिल्टनियन पथ या चक्र के अस्तित्व के प्रश्न के लिए|हैमिल्टनियन पथ समस्या देखें।}}
[[File:Hamiltonian.png|thumb|छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र]][[ग्राफ सिद्धांत|ग्राफ़ सिद्धांत]] के गणितीय क्षेत्र में, हैमिल्टनियन पथ (या अनुरेखणीय पथ) अप्रत्यक्ष या निर्देशित ग्राफ़ में एक [[पथ (ग्राफ सिद्धांत)|पथ]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन चक्र (या हैमिल्टनियन परिपथ) एक ऐसा [[चक्र (ग्राफ सिद्धांत)|चक्र]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन पथ जो निकटवर्ती शीर्षों पर प्रारम्भ और समाप्त होता है, हैमिल्टनियन चक्र बनाने के लिए एक और किनारा जोड़कर पूरा किया जा सकता है, और हैमिल्टनियन चक्र से किसी भी किनारे को हटाने से हैमिल्टनियन पथ का निर्माण होता है। यह निर्धारित करना कि क्या ऐसे पथ और चक्र ग्राफ़ में उपस्थित हैं ([[हैमिल्टनियन पथ समस्या]]  और [[हैमिल्टनियन चक्र समस्या]]) एनपी (NP)-पूर्ण हैं।  
[[File:Hamiltonian.png|thumb|छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र]][[ग्राफ सिद्धांत|ग्राफ़ सिद्धांत]] के गणितीय क्षेत्र में, '''हैमिल्टनियन पथ''' (या अनुरेखणीय पथ) अप्रत्यक्ष या निर्देशित ग्राफ़ में एक [[पथ (ग्राफ सिद्धांत)|पथ]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन चक्र (या हैमिल्टनियन परिपथ) एक ऐसा [[चक्र (ग्राफ सिद्धांत)|चक्र]] है जो प्रत्येक शीर्ष पर ठीक एक बार जाता है। हैमिल्टनियन पथ जो निकटवर्ती शीर्षों पर प्रारम्भ और समाप्त होता है, हैमिल्टनियन चक्र बनाने के लिए एक और किनारा जोड़कर पूरा किया जा सकता है, और हैमिल्टनियन चक्र से किसी भी किनारे को हटाने से हैमिल्टनियन पथ का निर्माण होता है। यह निर्धारित करना कि क्या ऐसे पथ और चक्र ग्राफ़ में उपस्थित हैं ([[हैमिल्टनियन पथ समस्या]]  और [[हैमिल्टनियन चक्र समस्या]]) एनपी (NP)-पूर्ण हैं।  


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


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


[[हैमिल्टनियन अपघटन]] ग्राफ का हैमिल्टनियन परिपथ में एक बढ़त अपघटन है।  
[[हैमिल्टनियन अपघटन]] ग्राफ का हैमिल्टनियन परिपथ में एक बढ़त अपघटन है।  
Line 53: Line 53:
  | year = 1999}}</ref>
  | year = 1999}}</ref>
== गुण ==
== गुण ==
[[Image:Herschel Hamiltonian path.svg|thumb|[[हर्शल ग्राफ]] सबसे छोटा संभव [[ बहुफलकीय ग्राफ ]] है जिसमें हैमिल्टनियन चक्र नहीं है। एक संभावित हैमिल्टनियन पथ दिखाया गया है।]]किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है, जब उसके समापन बिंदु आसन्न हों।
[[Image:Herschel Hamiltonian path.svg|thumb|[[हर्शल ग्राफ]] सबसे छोटा संभव [[ बहुफलकीय ग्राफ |बहुफलकीय ग्राफ]] है जिसमें हैमिल्टनियन चक्र नहीं है। एक संभावित हैमिल्टनियन पथ दिखाया गया है।]]किसी भी हैमिल्टनियन चक्र को उसके किनारों में से एक को हटाकर हैमिल्टनियन पथ में परिवर्तित किया जा सकता है, लेकिन हैमिल्टनियन पथ को हैमिल्टनियन चक्र तक तभी बढ़ाया जा सकता है, जब उसके समापन बिंदु आसन्न हों।


सभी हैमिल्टनियन ग्राफ [[द्विसंबद्ध ग्राफ|द्विसंबद्ध]] हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, [[पीटरसन ग्राफ]] देखें)।<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=बाइकनेक्टेड ग्राफ|author=Eric Weinstein|publisher=Wolfram MathWorld}}</ref>
सभी हैमिल्टनियन ग्राफ [[द्विसंबद्ध ग्राफ|द्विसंबद्ध]] हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, [[पीटरसन ग्राफ]] देखें)।<ref>{{cite web|url=http://mathworld.wolfram.com/BiconnectedGraph.html|title=बाइकनेक्टेड ग्राफ|author=Eric Weinstein|publisher=Wolfram MathWorld}}</ref>
Line 73: Line 73:
जैसा कि पूर्ण ग्राफ़ हैमिल्टनियन हैं, सभी ग्राफ़ जिनका समापन पूर्ण है, हैमिल्टनियन हैं, जो कि डिराक और ओरे द्वारा निम्नलिखित पहले के प्रमेय की सामग्री है।
जैसा कि पूर्ण ग्राफ़ हैमिल्टनियन हैं, सभी ग्राफ़ जिनका समापन पूर्ण है, हैमिल्टनियन हैं, जो कि डिराक और ओरे द्वारा निम्नलिखित पहले के प्रमेय की सामग्री है।


{{math theorem | name = Dirac's Theorem (1952) | math_statement = A [[simple graph]] with {{mvar|n}} vertices (<math>n\geq 3</math>) is Hamiltonian if every vertex has degree <math>\tfrac{n}{2}</math> or greater.}}
{{math theorem | name = डिराक की प्रमेय (1952) | math_statement = {{mvar|n}} शीर्षों (<math>n\geq 3</math>) के साथ एक [[सरल ग्राफ]] हैमिल्टनियन है यदि प्रत्येक शीर्ष की डिग्री <math>\tfrac{n}{2}</math> या इससे अधिक है।}}


{{math theorem | name = [[Ore's theorem|Ore's Theorem]] (1960) | math_statement = A [[simple graph]] with {{mvar|n}} vertices (<math>n\geq 3</math>) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is {{mvar|n}} or greater.}}
{{math theorem | name = [[अयस्क की प्रमेय|अयस्क की प्रमेय]] (1960) | math_statement = {{mvar|n}} शीर्षों (<math>n\geq 3</math>) के साथ एक [[सरल ग्राफ]] हैमिल्टनियन है, यदि गैर-निकटवर्ती शीर्षों के प्रत्येक युग्म के लिए, उनकी डिग्री का योग {{mvar|n}} या उससे अधिक है।}}


निम्नलिखित प्रमेयों को निर्देशित संस्करणों के रूप में माना जा सकता है:
निम्नलिखित प्रमेयों को निर्देशित संस्करणों के रूप में माना जा सकता है-


{{math theorem | name = Ghouila–Houiri (1960) | math_statement = A [[strongly connected graph|strongly connected]] [[simple graph|simple]] [[directed graph]] with {{mvar|n}} vertices is Hamiltonian if every vertex has a full degree greater than or equal to {{mvar|n}}.}}
{{math theorem | name = घौइला-होउरी (1960) | math_statement = {{mvar|n}} शीर्षों के साथ [[दृढ़ता से सम्बद्ध ग्राफ|दृढ़ता से सम्बद्ध]] [[सरल निर्देशित ग्राफ]] हैमिल्टनियन है यदि प्रत्येक शीर्ष की पूर्ण डिग्री {{mvar|n}} से अधिक या उसके बराबर है।}}


{{math theorem | name = Meyniel (1973) | math_statement = A [[strongly connected graph|strongly connected]] [[simple graph|simple]] [[directed graph]] with {{mvar|n}} vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to <math>2n-1</math>}}
{{math theorem | name = मेयनियल (1973) | math_statement = {{mvar|n}} शीर्ष के साथ [[दृढ़ता से सम्बद्ध|दृढ़ता से सम्बद्ध]]   [[सरल निर्देशित ग्राफ|सरल]] [[निर्देशित ग्राफ]] हैमिल्टनियन है यदि अलग-अलग गैर-आसन्न शीर्ष के प्रत्येक युग्म की पूर्ण डिग्री का योग <math>2n-1</math> से अधिक या उसके बराबर है}}


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


{{math theorem | name = Rahman–[[Mohammad Kaykobad|Kaykobad]] (2005) | math_statement = A [[simple graph]] with {{mvar|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 {{mvar|n}}.<ref>{{Cite journal|title = On Hamiltonian cycles and Hamiltonian paths|last1 = Rahman|first1 = M. S.|date = April 2005|journal = Information Processing Letters|doi = 10.1016/j.ipl.2004.12.002|last2 = Kaykobad|first2 = M.|volume = 94|pages = 37–41}}</ref>}}
{{math theorem | name = रहमान–[[कायकोबड|कायकोबड]] (2005) | math_statement = {{mvar|n}} शीर्षों के साथ [[सरल ग्राफ]] में एक हैमिल्टनियन पथ है, यदि प्रत्येक गैर-निकटवर्ती शीर्ष युग्म के लिए उनकी डिग्री का योग और उनकी सबसे छोटी पथ लंबाई {{mvar|n}} से अधिक है।}}


उपरोक्त प्रमेय केवल हैमिल्टनियन पथ के एक ग्राफ में अस्तित्व को पहचान सकता है और हैमिल्टनियन चक्र को नहीं।
उपरोक्त प्रमेय केवल हैमिल्टनियन पथ के ग्राफ में अस्तित्व को पहचान सकता है और हैमिल्टनियन चक्र को नहीं।


इनमें से कई परिणामों में संतुलित द्विदलीय रेखांकन के अनुरूप हैं, जिसमें शीर्ष डिग्री की तुलना पूरे ग्राफ में शीर्षों की संख्या के बजाय द्विदलीय के एक तरफ के शीर्षों की संख्या से की जाती है।<ref>{{citation | last1 = Moon | first1 = J. | last2 = Moser | first2 = L. | author2-link = Leo Moser | doi = 10.1007/BF02759704 | journal = [[Israel Journal of Mathematics]] | mr = 0161332 | pages = 163–165 | title = On Hamiltonian bipartite graphs | volume = 1 | issue = 3 | year = 1963| s2cid = 119358798 }}</ref>
इनमें से कई परिणामों में संतुलित द्विपक्षीय ग्राफ के अनुरूप हैं, जिसमें शीर्ष डिग्री की तुलना पूरे ग्राफ में शीर्षों की संख्या के स्थान पर द्विपक्षीय के एक तरफ के शीर्षों की संख्या से की जाती है।<ref>{{citation | last1 = Moon | first1 = J. | last2 = Moser | first2 = L. | author2-link = Leo Moser | doi = 10.1007/BF02759704 | journal = [[Israel Journal of Mathematics]] | mr = 0161332 | pages = 163–165 | title = On Hamiltonian bipartite graphs | volume = 1 | issue = 3 | year = 1963| s2cid = 119358798 }}</ref>
 
== प्लानर ग्राफ में हैमिल्टनियन चक्रों का अस्तित्व ==
 
{{math theorem | math_statement = 4-सम्बद्ध प्लानर त्रिभुज में एक हैमिल्टनियन चक्र है।<ref>{{citation
== प्लेनर ग्राफ में हैमिल्टनियन चक्रों का अस्तित्व ==
{{math theorem | math_statement = A 4-connected planar triangulation has a Hamiltonian cycle.<ref>{{citation
  | last = Whitney | first = Hassler | author-link = Hassler Whitney
  | last = Whitney | first = Hassler | author-link = Hassler Whitney
  | doi = 10.2307/1968197
  | doi = 10.2307/1968197
Line 105: Line 103:
  | year = 1931| jstor = 1968197}}</ref>}}
  | year = 1931| jstor = 1968197}}</ref>}}


{{math theorem | math_statement = A 4-connected planar graph has a Hamiltonian cycle.<ref>{{citation
{{math theorem | math_statement = एक 4-सम्बद्ध प्लानर ग्राफ में हैमिल्टनियन चक्र होता है।<ref>{{citation
  | last = Tutte | first = W. T. | author-link = W._T._Tutte
  | last = Tutte | first = W. T. | author-link = W._T._Tutte
  | doi = 10.1090/s0002-9947-1956-0081471-8
  | doi = 10.1090/s0002-9947-1956-0081471-8
Line 116: Line 114:
== [[हैमिल्टनियन चक्र बहुपद]] ==
== [[हैमिल्टनियन चक्र बहुपद]] ==


दिए गए भारित डिग्राफ के हैमिल्टनियन चक्रों का एक बीजगणितीय प्रतिनिधित्व (जिनके चापों को एक निश्चित जमीनी क्षेत्र से वजन सौंपा गया है) हैमिल्टनियन चक्र बहुपद है, इसके भारित आसन्न मैट्रिक्स को डिग्राफ के हैमिल्टनियन चक्रों के चाप भार के उत्पादों के योग के रूप में परिभाषित किया गया है। . चाप भार में एक फ़ंक्शन के रूप में यह बहुपद समान रूप से शून्य नहीं है यदि और केवल यदि डिग्राफ हैमिल्टनियन है। इसकी गणना करने की कम्प्यूटेशनल जटिलताओं और स्थायी कंप्यूटिंग के बीच संबंध ग्रिगोरी कोगन द्वारा दिखाया गया था।<ref>{{citation
दिए गए भारित द्विग्राफ के हैमिल्टनियन चक्रों का बीजगणितीय प्रतिनिधित्व (जिनके चापों को निश्चित जमीनी क्षेत्र से वजन सौंपा गया है) हैमिल्टनियन चक्र बहुपद है, इसके भारित आसन्न मैट्रिक्स को द्विग्राफ के हैमिल्टनियन चक्रों के चाप भार के उत्पादों के योग के रूप में परिभाषित किया गया है। चाप भार में फलन के रूप में यह बहुपद समान रूप से शून्य नहीं है यदि और केवल यदि द्विग्राफ हैमिल्टनियन है। इसकी गणना करने की कम्प्यूटेशनल जटिलताओं और स्थायी की गणना के बीच संबंध ग्रिगोरि कोगन द्वारा दिखाया गया था।<ref>{{citation
  | first = Grigoriy |last = Kogan
  | first = Grigoriy |last = Kogan
  | title = Computing permanents over fields of characteristic 3: where and why it becomes difficult
  | title = Computing permanents over fields of characteristic 3: where and why it becomes difficult
Line 126: Line 124:
  |s2cid = 39024286
  |s2cid = 39024286
  }}</ref>
  }}</ref>
== यह भी देखें ==
== यह भी देखें ==
{{div col|colwidth=30em}}
{{div col|colwidth=30em}}
* बार्नेट का अनुमान, घन द्विदलीय ग्राफ पॉलीहेड्रल ग्राफ की हैमिल्टनसिटी पर एक खुली समस्या
* बार्नेट का अनुमान, घन द्विपक्षीय बहुफलकीय ग्राफ की हैमिल्टनसिटी पर एक स्पष्ट समस्या
* [[यूलेरियन पथ]], एक ग्राफ में सभी किनारों के माध्यम से पथ
* [[यूलेरियन पथ]], ग्राफ में सभी किनारों से होकर जाने वाला पथ
* फ़्लिशनर की प्रमेय, ग्राफ की हैमिल्टनियन शक्ति पर
* फ्लाइशेर की प्रमेय, ग्राफ के हैमिल्टनियन वर्गों पर
* [[ग्रे कोड]]
* [[ग्रे कोड]]
* ग्रिनबर्ग का प्रमेय एक हैमिल्टनियन चक्र होने के लिए [[ प्लेनर ग्राफ ]]़ के लिए एक आवश्यक शर्त देता है
* ग्रिनबर्ग की प्रमेय [[समतलीय ग्राफ]] के लिए हैमिल्टनियन चक्र होने के लिए एक आवश्यक शर्त देती है  
* हैमिल्टनियन पथ समस्या, हैमिल्टनियन पथ खोजने की कम्प्यूटेशनल समस्या
* हैमिल्टनियन पथ समस्या, हैमिल्टनियन पथ खोजने की कम्प्यूटेशनल समस्या
* हाइपो[[सुभामिल्टोनियन ग्राफ]], एक गैर-हैमिल्टनियन ग्राफ जिसमें प्रत्येक शीर्ष-हटाए गए सबग्राफ हैमिल्टनियन हैं
* [[हाइपोहैमिल्टनियन]] ग्राफ, एक गैर-हैमिल्टनियन ग्राफ जिसमें प्रत्येक शीर्ष-हटाए गए सबग्राफ हैमिल्टनियन हैं
* नाइट का दौरा, नाइट के ग्राफ में हैमिल्टनियन चक्र
* नाइट का दौरा, नाइट के ग्राफ में हैमिल्टनियन चक्र
* हैमिल्टनियन [[क्यूबिक ग्राफ]] के लिए [[ एलसीएफ संकेतन ]]।
* हैमिल्टनियन [[घन ग्राफ]] के लिए [[एलसीएफ (LCF) संकेतन]]।
* लोवाज़ का अनुमान है कि [[शीर्ष-सकर्मक ग्राफ]] हैमिल्टनियन हैं
* लोवाज़ का अनुमान है कि [[शीर्ष-संक्रमणीय ग्राफ]] हैमिल्टनियन हैं
* [[पैनसाइक्लिक ग्राफ]], हैमिल्टनियन चक्र सहित सभी लंबाई के चक्रों के साथ ग्राफ
* [[पैनसाइक्लिक ग्राफ]], हैमिल्टनियन चक्र सहित सभी लंबाई के चक्रों के साथ ग्राफ
* कोनिग्सबर्ग के सात पुल
* कोनिग्सबर्ग के सात पुल
* [[लघुता प्रतिपादक]], एक परिवार में ग्राफ हैमिल्टनियन से कितनी दूर हो सकता है इसका एक संख्यात्मक माप
* [[लघुता प्रतिपादक]] एक संख्यात्मक माप है कि एक परिवार में ग्राफ हैमिल्टनियन से कितनी दूर हो सकते हैं
* [[सांप-इन-द-बॉक्स]], हाइपरक्यूब में सबसे लंबा [[प्रेरित पथ]]
* [[स्नेक-इन-द-बॉक्स]], हाइपरक्यूब में सबसे लंबा [[प्रेरित पथ]]  
* स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम एक [[permutohedron]] में हैमिल्टनियन पथ खोजने के लिए
* स्टाइनहॉस-जॉनसन-ट्रॉटर एल्गोरिथम [[परमुटोहेड्रोन]] में हैमिल्टनियन पथ खोजने के लिए
* Subhamiltonian ग्राफ, एक प्लानर ग्राफ हैमिल्टनियन ग्राफ का एक सबग्राफ
* उपहैमिल्टनियन ग्राफ, प्लानर ग्राफ हैमिल्टनियन ग्राफ का एक सबग्राफ
* टैट का अनुमान (अब झूठा है) कि 3-नियमित बहुफलकीय रेखांकन हैमिल्टनियन हैं
* टैट का अनुमान (अब असत्य जाना जाता है) कि 3-नियमित बहुफलकीय ग्राफ हैमिल्टनियन हैं  
* [[ट्रैवलिंग सेल्समैन की समस्या]]
* [[यात्रा विक्रेता समस्या]]{{div col end}}
{{div col end}}


==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist}}
{{reflist}}
== संदर्भ ==
== संदर्भ ==
* {{citation
* {{citation
Line 229: Line 222:
  | volume = 7
  | volume = 7
  | year = 1962}}.
  | year = 1962}}.
==बाहरी संबंध==
==बाहरी संबंध==
* {{MathWorld|title=Hamiltonian Cycle|urlname=HamiltonianCycle}}
* {{MathWorld|title=Hamiltonian Cycle|urlname=HamiltonianCycle}}
* [https://web.archive.org/web/20120309190309/http://www.graph-theory.net/euler-tour-and-hamilton-cycles/ Euler tour and Hamilton cycles]
* [https://web.archive.org/web/20120309190309/http://www.graph-theory.net/euler-tour-and-hamilton-cycles/ Euler tour and Hamilton cycles]
[[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]] [[Category: एनपी-पूर्ण समस्याएं]] [[Category: ग्राफ सिद्धांत वस्तुओं]] [[Category: हैमिल्टनियन पथ और चक्र | हैमिल्टनियन पथ और चक्र ]] [[Category: विलियम रोवन हैमिल्टन]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 28/02/2023]]
[[Category:Created On 28/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Multi-column templates]]
[[Category:Pages using div col with small parameter]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Templates using under-protected Lua modules]]
[[Category:Wikipedia fully protected templates|Div col]]
[[Category:एनपी-पूर्ण समस्याएं]]
[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
[[Category:ग्राफ सिद्धांत वस्तुओं]]
[[Category:विलियम रोवन हैमिल्टन]]
[[Category:हैमिल्टनियन पथ और चक्र| हैमिल्टनियन पथ और चक्र ]]

Latest revision as of 09:56, 29 August 2023

This article is about यह लेख हैमिल्टनियन पथों की प्रकृति के बारे में है।. For किसी दिए गए ग्राफ में हैमिल्टनियन पथ या चक्र के अस्तित्व के प्रश्न के लिए, see हैमिल्टनियन पथ समस्या देखें।.
छह शीर्षों के नेटवर्क के चारों ओर एक हैमिल्टनियन चक्र

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

गुण

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

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

सभी हैमिल्टनियन ग्राफ द्विसंबद्ध हैं, लेकिन द्विसंबद्ध ग्राफ को हैमिल्टनियन होना आवश्यक नहीं है (उदाहरण के लिए, पीटरसन ग्राफ देखें)।[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) — एक ग्राफ हैमिल्टनियन है यदि और केवल अगर इसका समापन हैमिल्टनियन है।

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

डिराक की प्रमेय (1952) — n शीर्षों () के साथ एक सरल ग्राफ हैमिल्टनियन है यदि प्रत्येक शीर्ष की डिग्री या इससे अधिक है।

अयस्क की प्रमेय (1960) — n शीर्षों () के साथ एक सरल ग्राफ हैमिल्टनियन है, यदि गैर-निकटवर्ती शीर्षों के प्रत्येक युग्म के लिए, उनकी डिग्री का योग n या उससे अधिक है।

निम्नलिखित प्रमेयों को निर्देशित संस्करणों के रूप में माना जा सकता है-

घौइला-होउरी (1960) — n शीर्षों के साथ दृढ़ता से सम्बद्ध सरल निर्देशित ग्राफ हैमिल्टनियन है यदि प्रत्येक शीर्ष की पूर्ण डिग्री n से अधिक या उसके बराबर है।

मेयनियल (1973) — n शीर्ष के साथ दृढ़ता से सम्बद्ध सरल निर्देशित ग्राफ हैमिल्टनियन है यदि अलग-अलग गैर-आसन्न शीर्ष के प्रत्येक युग्म की पूर्ण डिग्री का योग से अधिक या उसके बराबर है

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

रहमान–कायकोबड (2005) — n शीर्षों के साथ सरल ग्राफ में एक हैमिल्टनियन पथ है, यदि प्रत्येक गैर-निकटवर्ती शीर्ष युग्म के लिए उनकी डिग्री का योग और उनकी सबसे छोटी पथ लंबाई n से अधिक है।

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

इनमें से कई परिणामों में संतुलित द्विपक्षीय ग्राफ के अनुरूप हैं, जिसमें शीर्ष डिग्री की तुलना पूरे ग्राफ में शीर्षों की संख्या के स्थान पर द्विपक्षीय के एक तरफ के शीर्षों की संख्या से की जाती है।[12]

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

Theorem — 4-सम्बद्ध प्लानर त्रिभुज में एक हैमिल्टनियन चक्र है।[13]

Theorem — एक 4-सम्बद्ध प्लानर ग्राफ में हैमिल्टनियन चक्र होता है।[14]

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

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

यह भी देखें

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

टिप्पणियाँ

  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. ↑ de 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. ↑ 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
  13. ↑ Whitney, Hassler (1931), "A theorem on graphs", Annals of Mathematics, Second Series, 32 (2): 378–390, doi:10.2307/1968197, JSTOR 1968197, MR 1503003
  14. ↑ Tutte, W. T. (1956), "A theorem on planar graphs", Trans. Amer. Math. Soc., 82: 99–116, doi:10.1090/s0002-9947-1956-0081471-8
  15. ↑ 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

संदर्भ

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैमिल्टनियन_पथ&oldid=254012’