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

From Vigyanwiki
(text)
Line 2: Line 2:
{{about|यह निर्धारित करने की विशिष्ट समस्या कि किसी दिए गए ग्राफ़ में हैमिल्टनियन पथ या चक्र मौजूद है या नहीं|सामान्य ग्राफ़ सिद्धांत अवधारणाएँ|हैमिल्टनियन पथ}}
{{about|यह निर्धारित करने की विशिष्ट समस्या कि किसी दिए गए ग्राफ़ में हैमिल्टनियन पथ या चक्र मौजूद है या नहीं|सामान्य ग्राफ़ सिद्धांत अवधारणाएँ|हैमिल्टनियन पथ}}


[[ग्राफ सिद्धांत]] के गणित क्षेत्र में [[हैमिल्टनियन पथ|'''हैमिल्टनियन पथ''']] समस्या और हैमिल्टनियन चक्र समस्या यह निर्धारित करती है कि हैमिल्टनियन पथ (अदिष्‍ट या [[निर्देशित ग्राफ|दिष्ट ग्राफ]] में जो प्रत्येक शीर्ष पर बिल्कुल एक बार जाता है) या हैमिल्टनियन चक्र किसी दिए गए ग्राफ़ (चाहे दिष्ट ग्राफ हो या [[अप्रत्यक्ष ग्राफ|अदिष्‍ट ग्राफ]]) में मौजूद है। दोनों समस्याएँ एनपी-पूर्ण हैं।<ref>{{Citation|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A1.3: GT37&ndash;39, pp.&nbsp;199&ndash;200.</ref>  
[[ग्राफ सिद्धांत]] के गणित क्षेत्र में [[हैमिल्टनियन पथ|'''हैमिल्टनियन पथ''']] समस्या और हैमिल्टनियन चक्र समस्या यह निर्धारित करती है कि हैमिल्टनियन पथ (अदिष्‍ट या [[निर्देशित ग्राफ|दिष्ट ग्राफ]] में जो प्रत्येक शीर्ष पर बिल्कुल एक बार जाता है) या हैमिल्टनियन चक्र किसी दिए गए ग्राफ़ (चाहे दिष्ट ग्राफ हो या [[अप्रत्यक्ष ग्राफ|अदिष्‍ट ग्राफ]]) में सम्मिलित है। दोनों समस्याएँ NP-पूर्ण हैं।<ref>{{Citation|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5| title-link = Computers and Intractability: A Guide to the Theory of NP-Completeness }} A1.3: GT37&ndash;39, pp.&nbsp;199&ndash;200.</ref>  


हैमिल्टनियन चक्र समस्या [[ट्रैवलिंग सेल्समैन की समस्या|ट्रैवलिंग सेल्समैन समस्या]] का विशेष मामला है, जो दो शहरों के बीच की दूरी निर्धारित करके प्राप्त की जाती है यदि वे आसन्न और दो हैं अन्यथा, यह सत्यापित करते हुए कि यात्रा की गई कुल दूरी n के बराबर है (यदि हां, तो मार्ग है) हैमिल्टनियन सर्किट  है; यदि कोई हैमिल्टनियन सर्किट नहीं है तो सबसे छोटा मार्ग लंबा होगा)।
हैमिल्टनियन चक्र समस्या [[ट्रैवलिंग सेल्समैन की समस्या|ट्रैवलिंग सेल्समैन समस्या]] का विशेष मामला है, जो दो शहरों के बीच की दूरी निर्धारित करके प्राप्त की जाती है यदि वे आसन्न और दो हैं अन्यथा, यह सत्यापित करते हुए कि यात्रा की गई कुल दूरी n के बराबर है (यदि हां, तो मार्ग है) हैमिल्टनियन सर्किट  है; यदि कोई हैमिल्टनियन सर्किट नहीं है तो सबसे छोटा मार्ग लंबा होगा)।
Line 10: Line 10:


