हैमिल्टन पथ और चक्र की व्याख्या

पाँच बिंदु गोलाई में बनाइए, हर एक को उसके दोनों पड़ोसियों से जोड़िए, और आप हर बिंदु से एक बार गुज़रते हुए चक्कर लगाकर घर लौट सकते हैं: यही हैमिल्टन चक्र है। कुछ कोरें जोड़िए या हटाइए और सवाल हैरान कर देने वाली हद तक कठिन हो जाता है। किसी ग्राफ़ में ऐसा चक्र है या नहीं, यह उन सबसे प्रसिद्ध समस्याओं में है जिनका उत्तर कोई भी कंप्यूटर अब तक हर ग्राफ़ के लिए तेज़ी से नहीं दे पाता।

चपटा किया हुआ द्वादशफलक, जिसके बीस कोने व्यंजनों से अंकित हैं और उन सब से होकर जाता एक हैमिल्टन चक्र चमकीली रेखा में खिंचा है, तथा जहाँ खोज पीछे लौटी वहाँ एक लाल बिंदीदार कोर है
चपटा किया हुआ द्वादशफलक, जिसके बीस कोने व्यंजनों से अंकित हैं और उन सब से होकर जाता एक हैमिल्टन चक्र चमकीली रेखा में खिंचा है, तथा जहाँ खोज पीछे लौटी वहाँ एक लाल बिंदीदार कोर है

हर शीर्ष एक बार

ग्राफ़ बिंदुओं का समुच्चय है जिन्हें शीर्ष कहते हैं, और ये रेखाओं से जुड़े होते हैं जिन्हें कोर कहते हैं। हैमिल्टन पथ कोरों पर चलता है और हर शीर्ष से ठीक एक बार गुज़रता है; हैमिल्टन चक्र इसके अलावा वहीं लौट आता है जहाँ से चला था, इसलिए उसमें कोरें उतनी ही होती हैं जितने शीर्ष। जिस ग्राफ़ में हैमिल्टन चक्र हो उसे हैमिल्टन ग्राफ़ कहते हैं। दिए गए मार्ग को जाँचना आसान है: शीर्ष गिनिए और हर कदम देखिए। कठिन काम है कोई एक मार्ग खोजना, या यह दिखाना कि कोई मार्ग है ही नहीं, क्योंकि शीर्षों को देखने के क्रमों की संख्या n! की तरह बढ़ती है — 20 शीर्षों पर ही 2.4 × 10¹⁸।

हैमिल्टन का आइकोसियन खेल

चतुष्कोणों (क्वाटरनियन) की खोज करने वाले आयरिश गणितज्ञ विलियम रोवन हैमिल्टन ने 1857 में आइकोसियन खेल बनाया। उसके पट पर समतल में चपटा किया गया द्वादशफलक दिखता था, जिसके बीस कोने व्यंजनों से अंकित थे, और मुख्य काम था 1 से 20 तक अंकित खूँटियाँ कोनों पर इस तरह लगाना कि क्रमागत संख्याएँ, तथा 20 और 1, कोरों से जुड़ी हों। हैमिल्टन ने अधिकार 25 पाउंड में लंदन के खिलौना निर्माता John Jaques and Son को बेच दिए, जिसने इसे 1859 में निकाला; यह कम बिका। पहेली के 30 हल हैं, जब चक्र को उसके आरंभ और दिशा से बेपरवाह एक बार गिना जाए। सवाल खुद नया नहीं था: थॉमस किर्कमैन ने 1855 में रॉयल सोसाइटी को भेजे एक लेख में पूछा था कि किन बहुफलकों में सभी कोनों से होकर चक्र होता है, और एक ऐसा बहुफलक दिखाया था जिसमें नहीं होता।

घोड़े की सैर

घोड़े की सैर में शतरंज के घोड़े को इस तरह चलाया जाता है कि वह हर खाने पर ठीक एक बार उतरे: यह उस ग्राफ़ में हैमिल्टन पथ है जिसके शीर्ष खाने हैं और कोरें घोड़े की चालें। बंद सैर आरंभ से घोड़े की एक चाल की दूरी पर खत्म होती है, यानी वह हैमिल्टन चक्र है। शतरंज खेलने वाले ऐसी पहेलियाँ एक हज़ार साल से भी पहले रखते थे, और ऑयलर ने 1759 के एक लेख में इनका अध्ययन किया। 1823 में एच. सी. फ़ॉन वार्न्सडॉर्फ़ ने सुझाया कि हमेशा उस खाने पर जाएँ जहाँ से आगे सबसे कम चालें बचें; यह सरल नियम 8 × 8 बिसात की सैर प्रायः बिना पीछे लौटे पूरी कर देता है। घोड़ा हमेशा खाने का रंग बदलता है, इसलिए बंद सैर के लिए हल्के और गहरे खाने बराबर चाहिए, जिससे विषम संख्या में खानों वाली बिसातें बाहर हो जाती हैं। एलन श्वेंक ने 1991 में ठीक-ठीक बताया कि किन आयताकार बिसातों पर बंद सैर होती है; वर्गाकार बिसातों में 6 या उससे बड़ी सम भुजा वाली हर बिसात पर होती है। साधारण शतरंज की बिसात पर 13,267,364,410,532 बंद सैरें हैं, जिन्हें ब्रेंडन मैक्के ने 1997 में गिना।

