हैमिल्टोनियन पथ चेकर

हैमिल्टोनियन पथ (Hamiltonian Path) क्या है?

एक हैमिल्टोनियन पथ किसी ग्राफ में एक ऐसा पथ है जो प्रत्येक शीर्ष (vertex) से ठीक एक बार होकर गुजरता है। इस अवधारणा का नाम आयरिश गणितज्ञ सर विलियम रोवन हैमिल्टन के नाम पर रखा गया है, जिन्होंने 1857 में आइकोसियन गेम (Icosian game) का आविष्कार किया था — यह एक पहेली थी जिसमें खिलाड़ियों को डोडेकाहेड्रॉन ग्राफ के सभी 20 शीर्षों को पार करने वाला चक्र खोजना शामिल था। एक यूलरियन पथ के विपरीत, जो प्रत्येक किनारे से ठीक एक बार गुजरता है, एक हैमिल्टोनियन पथ विशेष रूप से शीर्षों से संबंधित है: प्रत्येक शीर्ष पर ठीक एक बार दौरा किया जाना चाहिए।

हैमिल्टोनियन पथ बनाम यूलरियन पथ

ये दो शास्त्रीय समस्याएं देखने में समान लगती हैं लेकिन जटिलता के मामले में मौलिक रूप से भिन्न हैं। एक यूलरियन पथ (प्रत्येक किनारे पर एक बार दौरा) का एक कुशल एल्गोरिदम समाधान है: हियरहोलज़र एल्गोरिदम O(E) समय में चलता है, और एक सरल नियम — विषम डिग्री के अधिकतम दो शीर्ष — तय करता है कि क्या कोई यूलरियन पथ मौजूद है। इसके विपरीत, यह तय करना कि क्या एक हैमिल्टोनियन पथ मौजूद है, एनपी-कम्पलीट (NP-complete) है। इसका मतलब है कि कोई कुशल पॉलिनोमियल-टाइम एल्गोरिदम ज्ञात नहीं है, और समस्या को सामान्य ग्राफ के लिए सबसे खराब स्थिति में घातीय (exponential) समय की आवश्यकता मानी जाती है।

हैमिल्टोनियन चक्र (Hamiltonian Cycle)

एक हैमिल्टोनियन चक्र (जिसे हैमिल्टोनियन सर्किट भी कहा जाता है) एक हैमिल्टोनियन पथ है जो अपने शुरुआती शीर्ष पर वापस लौटता है, जिससे एक बंद लूप बनता है। प्रत्येक ग्राफ जिसमें एक हैमिल्टोनियन चक्र होता है, उसमें एक हैमिल्टोनियन पथ भी होता है (बस एक किनारा हटा दें), लेकिन इसका उल्टा सच नहीं है। उदाहरण के लिए, एक साधारण पथ ग्राफ 1–2–3–4 में एक हैमिल्टोनियन पथ है लेकिन कोई हैमिल्टोनियन चक्र नहीं है, क्योंकि शीर्ष 4 बिना शीर्ष 2 या 3 पर दोबारा जाए वापस शीर्ष 1 पर नहीं लौट सकता है।