* एक दिशा में, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या से संबंधित हो सकती है, जिसमें नया [[सार्वभौमिक शीर्ष]] x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ खोजना संभव नहीं है हैमिल्टनियन चक्र खोजने की तुलना में काफी धीमा होता है (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फ़ंक्शन के रूप में)।
* एक दिशा में, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या से संबंधित हो सकती है, जिसमें नया [[सार्वभौमिक शीर्ष]] x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ खोजना संभव नहीं है हैमिल्टनियन चक्र खोजने की तुलना में काफी धीमा होता है (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फ़ंक्शन के रूप में)।
* दूसरी दिशा में, ग्राफ़ G के लिए हैमिल्टनियन चक्र समस्या, ग्राफ़ H में हैमिल्टनियन पथ समस्या के समतुल्य है, जिसे क्रमशः G के शीर्ष v और v' से जुड़े टर्मिनल (डिग्री-एक) शीर्ष s और t को जोड़कर प्राप्त किया गया है। v की क्लीव्ड प्रतिलिपि जो v' को v के समान निकटतम देता है। H में हैमिल्टनियन पथ शीर्षों से होकर गुजरता है {{tmath|s-v-x-\cdots-y-v'-t}} से होकर गुजरता है G में चल{{tmath|v-x-\cdots-y(-v)}} रहे हैमिल्टनियन चक्र से मेल खाता है।<ref>[https://math.stackexchange.com/q/1290804 Reduction from Hamiltonian cycle to Hamiltonian path]</ref>
* दूसरी दिशा में, ग्राफ़ G के लिए हैमिल्टनियन चक्र समस्या, ग्राफ़ H में हैमिल्टनियन पथ समस्या के समतुल्य है, जिसे क्रमशः G के शीर्ष v और v' से कनेक्टेड टर्मिनल (डिग्री-एक) शीर्ष s और t को जोड़कर प्राप्त किया गया है। v की क्लीव्ड प्रतिलिपि जो v' को v के समान निकटतम देता है। H में हैमिल्टनियन पथ शीर्षों से होकर गुजरता है {{tmath|s-v-x-\cdots-y-v'-t}} से होकर गुजरता है G में चल{{tmath|v-x-\cdots-y(-v)}} रहे हैमिल्टनियन चक्र से मेल खाता है।<ref>[https://math.stackexchange.com/q/1290804 Reduction from Hamiltonian cycle to Hamiltonian path]</ref>
==एल्गोरिदम==
==एल्गोरिदम==
शीर्षों के n! विभिन्न अनुक्रम जो किसी दिए गए ''n''-शीर्ष ग्राफ़ में हैमिल्टनियन पथ हो सकते हैं (और एक पूर्ण ग्राफ़ में हैं), इसलिए  [[क्रूर बल खोज|मनमानीबल गवेक्षण]] एल्गोरिदम जो सभी संभावित अनुक्रमों का परीक्षण करता है वह बहुत धीमा होता है। दिष्ट ग्राफ़ पर हैमिल्टनियन चक्र को खोजने के लिए प्रारंभिक सटीक एल्गोरिदम मार्टेलो का गणनात्मक एल्गोरिदम था।<ref>{{citation
शीर्षों के n! विभिन्न अनुक्रम जो किसी दिए गए ''n''-शीर्ष ग्राफ़ में हैमिल्टनियन पथ हो सकते हैं (और एक पूर्ण ग्राफ़ में हैं), इसलिए  [[क्रूर बल खोज|मनमानीबल गवेक्षण]] एल्गोरिदम जो सभी संभावित अनुक्रमों का परीक्षण करता है वह बहुत धीमा होता है। दिष्ट ग्राफ़ पर हैमिल्टनियन चक्र को खोजने के लिए प्रारंभिक सटीक एल्गोरिदम मार्टेलो का गणनात्मक एल्गोरिदम था।<ref>{{citation
Line 30: Line 30:
  | doi = 10.1145/321850.321854
  | doi = 10.1145/321850.321854
  | issue = 4| s2cid = 7132716
  | issue = 4| s2cid = 7132716
  }}</ref> ग्राफ़ के किनारों को तीन वर्गों में विभाजित करता है: वे जो पथ में होने चाहिए, वे जो पथ में नहीं हो सकते, और अनिर्णीत हैं। जैसे-जैसे गवेक्षण आगे बढ़ती है, निर्णय नियमों का सेट अनिर्णीत किनारों को वर्गीकृत करता है, और यह निर्धारित करता है कि गवेक्षण को रोकना है या जारी रखना है। एल्गोरिदम ग्राफ़ को उन घटकों में विभाजित करता है जिन्हें अलग से हल किया जा सकता है। इसके अलावा, समय O(''n''<sup>2</sup> 2<sup>''n''</sup>) में समस्या को हल करने के लिए बेलमैन, हेल्ड और कार्प के [[गतिशील प्रोग्रामिंग|गतिक क्रमादेशन]] एल्गोरिदम का उपयोग किया जा सकता है। इस विधि में, कोई यह निर्धारित करता है कि शीर्षों के प्रत्येक सेट ''S'' और ''S'' में प्रत्येक शीर्ष v के लिए, क्या कोई ऐसा पथ है जो S में बिल्कुल शीर्षों को कवर करता है और ''v'' पर समाप्त होता है। ''S'' और ''v'' की प्रत्येक पसंद के लिए, एक पथ मौजूद है ''(S,v)'' यदि और केवल यदि ''v'' का कोई निकटतम ''w'' है, जैसे कि ''(S − v,w)'' के लिए पथ मौजूद है, जिसे गतिशील कार्यक्रम में पहले से ही गणना की गई जानकारी से देखा जा सकता है।<ref>{{citation
  }}</ref> ग्राफ़ के किनारों को तीन वर्गों में विभाजित करता है: वे जो पथ में होने चाहिए, वे जो पथ में नहीं हो सकते, और अनिर्णीत हैं। जैसे-जैसे गवेक्षण आगे बढ़ती है, निर्णय नियमों का सेट अनिर्णीत किनारों को वर्गीकृत करता है, और यह निर्धारित करता है कि गवेक्षण को रोकना है या जारी रखना है। एल्गोरिदम ग्राफ़ को उन घटकों में विभाजित करता है जिन्हें अलग से हल किया जा सकता है। इसके अलावा, समय O(''n''<sup>2</sup> 2<sup>''n''</sup>) में समस्या को हल करने के लिए बेलमैन, हेल्ड और कार्प के [[गतिशील प्रोग्रामिंग|गतिक क्रमादेशन]] एल्गोरिदम का उपयोग किया जा सकता है। इस विधि में, कोई यह निर्धारित करता है कि शीर्षों के प्रत्येक सेट ''S'' और ''S'' में प्रत्येक शीर्ष v के लिए, क्या कोई ऐसा पथ है जो S में बिल्कुल शीर्षों को कवर करता है और ''v'' पर समाप्त होता है। ''S'' और ''v'' की प्रत्येक पसंद के लिए, एक पथ सम्मिलित है ''(S,v)'' यदि और केवल यदि ''v'' का कोई निकटतम ''w'' है, जैसे कि ''(S − v,w)'' के लिए पथ सम्मिलित है, जिसे गतिशील कार्यक्रम में पहले से ही गणना की गई जानकारी से देखा जा सकता है।<ref>{{citation
  | last = Bellman | first = R. | authorlink = Richard Bellman
  | last = Bellman | first = R. | authorlink = Richard Bellman
  | doi = 10.1145/321105.321111
  | doi = 10.1145/321105.321111
Line 61: Line 61:
  | isbn = 978-1-4244-8525-3}}.</ref>
  | isbn = 978-1-4244-8525-3}}.</ref>


अधिकतम डिग्री तीन के ग्राफ़ के लिए, सावधानीपूर्वक बैकट्रैकिंग गवेक्षण से समय O(1.251<sup>''n''</sup>) में  हैमिल्टनियन चक्र (यदि कोई मौजूद है) पाया जा सकता है।<ref>{{citation
अधिकतम डिग्री तीन के ग्राफ़ के लिए, सावधानीपूर्वक बैकट्रैकिंग गवेक्षण से समय O(1.251<sup>''n''</sup>) में  हैमिल्टनियन चक्र (यदि कोई सम्मिलित है) पाया जा सकता है।<ref>{{citation
  | last1 = Iwama | first1 = Kazuo
  | last1 = Iwama | first1 = Kazuo
  | last2 = Nakashima | first2 = Takuya
  | last2 = Nakashima | first2 = Takuya
Line 76: Line 76:
[[सैट सॉल्वर]] का उपयोग करके हैमिल्टनियन पथ और चक्र पाए जा सकते हैं।
[[सैट सॉल्वर]] का उपयोग करके हैमिल्टनियन पथ और चक्र पाए जा सकते हैं।


पारंपरिक कंप्यूटरों पर हैमिल्टनियन पथ और चक्र समस्याओं को हल करने की कठिनाई के कारण, कंप्यूटिंग के अपरंपरागत मॉडल में भी उनका अध्ययन किया गया है। उदाहरण के लिए, [[लियोनार्ड एडलमैन]] ने दिखाया कि हैमिल्टनियन पथ समस्या को [[डीएनए कंप्यूटिंग]] का उपयोग करके हल किया जा सकता है। रासायनिक प्रतिक्रियाओं में निहित समानता का फायदा उठाते हुए, ग्राफ़ के शीर्षों की संख्या में रैखिक कई रासायनिक प्रतिक्रिया चरणों का उपयोग करके समस्या को हल किया जा सकता है; हालाँकि, प्रतिक्रिया में भाग लेने के लिए डीएनए अणुओं की एक फैक्टोरियल संख्या की आवश्यकता होती है।<ref>{{citation
पारंपरिक कंप्यूटरों पर हैमिल्टनियन पथ और चक्र समस्याओं को हल करने की कठिनाई के कारण, कंप्यूटिंग के अपरंपरागत मॉडल में भी उनका अध्ययन किया गया है। उदाहरण के लिए, [[लियोनार्ड एडलमैन]] ने दिखाया कि हैमिल्टनियन पथ समस्या को [[डीएनए कंप्यूटिंग]] का उपयोग करके हल किया जा सकता है। रासायनिक प्रतिक्रियाओं में निहित समानता का फायदा उठाते हुए, ग्राफ़ के शीर्षों की संख्या में रैखिक कई रासायनिक प्रतिक्रिया चरणों का उपयोग करके समस्या को हल किया जा सकता है; हालाँकि, प्रतिक्रिया में भाग लेने के लिए डीएनए अणुओं की क्रमगुणित संख्या की आवश्यकता होती है।<ref>{{citation
  | last = Adleman | first = Leonard | author-link = Leonard Adleman
  | last = Adleman | first = Leonard | author-link = Leonard Adleman
  | doi = 10.1126/science.7973651
  | doi = 10.1126/science.7973651
Line 87: Line 87:
  | volume = 266
  | volume = 266
  | date = November 1994| bibcode = 1994Sci...266.1021A
  | date = November 1994| bibcode = 1994Sci...266.1021A
  | citeseerx = 10.1.1.54.2565 }}.</ref> हैमिल्टनियन समस्या का एक ऑप्टिकल समाधान भी प्रस्तावित किया गया है।<ref name= "oltean_hamiltonian">{{cite conference|author=Mihai Oltean|title= हैमिल्टनियन पथ समस्या को हल करने के लिए एक प्रकाश-आधारित उपकरण|conference=Unconventional Computing| pages= 217–227| publisher= Springer LNCS 4135|doi=10.1007/11839132_18|date=2006|arxiv=0708.1496}}</ref> समस्या का समाधान तैयार करने के लिए विचार यह है कि ऑप्टिकल केबल और बीम स्प्लिटर्स से बनी एक ग्राफ जैसी संरचना तैयार की जाए जो प्रकाश द्वारा पार की जाती है। इस दृष्टिकोण का कमजोर बिंदु ऊर्जा की आवश्यक मात्रा है जो नोड्स की संख्या में घातीय है।
  | citeseerx = 10.1.1.54.2565 }}.</ref>


==जटिलता==
हैमिल्टनियन समस्या का प्रकाशिकी समाधान भी प्रस्तावित किया गया है।<ref name="oltean_hamiltonian">{{cite conference|author=Mihai Oltean|title= हैमिल्टनियन पथ समस्या को हल करने के लिए एक प्रकाश-आधारित उपकरण|conference=Unconventional Computing| pages= 217–227| publisher= Springer LNCS 4135|doi=10.1007/11839132_18|date=2006|arxiv=0708.1496}}</ref> समस्या का समाधान तैयार करने के लिए विचार यह है कि प्रकाशिकी केबल और बीम स्प्लिटर्स (किरणपुंज विपाटक )से बनी ग्राफ जैसी संरचना तैयार की जाए जो प्रकाश द्वारा पार की जाती है। इस दृष्टिकोण का कमजोर बिंदु ऊर्जा की आवश्यक मात्रा है जो नोड्स की संख्या में घातीय है।
हैमिल्टनियन चक्र या पथ खोजने की समस्या [[एफएनपी (जटिलता)]] में है; अनुरूप [[निर्णय समस्या]] यह परीक्षण करना है कि हैमिल्टनियन चक्र या पथ मौजूद है या नहीं। दिष्ट और अदिष्‍ट हैमिल्टनियन चक्र समस्याएं कार्प की 21 एनपी-पूर्ण समस्याओं में से दो थीं। वे विशेष प्रकार के ग्राफ़ के लिए भी एनपी-पूर्ण रहते हैं, जैसे:
 
==सम्मिश्रता==
हैमिल्टनियन चक्र या पथ खोजने की समस्या [[एफएनपी (जटिलता)|एफएनपी (सम्मिश्रता)]] में है; अनुरूप [[निर्णय समस्या]] यह परीक्षण करना है कि हैमिल्टनियन चक्र या पथ सम्मिलित है या नहीं। दिष्ट और अदिष्‍ट हैमिल्टनियन चक्र समस्याएं कार्प की 21 NP-पूर्ण समस्याओं में से दो थीं। वे विशेष प्रकार के ग्राफ़ के लिए भी NP-पूर्ण रहते हैं, जैसे:


* द्विदलीय ग्राफ,<ref>{{Cite web|url=https://cs.stackexchange.com/q/18335 |title=प्रमाण है कि द्विदलीय ग्राफ़ में हैमिल्टन पथ का अस्तित्व एनपी-पूर्ण है|website=Computer Science Stack Exchange|access-date=2019-03-18}}</ref>
* द्विदलीय ग्राफ,<ref>{{Cite web|url=https://cs.stackexchange.com/q/18335 |title=प्रमाण है कि द्विदलीय ग्राफ़ में हैमिल्टन पथ का अस्तित्व एनपी-पूर्ण है|website=Computer Science Stack Exchange|access-date=2019-03-18}}</ref>
* अधिकतम डिग्री तीन के अदिष्‍ट [[समतलीय ग्राफ]]़,<ref>{{citation
* अधिकतम डिग्री तीन के अदिष्‍ट [[समतलीय ग्राफ]],<ref>{{citation
  | last1 = Garey | first1 = M. R. | author1-link = Michael Garey
  | last1 = Garey | first1 = M. R. | author1-link = Michael Garey
  | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
  | last2 = Johnson | first2 = D. S. | author2-link = David S. Johnson
Line 101: Line 103:
  | pages = 47–63
  | pages = 47–63
  | title = Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
  | title = Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
  | year = 1974| s2cid = 207693360 }}.</ref> * इंडिग्री और आउटडिग्री के साथ अधिकतम दो दिष्ट समतलीय ग्राफ़,<ref>{{citation
  | year = 1974| s2cid = 207693360 }}.</ref>  
*अंतःकोटि और आउटडिग्री के साथ अधिकतम दो दिष्ट समतलीय ग्राफ़,<ref>{{citation
  | last = Plesńik | first = J.
  | last = Plesńik | first = J.
  | issue = 4
  | issue = 4
Line 110: Line 113:
  | volume = 8
  | volume = 8
  | year = 1979
  | year = 1979
  | doi = 10.1016/0020-0190(79)90023-1}}.</ref> * [[ब्रिजलेस ग्राफ]] अदिष्‍ट समतल 3-[[नियमित ग्राफ]] द्विदलीय ग्राफ,
  | doi = 10.1016/0020-0190(79)90023-1}}.</ref>
* 3-जुड़े हुए 3-नियमित द्विदलीय ग्राफ़,<ref>{{citation
*[[ब्रिजलेस ग्राफ]] अदिष्‍ट समतल 3-[[नियमित ग्राफ]] द्विदलीय ग्राफ,
* 3-कनेक्टेड हुए 3-नियमित द्विदलीय ग्राफ़,<ref>{{citation
  | last1 = Akiyama | first1 = Takanori
  | last1 = Akiyama | first1 = Takanori
  | last2 = Nishizeki | first2 = Takao | author2-link = Takao Nishizeki
  | last2 = Nishizeki | first2 = Takao | author2-link = Takao Nishizeki
Line 122: Line 126:
  | url =  
  | url =  
  | volume = 3
  | volume = 3
  | year = 1980–1981}}.</ref> * जाली ग्राफ के उपग्राफ#स्क्वायर ग्रिड ग्राफ,<ref>{{citation
  | year = 1980–1981}}.</ref>
*वर्गाकार ग्रिड ग्राफ़ के उपग्राफ़,<ref>{{citation
  | last1 = Itai | first1 = Alon
  | last1 = Itai | first1 = Alon
  | last2 = Papadimitriou | first2 = Christos
  | last2 = Papadimitriou | first2 = Christos
Line 132: Line 137:
  | doi = 10.1137/0211056
  | doi = 10.1137/0211056
  | volume = 4
  | volume = 4
  | year = 1982| citeseerx = 10.1.1.383.1078}}.</ref> * वर्गाकार ग्रिड ग्राफ़ के घन उपग्राफ़।<ref>{{citation
  | year = 1982| citeseerx = 10.1.1.383.1078}}.</ref>
*वर्ग ग्रिड ग्राफ़ के घन उपग्राफ़।<ref>{{citation
  | last = Buro | first = Michael
  | last = Buro | first = Michael
  | contribution = Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs
  | contribution = Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs
Line 146: Line 152:
हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:
हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:


* [[के-वर्टेक्स-कनेक्टेड ग्राफ़|के-शीर्ष-कनेक्टेड ग्राफ़]] | 4-कनेक्टेड प्लेनर ग्राफ़ हमेशा W. T. टुटे के परिणाम के अनुसार हैमिल्टनियन होते हैं, और इन ग्राफ़ में हैमिल्टनियन चक्र खोजने का कम्प्यूटेशनल कार्य रैखिक समय में किया जा सकता है<ref>{{citation
* टुटे के कारण 4-कनेक्टेड समतलीय ग्राफ हमेशा हैमिल्टनियन होते हैं, और इन ग्राफ़ों में हैमिल्टनियन चक्र खोजने का कम्प्यूटेशनल कार्य तथाकथित [[ सभी पथ |टुटे पथ]] की गणना करके रैखिक समय <ref>{{citation
  | last1 = Chiba| first1 = Norishige
  | last1 = Chiba| first1 = Norishige
  | last2 = Nishizeki| first2 = Takao
  | last2 = Nishizeki| first2 = Takao
Line 155: Line 161:
  | volume = 10
  | volume = 10
  | issue = 2
  | issue = 2
  | year = 1989}}</ref> तथाकथित [[ सभी पथ ]] की गणना करके।
  | year = 1989}}</ref> में किया जा सकता है।
* टुट्टे ने इस परिणाम को यह दिखाकर सिद्ध किया कि प्रत्येक 2-जुड़े समतलीय ग्राफ में एक टुट्टे पथ होता है। बदले में टुटे पथों की गणना 2-जुड़े समतलीय ग्राफ़ के लिए भी द्विघात समय में की जा सकती है,<ref>{{citation
* टुट्टे ने इस परिणाम को यह दिखाकर सिद्ध किया कि प्रत्येक 2-कनेक्टेड समतलीय ग्राफ में टुट्टे पथ होता है। बदले में टुटे पथों की गणना 2-कनेक्टेड समतलीय ग्राफ़ के लिए भी द्विघात समय में की जा सकती है,<ref>{{citation
  | last1 = Schmid| first1 = Andreas
  | last1 = Schmid| first1 = Andreas
  | last2 = Schmidt| first2 = Jens M.
  | last2 = Schmidt| first2 = Jens M.
Line 164: Line 170:
}}</ref> जिसका उपयोग समतलीय ग्राफ़ के सामान्यीकरण में हैमिल्टनियन चक्र और लंबे चक्र को खोजने के लिए किया जा सकता है।
}}</ref> जिसका उपयोग समतलीय ग्राफ़ के सामान्यीकरण में हैमिल्टनियन चक्र और लंबे चक्र को खोजने के लिए किया जा सकता है।


इन सभी शर्तों को एक साथ रखने पर, यह खुला रहता है कि क्या 3-जुड़े 3-नियमित द्विदलीय समतल ग्राफ़ में हमेशा एक हैमिल्टनियन चक्र होना चाहिए, जिस स्थिति में उन ग्राफ़ों तक सीमित समस्या एनपी-पूर्ण नहीं हो सकती है; बार्नेट का अनुमान देखें.
इन सभी शर्तों को एक साथ रखने पर, यह खुला रहता है कि 3-कनेक्टेड 3-नियमित द्विदलीय समतल ग्राफ़ में हमेशा हैमिल्टनियन चक्र होना चाहिए, जिस स्थिति में उन ग्राफ़ों तक सीमित समस्या NP-पूर्ण नहीं हो सकती है; बार्नेट का अनुमान देखें.


ऐसे ग्राफ़ में जिनमें सभी शीर्षों की डिग्री विषम होती है, [[ हाथ मिलाना लेम्मा ]] से संबंधित एक तर्क से पता चलता है कि किसी भी निश्चित किनारे के माध्यम से हैमिल्टनियन चक्रों की संख्या हमेशा सम होती है, इसलिए यदि एक हैमिल्टनियन चक्र दिया गया है, तो दूसरा भी मौजूद होना चाहिए।<ref>{{citation
ऐसे ग्राफ़ में जिनमें सभी शीर्षों की डिग्री विषम होती है, [[ हाथ मिलाना लेम्मा |हैंडशेकिंग लेम्मा]] से संबंधित तर्क से पता चलता है कि किसी भी निश्चित किनारे के माध्यम से हैमिल्टनियन चक्रों की संख्या हमेशा सम होती है, इसलिए यदि हैमिल्टनियन चक्र दिया गया है, तो दूसरा भी सम्मिलित होना चाहिए।<ref>{{citation
  | last = Thomason
  | last = Thomason
  | first = A. G.
  | first = A. G.
Line 179: Line 185:
  | isbn = 9780720408430
  | isbn = 9780720408430
  | url = https://archive.org/details/advancesingrapht0000camb/page/259
  | url = https://archive.org/details/advancesingrapht0000camb/page/259
  }}.</ref> हालाँकि, इस दूसरे चक्र को खोजना कोई आसान कम्प्यूटेशनल कार्य नहीं लगता है। [[क्रिस्टोस पापादिमित्रियोउ]] ने इस तरह की समस्याओं को समाहित करने के लिए [[जटिलता वर्ग]] [[पीपीए (जटिलता)]] को परिभाषित किया।<ref>{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
  }}.</ref> हालाँकि, इस दूसरे चक्र को खोजना कोई आसान कम्प्यूटेशनल कार्य नहीं लगता है। [[क्रिस्टोस पापादिमित्रियोउ]] ने इस तरह की समस्याओं को समाहित करने के लिए [[जटिलता वर्ग|सम्मिश्रता वर्ग]] [[पीपीए (जटिलता)|पीपीए (सम्मिश्रता)]] को परिभाषित किया  है।<ref>{{citation | last = Papadimitriou| first = Christos H.| author-link = Christos Papadimitriou | doi = 10.1016/S0022-0000(05)80063-7
| issue = 3
| issue = 3
| journal = [[Journal of Computer and System Sciences]]
| journal = [[Journal of Computer and System Sciences]]
Line 187: Line 193:
| year = 1994 | mr = 1279412| citeseerx = 10.1.1.321.7008
| year = 1994 | mr = 1279412| citeseerx = 10.1.1.321.7008
}}.</ref>
}}.</ref>
== संदर्भ ==
== संदर्भ ==
{{commons category inline}}
{{commons category inline}}

Revision as of 11:13, 4 July 2023

This article is about यह निर्धारित करने की विशिष्ट समस्या कि किसी दिए गए ग्राफ़ में हैमिल्टनियन पथ या चक्र मौजूद है या नहीं. For सामान्य ग्राफ़ सिद्धांत अवधारणाएँ, see हैमिल्टनियन पथ.

ग्राफ सिद्धांत के गणित क्षेत्र में हैमिल्टनियन पथ समस्या और हैमिल्टनियन चक्र समस्या यह निर्धारित करती है कि हैमिल्टनियन पथ (अदिष्‍ट या दिष्ट ग्राफ में जो प्रत्येक शीर्ष पर बिल्कुल एक बार जाता है) या हैमिल्टनियन चक्र किसी दिए गए ग्राफ़ (चाहे दिष्ट ग्राफ हो या अदिष्‍ट ग्राफ) में सम्मिलित है। दोनों समस्याएँ NP-पूर्ण हैं।[1]

हैमिल्टनियन चक्र समस्या ट्रैवलिंग सेल्समैन समस्या का विशेष मामला है, जो दो शहरों के बीच की दूरी निर्धारित करके प्राप्त की जाती है यदि वे आसन्न और दो हैं अन्यथा, यह सत्यापित करते हुए कि यात्रा की गई कुल दूरी n के बराबर है (यदि हां, तो मार्ग है) हैमिल्टनियन सर्किट है; यदि कोई हैमिल्टनियन सर्किट नहीं है तो सबसे छोटा मार्ग लंबा होगा)।

पथ समस्या और चक्र समस्या के बीच कमी

हैमिल्टनियन पथ और हैमिल्टनियन चक्र खोजने की समस्याएं इस प्रकार संबंधित हो सकती हैं:

  • एक दिशा में, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या से संबंधित हो सकती है, जिसमें नया सार्वभौमिक शीर्ष x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ खोजना संभव नहीं है हैमिल्टनियन चक्र खोजने की तुलना में काफी धीमा होता है (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फ़ंक्शन के रूप में)।
  • दूसरी दिशा में, ग्राफ़ G के लिए हैमिल्टनियन चक्र समस्या, ग्राफ़ H में हैमिल्टनियन पथ समस्या के समतुल्य है, जिसे क्रमशः G के शीर्ष v और v' से कनेक्टेड टर्मिनल (डिग्री-एक) शीर्ष s और t को जोड़कर प्राप्त किया गया है। v की क्लीव्ड प्रतिलिपि जो v' को v के समान निकटतम देता है। H में हैमिल्टनियन पथ शीर्षों से होकर गुजरता है से होकर गुजरता है G में चल रहे हैमिल्टनियन चक्र से मेल खाता है।[2]

एल्गोरिदम

शीर्षों के n! विभिन्न अनुक्रम जो किसी दिए गए n-शीर्ष ग्राफ़ में हैमिल्टनियन पथ हो सकते हैं (और एक पूर्ण ग्राफ़ में हैं), इसलिए मनमानीबल गवेक्षण एल्गोरिदम जो सभी संभावित अनुक्रमों का परीक्षण करता है वह बहुत धीमा होता है। दिष्ट ग्राफ़ पर हैमिल्टनियन चक्र को खोजने के लिए प्रारंभिक सटीक एल्गोरिदम मार्टेलो का गणनात्मक एल्गोरिदम था।[3] फ़्रैंक रुबिन द्वारा गवेक्षण प्रक्रिया[4] ग्राफ़ के किनारों को तीन वर्गों में विभाजित करता है: वे जो पथ में होने चाहिए, वे जो पथ में नहीं हो सकते, और अनिर्णीत हैं। जैसे-जैसे गवेक्षण आगे बढ़ती है, निर्णय नियमों का सेट अनिर्णीत किनारों को वर्गीकृत करता है, और यह निर्धारित करता है कि गवेक्षण को रोकना है या जारी रखना है। एल्गोरिदम ग्राफ़ को उन घटकों में विभाजित करता है जिन्हें अलग से हल किया जा सकता है। इसके अलावा, समय O(n2 2n) में समस्या को हल करने के लिए बेलमैन, हेल्ड और कार्प के गतिक क्रमादेशन एल्गोरिदम का उपयोग किया जा सकता है। इस विधि में, कोई यह निर्धारित करता है कि शीर्षों के प्रत्येक सेट S और S में प्रत्येक शीर्ष v के लिए, क्या कोई ऐसा पथ है जो S में बिल्कुल शीर्षों को कवर करता है और v पर समाप्त होता है। S और v की प्रत्येक पसंद के लिए, एक पथ सम्मिलित है (S,v) यदि और केवल यदि v का कोई निकटतम w है, जैसे कि (S − v,w) के लिए पथ सम्मिलित है, जिसे गतिशील कार्यक्रम में पहले से ही गणना की गई जानकारी से देखा जा सकता है।[5][6]

एंड्रियास ब्योर्कलुंड ने हैमिल्टनियन चक्रों की संख्या की गणना करने की समस्या को कम करने के लिए समावेशन-बहिष्करण सिद्धांत का उपयोग करके चक्र कवर की गिनती की एक सरल गिनती समस्या को कम करने के लिए वैकल्पिक दृष्टिकोण प्रदान किया, जिसे कुछ मैट्रिक्स निर्धारकों की गणना करके हल किया जा सकता है। इस पद्धति का उपयोग करते हुए, उन्होंने दिखाया कि समय O(1.657n) में मोंटे कार्लो एल्गोरिथ्म द्वारा मनमाने ढंग से n-शीर्ष ग्राफ़ में हैमिल्टनियन चक्र समस्या को कैसे हल किया जाए); द्विदलीय ग्राफ के लिए इस एल्गोरिदम को समय o(1.415n) तक और बेहतर बनाया जा सकता है।[7]

अधिकतम डिग्री तीन के ग्राफ़ के लिए, सावधानीपूर्वक बैकट्रैकिंग गवेक्षण से समय O(1.251n) में हैमिल्टनियन चक्र (यदि कोई सम्मिलित है) पाया जा सकता है।[8]

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

पारंपरिक कंप्यूटरों पर हैमिल्टनियन पथ और चक्र समस्याओं को हल करने की कठिनाई के कारण, कंप्यूटिंग के अपरंपरागत मॉडल में भी उनका अध्ययन किया गया है। उदाहरण के लिए, लियोनार्ड एडलमैन ने दिखाया कि हैमिल्टनियन पथ समस्या को डीएनए कंप्यूटिंग का उपयोग करके हल किया जा सकता है। रासायनिक प्रतिक्रियाओं में निहित समानता का फायदा उठाते हुए, ग्राफ़ के शीर्षों की संख्या में रैखिक कई रासायनिक प्रतिक्रिया चरणों का उपयोग करके समस्या को हल किया जा सकता है; हालाँकि, प्रतिक्रिया में भाग लेने के लिए डीएनए अणुओं की क्रमगुणित संख्या की आवश्यकता होती है।[9]

हैमिल्टनियन समस्या का प्रकाशिकी समाधान भी प्रस्तावित किया गया है।[10] समस्या का समाधान तैयार करने के लिए विचार यह है कि प्रकाशिकी केबल और बीम स्प्लिटर्स (किरणपुंज विपाटक )से बनी ग्राफ जैसी संरचना तैयार की जाए जो प्रकाश द्वारा पार की जाती है। इस दृष्टिकोण का कमजोर बिंदु ऊर्जा की आवश्यक मात्रा है जो नोड्स की संख्या में घातीय है।

सम्मिश्रता

हैमिल्टनियन चक्र या पथ खोजने की समस्या एफएनपी (सम्मिश्रता) में है; अनुरूप निर्णय समस्या यह परीक्षण करना है कि हैमिल्टनियन चक्र या पथ सम्मिलित है या नहीं। दिष्ट और अदिष्‍ट हैमिल्टनियन चक्र समस्याएं कार्प की 21 NP-पूर्ण समस्याओं में से दो थीं। वे विशेष प्रकार के ग्राफ़ के लिए भी NP-पूर्ण रहते हैं, जैसे:

  • द्विदलीय ग्राफ,[11]
  • अधिकतम डिग्री तीन के अदिष्‍ट समतलीय ग्राफ,[12]
  • अंतःकोटि और आउटडिग्री के साथ अधिकतम दो दिष्ट समतलीय ग्राफ़,[13]
  • ब्रिजलेस ग्राफ अदिष्‍ट समतल 3-नियमित ग्राफ द्विदलीय ग्राफ,
  • 3-कनेक्टेड हुए 3-नियमित द्विदलीय ग्राफ़,[14]
  • वर्गाकार ग्रिड ग्राफ़ के उपग्राफ़,[15]
  • वर्ग ग्रिड ग्राफ़ के घन उपग्राफ़।[16]

हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:

  • टुटे के कारण 4-कनेक्टेड समतलीय ग्राफ हमेशा हैमिल्टनियन होते हैं, और इन ग्राफ़ों में हैमिल्टनियन चक्र खोजने का कम्प्यूटेशनल कार्य तथाकथित टुटे पथ की गणना करके रैखिक समय [17] में किया जा सकता है।
  • टुट्टे ने इस परिणाम को यह दिखाकर सिद्ध किया कि प्रत्येक 2-कनेक्टेड समतलीय ग्राफ में टुट्टे पथ होता है। बदले में टुटे पथों की गणना 2-कनेक्टेड समतलीय ग्राफ़ के लिए भी द्विघात समय में की जा सकती है,[18] जिसका उपयोग समतलीय ग्राफ़ के सामान्यीकरण में हैमिल्टनियन चक्र और लंबे चक्र को खोजने के लिए किया जा सकता है।

इन सभी शर्तों को एक साथ रखने पर, यह खुला रहता है कि 3-कनेक्टेड 3-नियमित द्विदलीय समतल ग्राफ़ में हमेशा हैमिल्टनियन चक्र होना चाहिए, जिस स्थिति में उन ग्राफ़ों तक सीमित समस्या NP-पूर्ण नहीं हो सकती है; बार्नेट का अनुमान देखें.

ऐसे ग्राफ़ में जिनमें सभी शीर्षों की डिग्री विषम होती है, हैंडशेकिंग लेम्मा से संबंधित तर्क से पता चलता है कि किसी भी निश्चित किनारे के माध्यम से हैमिल्टनियन चक्रों की संख्या हमेशा सम होती है, इसलिए यदि हैमिल्टनियन चक्र दिया गया है, तो दूसरा भी सम्मिलित होना चाहिए।[19] हालाँकि, इस दूसरे चक्र को खोजना कोई आसान कम्प्यूटेशनल कार्य नहीं लगता है। क्रिस्टोस पापादिमित्रियोउ ने इस तरह की समस्याओं को समाहित करने के लिए सम्मिश्रता वर्ग पीपीए (सम्मिश्रता) को परिभाषित किया है।[20]

संदर्भ

Media related to हैमिल्टनियन पथ समस्या at Wikimedia Commons

  1. ↑ Michael R. Garey and David S. Johnson (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1045-5 A1.3: GT37–39, pp. 199–200.
  2. ↑ Reduction from Hamiltonian cycle to Hamiltonian path
  3. ↑ Martello, Silvano (1983), "An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph", ACM Transactions on Mathematical Software, 9 (1): 131–138, doi:10.1145/356022.356030, S2CID 11879800
  4. ↑ Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits", Journal of the ACM, 21 (4): 576–80, doi:10.1145/321850.321854, S2CID 7132716
  5. ↑ Bellman, R. (1962), "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM, 9: 61–63, doi:10.1145/321105.321111.
  6. ↑ Held, M.; Karp, R. M. (1962), "A dynamic programming approach to sequencing problems" (PDF), J. SIAM, 10 (1): 196–210, doi:10.1137/0110015, hdl:10338.dmlcz/103900.
  7. ↑ Björklund, Andreas (2010), "Determinant sums for undirected Hamiltonicity", Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541, doi:10.1109/FOCS.2010.24, ISBN 978-1-4244-8525-3.
  8. ↑ Iwama, Kazuo; Nakashima, Takuya (2007), "An improved exact algorithm for cubic graph TSP", Proc. 13th Annual International Conference on Computing and Combinatorics (COCOON 2007), Lecture Notes in Computer Science, vol. 4598, pp. 108–117, CiteSeerX 10.1.1.219.1672, doi:10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1.
  9. ↑ Adleman, Leonard (November 1994), "Molecular computation of solutions to combinatorial problems", Science, 266 (5187): 1021–1024, Bibcode:1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565, doi:10.1126/science.7973651, JSTOR 2885489, PMID 7973651.
  10. ↑ Mihai Oltean (2006). हैमिल्टनियन पथ समस्या को हल करने के लिए एक प्रकाश-आधारित उपकरण. Unconventional Computing. Springer LNCS 4135. pp. 217–227. arXiv:0708.1496. doi:10.1007/11839132_18.
  11. ↑ "प्रमाण है कि द्विदलीय ग्राफ़ में हैमिल्टन पथ का अस्तित्व एनपी-पूर्ण है". Computer Science Stack Exchange. Retrieved 2019-03-18.
  12. ↑ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884, S2CID 207693360.
  13. ↑ Plesńik, J. (1979), "The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two" (PDF), Information Processing Letters, 8 (4): 199–201, doi:10.1016/0020-0190(79)90023-1.
  14. ↑ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313.
  15. ↑ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs", SIAM Journal on Computing, 4 (11): 676–686, CiteSeerX 10.1.1.383.1078, doi:10.1137/0211056.
  16. ↑ Buro, Michael (2000), "Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs" (PDF), Conference on Computers and Games, Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731, doi:10.1007/3-540-45579-5_17, ISBN 978-3-540-43080-3.
  17. ↑ Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs", Journal of Algorithms, 10 (2): 187–211, doi:10.1016/0196-6774(89)90012-6
  18. ↑ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
  19. ↑ Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, pp. 259–268, doi:10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, MR 0499124.
  20. ↑ Papadimitriou, Christos H. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences, 48 (3): 498–532, CiteSeerX 10.1.1.321.7008, doi:10.1016/S0022-0000(05)80063-7, MR 1279412.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हैमिल्टनियन_पथ_समस्या&oldid=209120’