बिना हैमिल्टन चक्र वाले ग्राफ़

चक्र न होने के सबसे तेज़ प्रमाण गिनती के तर्क हैं। यदि शीर्षों को दो रंगों में इस तरह रंगा जा सके कि हर कोर अलग-अलग रंगों को जोड़े, तो चक्र बारी-बारी चलता है और उसे हर रंग के बराबर शीर्ष चाहिए; 5 × 5 जाली में एक रंग के 13 और दूसरे के 12 हैं, इसलिए उसमें हैमिल्टन चक्र नहीं है। जिस कटाव-शीर्ष को हटाने पर ग्राफ़ बँट जाता है, उससे दो बार गुज़रना पड़ेगा, और घात 1 वाले शीर्ष से तो गुज़रा ही नहीं जा सकता। कुछ ग्राफ़ इन सब तर्कों से बच निकलते हैं। यूलियुस पीटरसन द्वारा 1898 में प्रकाशित पीटरसन ग्राफ़ में घात 3 वाले 10 शीर्ष हैं और हैमिल्टन चक्र नहीं, फिर भी कोई भी एक शीर्ष हटा दें तो बचा ग्राफ़ हैमिल्टन चक्र वाला होता है; यह सबसे छोटा ऐसा हाइपोहैमिल्टन ग्राफ़ है। हर्शल ग्राफ़, जिसका नाम अलेक्ज़ेंडर स्टुअर्ट हर्शल के नाम पर है जिन्होंने 1862 में आइकोसियन खेल पर लिखा, में 11 शीर्ष और 18 कोरें हैं और यह नौ चतुर्भुज फलकों वाले एक बहुफलक का ग्राफ़ है। इससे कम कोनों वाले किसी बहुफलक में हैमिल्टन चक्र की कमी नहीं है। 1884 में पीटर गथ्री टेट ने अनुमान लगाया कि हर उस बहुफलक में हैमिल्टन चक्र होता है जिसके हर कोने पर तीन कोरें मिलती हैं; डब्ल्यू. टी. टट ने 1946 में 46 शीर्षों का प्रतिउदाहरण खोज निकाला।

चक्र सुनिश्चित करने वाली शर्तें

यदि ग्राफ़ में बहुत सी कोरें हों तो हैमिल्टन चक्र निश्चित है। गैब्रिएल डिराक ने 1952 में सिद्ध किया कि n ≥ 3 शीर्षों वाले जिस ग्राफ़ में हर शीर्ष की घात कम से कम n/2 हो उसमें हैमिल्टन चक्र होता है, और ओइस्टाइन ओरे ने 1960 में शर्त ढीली कर दी: इतना काफ़ी है कि न जुड़े किन्हीं दो शीर्षों की घातों का योग हमेशा कम से कम n हो। दोनों शर्तें केवल एक दिशा में काम करती हैं। 100 शीर्षों का सादा छल्ला हर जगह घात 2 वाला है, 50 से कहीं कम, फिर भी वह स्वयं एक हैमिल्टन चक्र है। कुल तस्वीर यही है: पर्याप्त शर्तें हैं और असफलता के कारण हैं, और इनके बीच ग्राफ़ों का एक विशाल क्षेत्र है जिसका फ़ैसला केवल खोज कर सकती है।

कोई तेज़ जाँच क्यों ज्ञात नहीं है

किसी ग्राफ़ में हैमिल्टन चक्र है या नहीं, यह तय करना NP-पूर्ण है; यह रिचर्ड कार्प की 1972 की सूची की 21 समस्याओं में से एक थी। जो विधि इसे हर ग्राफ़ के लिए तेज़ी से हल कर दे वह हज़ारों अन्य समस्याओं को भी तेज़ी से हल कर देगी और P बनाम NP का सवाल भी सुलझा देगी। हर कोर का एक बार उपयोग करने वाले ऑयलर पथ से तुलना चौंकाने वाली है: ऑयलर ने 1736 में दिखाया कि विषम घात वाले शीर्ष गिनना उस सवाल को तुरंत सुलझा देता है। हैमिल्टन चक्र के लिए सबसे अच्छी यथार्थ विधियाँ अब भी चरघातांकी समय लेती हैं। शीर्षों के सभी उपसमुच्चयों पर गतिक प्रोग्रामिंग, जिसे रिचर्ड बेलमैन तथा माइकल हेल्ड और रिचर्ड कार्प ने 1962 में खोजा, लगभग n² × 2ⁿ चरण लेती है, और आंद्रेयास ब्यॉर्क्लुंड की 2010 की यादृच्छिक विधि लगभग 1.657ⁿ। व्यवहार में अच्छी छँटाई वाली बैकट्रैकिंग कुछ दर्जन शीर्षों के ग्राफ़ संभाल लेती है, और सबसे छोटा हैमिल्टन चक्र खोजने वाली फेरीवाले की समस्या इसी सवाल का भारित रूप है।