डिराक का प्रमेय (Dirac's Theorem - 1952)

डिराक का प्रमेय, जिसे 1952 में गैब्रियल एंड्रयू डिराक द्वारा सिद्ध किया गया था, हैमिल्टोनियन चक्र के अस्तित्व के लिए सबसे व्यापक रूप से उद्धृत पर्याप्त स्थिति प्रदान करता है: यदि n ≥ 3 शीर्षों वाले एक सरल अदिशित ग्राफ में प्रत्येक शीर्ष की डिग्री कम से कम n/2 है, तो ग्राफ में एक हैमिल्टोनियन चक्र होता है। यह स्थिति मजबूत है लेकिन आवश्यक नहीं है — कम-डिग्री वाले शीर्षों वाले कई ग्राफ में अभी भी हैमिल्टोनियन चक्र होते हैं। यह उपकरण पूर्ण बैकट्रैकिंग खोज चलाने से पहले एक त्वरित प्री-फ़िल्टर के रूप में डिराक की स्थिति की जांच करता है।

ओरे का प्रमेय (Ore's Theorem - 1960)

ओरे का प्रमेय, जिसे 1960 में ओयस्टीन ओरे द्वारा सिद्ध किया गया था, डिराक के परिणाम का एक सामान्यीकरण (generalization) है। यह बताता है: यदि n ≥ 3 शीर्षों वाले ग्राफ में गैर-आसन्न शीर्षों u और v की प्रत्येक जोड़ी के लिए, उनकी डिग्री का योग deg(u) + deg(v) ≥ n को संतुष्ट करता है, तो एक हैमिल्टोनियन चक्र मौजूद होता है। ओरे की स्थिति डिराक की तुलना में अधिक व्यापक है (डिराक को संतुष्ट करने वाला प्रत्येक ग्राफ ओरे को भी संतुष्ट करता है), इसलिए यह अधिक ग्राफों पर लागू होती है। दोनों पर्याप्त स्थितियां हैं, आवश्यक नहीं।

बैकट्रैकिंग एल्गोरिदम

यह चेकर हैमिल्टोनियन पथ खोजने के लिए बैकट्रैकिंग डेप्थ-फर्स्ट सर्च (backtracking depth-first search) का उपयोग करता है। एक चुने हुए शीर्ष से शुरू होकर, एल्गोरिदम एक अनदेखे आसन्न शीर्ष को जोड़कर वर्तमान पथ को विस्तारित करने का प्रयास करता है। यदि कोई वैध विस्तार मौजूद नहीं है और पथ अभी तक सभी शीर्षों तक नहीं पहुंचा है, तो यह बैकट्रैक करता है — अंतिम शीर्ष को हटा देता है और अगले उम्मीदवार का प्रयास करता है। जब पथ सभी n शीर्षों तक पहुँच जाता है, तो एक हैमिल्टोनियन पथ दर्ज किया जाता है। यदि अंतिम शीर्ष भी शुरुआत के आसन्न है, तो एक हैमिल्टोनियन चक्र मिल जाता है। ब्राउज़र के प्रदर्शन को सुरक्षित रखने के लिए, खोज 100,000 रिकर्सिव कॉल्स के बाद रुक जाती है।

हैमिल्टोनियन पथों के अनुप्रयोग

• ट्रैवलिंग सेल्समैन समस्या (TSP): एक भारित ग्राफ में सबसे छोटा हैमिल्टोनियन चक्र खोजना। भार रहित संस्करण हैमिल्टोनियन चक्र समस्या में बदल जाता है जिसे यहाँ हल किया गया है।
• डीएनए खंड असेंबली (DNA Fragment Assembly): छोटे डीएनए रीड्स को अनुक्रमित करने को एक ओवरलैप ग्राफ के माध्यम से हैमिल्टोनियन पथ खोजने के रूप में मॉडल किया जा सकता है।
• शेड्यूलिंग और अनुक्रमण: नौकरी शेड्यूलिंग जहां प्रत्येक कार्य एक बार किया जाना चाहिए और कार्य-दर-कार्य संक्रमण सीमित होते हैं, हैमिल्टोनियन पथ समस्या में मैप होते हैं।
• नाइट का दौरा (Knight's Tour): शतरंज के घोड़े का दौरा — शतरंज की बिसात के प्रत्येक वर्ग पर ठीक एक बार जाना — घोड़े की चाल वाले ग्राफ पर एक हैमिल्टोनियन पथ समस्या है।
• ग्रे कोड (Gray Codes): एक मानक बाइनरी ग्रे कोड n-आयामी हाइपरक्यूब ग्राफ पर एक हैमिल्टोनियन चक्र है।
• नेटवर्क राउटिंग: कुछ राउटिंग प्रोटोकॉल को प्रत्येक नोड पर एक बार जाने की आवश्यकता होती है; यह प्रश्न वास्तव में हैमिल्टोनियन पथ समस्या है।

NP-Completeness (एनपी-पूर्णता)

रिचर्ड कार्प के 1972 के ऐतिहासिक पेपर "Reducibility Among Combinatorial Problems" में हैमिल्टोनियन चक्र समस्या को 21 एनपी-कम्पलीट समस्याओं में से एक के रूप में सूचीबद्ध किया गया था। इसका मतलब है: (1) किसी भी प्रस्तावित समाधान को पॉलिनोमियल समय में सत्यापित किया जा सकता है, लेकिन (2) खोजने का कोई पॉलिनोमियल-टाइम एल्गोरिदम ज्ञात नहीं है। व्यावहारिक रूप से, लगभग 15 शीर्षों वाले ग्राफ के लिए बैकट्रैकिंग संभव है। बड़े ग्राफ के लिए, ह्यूरिस्टिक्स, डायनेमिक प्रोग्रामिंग (Held-Karp, O(2^n · n^2)), और अनुमानित एल्गोरिदम का उपयोग किया जाता है।

संदर्भ: क्लासिक ग्राफ के हैमिल्टोनियन गुण

ग्राफ	शीर्ष	हैमिल्टोनियन पथ	हैमिल्टोनियन चक्र	नोट
पूर्ण Kn (n≥2)	n	हाँ	हाँ (n≥3)	डिराक और ओरे को संतुष्ट करता है
चक्र Cn (n≥3)	n	हाँ	हाँ	यह स्वयं एक हैमिल्टोनियन चक्र है
पथ Pn	n	हाँ	नहीं	यह स्वयं एक हैमिल्टोनियन पथ है
पीटरसन ग्राफ (Petersen)	10	हाँ	नहीं	प्रसिद्ध प्रति-उदाहरण (counterexample)
डिस्कनेक्टेड ग्राफ	कोई भी	नहीं	नहीं	आवश्यक: ग्राफ का जुड़ा होना जरूरी है
पेड़ / ट्री (n>2)	n	केवल यदि पथ ग्राफ हो	नहीं	ट्री में चक्रों की अनुमति नहीं है