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

From Vigyanwiki
(Created page with "{{short description|Problem of finding a cycle through all vertices of a graph}} {{about|the specific problem of determining whether a Hamiltonian path or cycle exists in a gi...")
 
(text)
Line 1: Line 1:
{{short description|Problem of finding a cycle through all vertices of a graph}}
{{short description|Problem of finding a cycle through all vertices of a graph}}
{{about|the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph|the general graph theory concepts|Hamiltonian path}}
{{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> हैमिल्टनियन चक्र समस्या [[ट्रैवलिंग सेल्समैन की समस्या]] का एक विशेष मामला है, जो दो शहरों के बीच की दूरी निर्धारित करके प्राप्त की जाती है यदि वे आसन्न हैं और दो अन्यथा, और यह सत्यापित करते हुए कि यात्रा की गई कुल दूरी n के बराबर है (यदि हां, तो मार्ग है) एक हैमिल्टनियन सर्किट; यदि कोई हैमिल्टनियन सर्किट नहीं है तो सबसे छोटा मार्ग लंबा होगा)।
[[ग्राफ सिद्धांत]] के गणित क्षेत्र में [[हैमिल्टनियन पथ|'''हैमिल्टनियन पथ''']] समस्या और हैमिल्टनियन चक्र समस्या यह निर्धारित करती है कि हैमिल्टनियन पथ (अदिष्‍ट या [[निर्देशित ग्राफ|दिष्ट ग्राफ]] में जो प्रत्येक शीर्ष पर बिल्कुल एक बार जाता है) या हैमिल्टनियन चक्र किसी दिए गए ग्राफ़ (चाहे दिष्ट ग्राफ हो या [[अप्रत्यक्ष ग्राफ|अदिष्‍ट ग्राफ]]) में मौजूद है। दोनों समस्याएँ एनपी-पूर्ण हैं।<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 के बराबर है (यदि हां, तो मार्ग है) हैमिल्टनियन सर्किट है; यदि कोई हैमिल्टनियन सर्किट नहीं है तो सबसे छोटा मार्ग लंबा होगा)।


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


* एक दिशा में, ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या से संबंधित हो सकती है, जिसमें एक नया [[सार्वभौमिक शीर्ष]] x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ नहीं खोजा जा सकता है हैमिल्टनियन चक्र खोजने की तुलना में काफी धीमा हो (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फ़ंक्शन के रूप में)।
* एक दिशा में, G से प्राप्त ग्राफ़ H में हैमिल्टनियन चक्र समस्या ग्राफ़ G के लिए हैमिल्टनियन पथ समस्या से संबंधित हो सकती है, जिसमें नया [[सार्वभौमिक शीर्ष]] x जोड़कर, x को G के सभी शीर्षों से जोड़ा जा सकता है। इस प्रकार, हैमिल्टनियन पथ खोजना संभव नहीं है हैमिल्टनियन चक्र खोजने की तुलना में काफी धीमा होता है (सबसे खराब स्थिति में, शीर्षों की संख्या के एक फ़ंक्शन के रूप में)।
* दूसरी दिशा में, ग्राफ़ G के लिए हैमिल्टनियन चक्र समस्या, ग्राफ़ H में हैमिल्टनियन पथ समस्या के बराबर है, जिसे G के शीर्ष v से जुड़े टर्मिनल (डिग्री (ग्राफ़ सिद्धांत)-एक) शीर्षों s और t को जोड़कर प्राप्त किया गया है। और v' के लिए, v का एक Edge_contraction#Vertex_cleaving जो v' को v के समान पड़ोस देता है। H में हैमिल्टनियन पथ शीर्षों से होकर गुजरता है {{tmath|s-v-x-\cdots-y-v'-t}} जी में चल रहे हैमिल्टनियन चक्र से मेल खाता है {{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
निर्देशित ग्राफ़ पर हैमिल्टनियन चक्र को खोजने के लिए एक प्रारंभिक सटीक एल्गोरिदम मार्टेलो का गणनात्मक एल्गोरिदम था।<ref>{{citation
  | last = Martello | first = Silvano
  | last = Martello | first = Silvano
  | journal = [[ACM Transactions on Mathematical Software]]
  | journal = [[ACM Transactions on Mathematical Software]]
Line 22: Line 21:
  | doi = 10.1145/356022.356030
  | doi = 10.1145/356022.356030
  | issue = 1| s2cid = 11879800
  | issue = 1| s2cid = 11879800
  }}</ref> फ़्रैंक रुबिन द्वारा एक खोज प्रक्रिया<ref>{{citation
  }}</ref> फ़्रैंक रुबिन द्वारा गवेक्षण प्रक्रिया<ref>{{citation
  | last = Rubin | first = Frank
  | last = Rubin | first = Frank
  | journal = [[Journal of the ACM]]
  | journal = [[Journal of the ACM]]
Line 31: 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 51: Line 50:
  | url = http://dml.cz/bitstream/handle/10338.dmlcz/103900/AplMat_26-1981-2_3.pdf
  | url = http://dml.cz/bitstream/handle/10338.dmlcz/103900/AplMat_26-1981-2_3.pdf
  }}.</ref>
  }}.</ref>