ग्रे कोड और अतिघन

0 से 7 तक की संख्याएँ 3-बिट कोड के रूप में लिखिए और दो कोडों को तब जोड़िए जब उनमें ठीक एक बिट का अंतर हो: परिणाम एक घन का ग्राफ़ है। उसमें से गुज़रता एक हैमिल्टन चक्र, जैसे 000, 001, 011, 010, 110, 111, 101, 100, आठों कोडों को इस तरह क्रम में रखता है कि हर कोड अपने पिछले से केवल एक बिट में अलग हो। ऐसी सूची ही ग्रे कोड है, जिसका नाम बेल लैब्स के फ़्रैंक ग्रे के नाम पर है, जिन्होंने इसे 1947 में दायर एक पेटेंट में वर्णित किया। हर अतिघन में एक ऐसी सूची होती है: एक बिट कम वाले कोड लिखिए, फिर वही सूची उल्टी लिखिए, और पहले आधे के आगे 0 तथा दूसरे आधे के आगे 1 लगा दीजिए। घूर्णी एनकोडर ग्रे कोड इसलिए उपयोग करते हैं ताकि दो स्थितियों के बीच लिया गया पाठ कभी एक कदम से अधिक ग़लत न हो। घन में 6 हैमिल्टन चक्र हैं और 4-बिट अतिघन में 1,344।

खुद आज़माइए

हैमिल्टन की पहेली खुद आज़माने के लिए हैमिल्टन पथ एक्सप्लोरर खोलिए, जहाँ बिंदीदार छल्ले दिखाते हैं कि आगे कहाँ जा सकते हैं; या खोज पर जाइए और बैकट्रैकिंग को काम करते देखिए: पथ बढ़ता है, लाल बिंदीदार रेखाएँ लौटने की जगह दिखाती हैं, और स्तंभ पथ की लंबाई के अनुसार नोड गिनते हैं। गतिरोध जाँच, संयोजकता जाँच और वार्न्सडॉर्फ़ क्रम चालू-बंद कीजिए, तुलना कीजिए कि हर एक को कितने नोड चाहिए, किसी छोटे ग्राफ़ के सारे चक्र गिनिए, या अपना ग्राफ़ बनाकर देखिए कि कौन-सी तेज़ जाँचें लागू होती हैं।

अक्सर पूछे जाने वाले प्रश्न

क्या ऑयलर परिपथ वाला ग्राफ़ हैमिल्टन ग्राफ़ भी होता है, या उल्टा?

दोनों में से कोई दूसरे से नहीं निकलता। तितली, यानी एक शीर्ष साझा करते दो त्रिभुज, में ऑयलर परिपथ है क्योंकि हर घात सम है, पर हैमिल्टन चक्र नहीं, क्योंकि साझा शीर्ष से दो बार गुज़रना पड़ेगा। पूर्ण ग्राफ़ K₄ में हैमिल्टन चक्र हैं, पर चारों शीर्षों की घात 3 है, इसलिए उसमें ऑयलर परिपथ नहीं है।

क्या कंप्यूटर सारे क्रम आज़मा नहीं सकता?

केवल छोटे ग्राफ़ों में। n शीर्षों के n! क्रम होते हैं, 20 के लिए लगभग 2.4 × 10¹⁸। बैकट्रैकिंग कहीं बेहतर करती है, क्योंकि वह केवल कोरों पर चलती है और अटकते ही अधूरा पथ छोड़ देती है: वह 20 शीर्षों वाले द्वादशफलक के सारे 30 चक्र लगभग 1,400 चरणों में खोज लेती है। फिर भी कुछ ग्राफ़ों में अधूरे पथों की संख्या चरघातांकी रूप से बढ़ती है, और ऐसी कोई विधि ज्ञात नहीं जो हर ग्राफ़ में इससे बचा सके।

क्या हैमिल्टन पथ की समस्या चक्र की समस्या से आसान है?

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

5 × 5 बिसात पर घोड़े की सैर कोने वाले रंग से ही क्यों शुरू होनी चाहिए?

25 खानों में से 13 कोनों के रंग के हैं और 12 दूसरे रंग के, और घोड़ा हर चाल पर रंग बदलता है। 25 खानों की सैर में रंग बारी-बारी आते हैं, इसलिए वह उस रंग पर शुरू और खत्म होती है जिसके खाने अधिक हैं। ऐप 5 × 5 बिसात की सभी 1,728 खुली सैरें खोज लेता है, यानी 864 यदि सैर और उसका उल्टा क्रम एक गिना जाए, और हर सैर कोने वाले रंग के खाने पर शुरू और खत्म होती है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

हैमिल्टन पथ एक्सप्लोरर खोलें