एंड्रियास ब्योर्कलुंड ने हैमिल्टनियन चक्रों की संख्या की गणना करने की समस्या को कम करने के लिए समावेशन-बहिष्करण सिद्धांत का उपयोग करके चक्र कवर की गिनती की एक सरल गिनती समस्या को कम करने के लिए एक वैकल्पिक दृष्टिकोण प्रदान किया, जिसे कुछ मैट्रिक्स निर्धारकों की गणना करके हल किया जा सकता है। इस पद्धति का उपयोग करते हुए, उन्होंने दिखाया कि समय O(1.657) में [[मोंटे कार्लो एल्गोरिथ्म]] द्वारा मनमाने ढंग से एन-वर्टेक्स ग्राफ़ में हैमिल्टनियन चक्र समस्या को कैसे हल किया जाए<sup>n</sup>); [[द्विदलीय ग्राफ]]़ के लिए इस एल्गोरिदम को बिग ओ नोटेशन#लिटिल-ओ नोटेशन(1.415) के अनुसार और बेहतर बनाया जा सकता है<sup>n</sup>).<ref>{{citation
 
एंड्रियास ब्योर्कलुंड ने हैमिल्टनियन चक्रों की संख्या की गणना करने की समस्या को कम करने के लिए समावेशन-बहिष्करण सिद्धांत का उपयोग करके चक्र कवर की गिनती की एक सरल गिनती समस्या को कम करने के लिए वैकल्पिक दृष्टिकोण प्रदान किया, जिसे कुछ मैट्रिक्स निर्धारकों की गणना करके हल किया जा सकता है। इस पद्धति का उपयोग करते हुए, उन्होंने दिखाया कि समय O(1.657<sup>''n''</sup>) में [[मोंटे कार्लो एल्गोरिथ्म]] द्वारा मनमाने ढंग से ''n-''शीर्ष ग्राफ़ में हैमिल्टनियन चक्र समस्या को कैसे हल किया जाए); [[द्विदलीय ग्राफ]] के लिए इस एल्गोरिदम को समय  o(1.415<sup>''n''</sup>) तक और बेहतर बनाया जा सकता है।<ref>{{citation
  | last = Björklund | first = Andreas
  | last = Björklund | first = Andreas
  | arxiv = 1008.0541
  | arxiv = 1008.0541
Line 60: Line 60:
  | year = 2010
  | year = 2010
  | 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 72: Line 73:
  | isbn = 978-3-540-73544-1| citeseerx = 10.1.1.219.1672
  | isbn = 978-3-540-73544-1| citeseerx = 10.1.1.219.1672
  }}.</ref>
  }}.</ref>
[[सैट सॉल्वर]] का उपयोग करके हैमिल्टनियन पथ और चक्र पाए जा सकते हैं।
[[सैट सॉल्वर]] का उपयोग करके हैमिल्टनियन पथ और चक्र पाए जा सकते हैं।


Line 88: Line 90:


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


* द्विदलीय ग्राफ,<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 99: Line 101:
  | 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 108: Line 110:
  | 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-जुड़े हुए 3-नियमित द्विदलीय ग्राफ़,<ref>{{citation
* 3-जुड़े हुए 3-नियमित द्विदलीय ग्राफ़,<ref>{{citation
  | last1 = Akiyama | first1 = Takanori
  | last1 = Akiyama | first1 = Takanori
Line 144: Line 146:
हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:
हालाँकि, ग्राफ़ के कुछ विशेष वर्गों के लिए, समस्या को बहुपद समय में हल किया जा सकता है:


* [[के-वर्टेक्स-कनेक्टेड ग्राफ़]] | 4-कनेक्टेड प्लेनर ग्राफ़ हमेशा W. T. टुटे के परिणाम के अनुसार हैमिल्टनियन होते हैं, और इन ग्राफ़ में हैमिल्टनियन चक्र खोजने का कम्प्यूटेशनल कार्य रैखिक समय में किया जा सकता है<ref>{{citation
* [[के-वर्टेक्स-कनेक्टेड ग्राफ़|के-शीर्ष-कनेक्टेड ग्राफ़]] | 4-कनेक्टेड प्लेनर ग्राफ़ हमेशा W. T. टुटे के परिणाम के अनुसार हैमिल्टनियन होते हैं, और इन ग्राफ़ में हैमिल्टनियन चक्र खोजने का कम्प्यूटेशनल कार्य रैखिक समय में किया जा सकता है<ref>{{citation
  | last1 = Chiba| first1 = Norishige
  | last1 = Chiba| first1 = Norishige
  | last2 = Nishizeki| first2 = Takao
  | last2 = Nishizeki| first2 = Takao

Revision as of 10:49, 4 July 2023

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

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

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

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

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

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

ऐसे ग्राफ़ में जिनमें सभी शीर्षों की डिग्री विषम होती है, हाथ मिलाना लेम्मा से संबंधित एक तर्क से पता चलता है कि किसी भी निश्चित किनारे के माध्यम से हैमिल्टनियन चक्रों की संख्या हमेशा सम होती है, इसलिए यदि एक हैमिल्टनियन चक्र दिया गया है, तो दूसरा भी मौजूद होना चाहिए।[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=209119’