पथ
देखे गए नोड
हैमिल्टन चक्र
हैमिल्टन पथ

मोड

    लक्ष्य

    हैमिल्टन पथ और चक्र के बारे में और जानें

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

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

    यह कैसे काम करता है

    1. कोई ग्राफ़ चुनें, जैसे हैमिल्टन का द्वादशफलक, पीटरसन ग्राफ़ या घोड़े की सैर, या संपादन में अपना ग्राफ़ बनाएँ, और लक्ष्य के रूप में चक्र या पथ चुनें।
    2. खींचें में शुरू करने के लिए किसी शीर्ष पर क्लिक करें और फिर एक-एक कर पड़ोसियों पर। पीछे और पूर्ववत् एक कदम पीछे ले जाते हैं, और संकेत ऐसा अगला कदम दिखाता है जिससे अब भी पूरा किया जा सकता है।
    3. खोज में चलाएँ या चरण दबाकर बैकट्रैकिंग को मार्ग ढूँढ़ते देखें, छँटाई चालू-बंद करें, और तुलना दबाकर देखें कि हर रूप को कितने नोड चाहिए।

    हैमिल्टन बनाम ऑयलर

    ऑयलर पथ हर कोर का एक बार उपयोग करता है; हैमिल्टन पथ हर शीर्ष से एक बार गुज़रता है। सुनने में दोनों एक से लगते हैं, पर इनका व्यवहार बहुत अलग है। किसी संयोजित ग्राफ़ में ऑयलर पथ है या नहीं, यह विषम घात वाले शीर्ष गिनकर तय होता है, जैसा ऑयलर ने 1736 में दिखाया: ऐसे शीर्ष शून्य हों या दो, तब पथ होता है। हैमिल्टन पथ के लिए ऐसा कोई नियम ज्ञात नहीं है। किसी ग्राफ़ में हैमिल्टन चक्र है या नहीं, यह तय करना NP-पूर्ण है और रिचर्ड कार्प की 1972 की सूची की 21 समस्याओं में से एक है, इसलिए इसके लिए कोई तेज़ विधि मिल जाए तो हज़ारों अन्य कठिन समस्याओं की भी तेज़ विधियाँ मिल जाएँगी। जो मौजूद है वह कुछ शर्तें हैं जो कुछ ग्राफ़ों का फ़ैसला कर देती हैं। डिराक का 1952 का प्रमेय कहता है कि हर शीर्ष की घात कम से कम n/2 हो तो हैमिल्टन चक्र अवश्य है, और ओरे का 1960 का प्रमेय कहता है कि न जुड़े किन्हीं दो शीर्षों की घातों का योग कम से कम n हो तो भी। घात 1 वाला शीर्ष, कटाव-शीर्ष या अलग-अलग आकार के दो रंग-वर्ग चक्र को असंभव बना देते हैं।

    खोज कैसे काम करती है

    बैकट्रैकिंग एक-एक शीर्ष जोड़कर पथ बनाती है और अटकने पर आखिरी कदम वापस लेकर अगला पड़ोसी आज़माती है। अगर हैमिल्टन चक्र है तो वह हमेशा मिल जाता है, पर अधूरे पथों की संख्या चरघातांकी रूप से बढ़ सकती है। 5 × 5 जाली में, जिसमें हैमिल्टन चक्र नहीं है, सादी बैकट्रैकिंग निश्चय करने से पहले 153,745 नोड देखती है। दो जाँचें निराशाजनक पथों को जल्दी रोक देती हैं: जिस अनदेखे शीर्ष के दो से कम खाली पड़ोसी हों उसे अब चक्र में नहीं बैठाया जा सकता, और जब अनदेखे शीर्ष अलग-अलग टुकड़ों में बँट जाएँ तो कोई एक पथ उन्हें नहीं ढक सकता। दोनों के साथ वही प्रमाण 1,761 नोड लेता है। 1823 का वार्न्सडॉर्फ़ का नियम, जो पहले उस पड़ोसी को आज़माता है जिसके आगे सबसे कम चालें बची हों, कोने से शुरू होकर 8 × 8 की घोड़े की सैर 64 चालों में बिना एक भी गतिरोध के खोज लेता है।

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

    हैमिल्टन पथ और हैमिल्टन चक्र में क्या अंतर है?

    हैमिल्टन पथ ग्राफ़ के हर शीर्ष से ठीक एक बार गुज़रता है। हैमिल्टन चक्र भी यही करता है और फिर एक और कोर से होकर वहीं लौट आता है जहाँ से शुरू हुआ था, इसलिए वह अपने किसी भी शीर्ष से शुरू हो सकता है। जिस ग्राफ़ में हैमिल्टन चक्र है उसमें हैमिल्टन पथ भी है (चक्र की एक कोर हटा दीजिए), पर उल्टा सच नहीं: पीटरसन ग्राफ़ में हैमिल्टन पथ हैं और हैमिल्टन चक्र नहीं।

    क्या द्वादशफलक में हैमिल्टन चक्र है?

    हाँ, 30, जब हर चक्र को उसके आरंभ और दिशा से बेपरवाह एक बार गिना जाए। हैमिल्टन ने 1857 में इसे आइकोसियन खेल बना दिया — एक पट जिस पर चपटे किए गए द्वादशफलक के बीस कोने व्यंजनों से अंकित थे — और अधिकार 25 पाउंड में लंदन के खिलौना निर्माता John Jaques and Son को बेच दिए। ऐप में सब गिनें इन 30 चक्रों को लगभग 1,400 नोड में खोज लेती है।

    5 × 5 जाली में हैमिल्टन चक्र क्यों नहीं है?

    25 बिंदुओं को शतरंज की बिसात जैसे रंगिए: 13 को एक रंग मिलता है और 12 को दूसरा, और हर कदम दूसरे रंग पर जाता है। चक्र पूरे चक्कर में रंग बदलता रहता है, इसलिए उसे दोनों रंग बराबर चाहिए, जो 13 और 12 नहीं दे सकते। यही तर्क विषम संख्या में बिंदुओं वाली हर जाली पर, 5 × 5 या 7 × 7 बिसात के घोड़े पर (घोड़ा हमेशा खाने का रंग बदलता है) और हर्शल ग्राफ़ पर लागू होता है, जिसके दो वर्गों में 6 और 5 शीर्ष हैं। हैमिल्टन पथ फिर भी संभव है: वह बड़े रंग पर शुरू और खत्म होता है।

    वार्न्सडॉर्फ़ का नियम घोड़े की सैर कैसे खोजता है?

    एच. सी. फ़ॉन वार्न्सडॉर्फ़ ने 1823 में सुझाया कि घोड़े को हमेशा उस खाने पर ले जाएँ जहाँ से आगे सबसे कम चालें बचें। किनारों और कोनों के पास के खाने, जो आसानी से कट जाते हैं, इस तरह जल्दी देखे जाते हैं, जब तक घोड़ा वहाँ पहुँच सकता है। यह नियम अनुभव की बात है, गारंटी नहीं, और बराबरी की स्थिति किसी तरह तोड़नी पड़ती है, पर 8 × 8 बिसात पर यह प्रायः बिना पीछे लौटे सैर पूरी कर देता है। इस ऐप की तरह बैकट्रैकिंग के साथ मिलाने पर यह 5 × 5 से ऊपर खुली सैरें और 6 × 6 तथा 8 × 8 बिसातों पर बंद सैरें खोज लेता है।

    पूर्ण ग्राफ़ में कितने हैमिल्टन चक्र होते हैं?

    n ≥ 3 के लिए (n − 1)!/2। आरंभिक शीर्ष स्थिर कर दीजिए; बाकी n − 1 किसी भी क्रम में आ सकते हैं, और हर चक्र दो बार गिना जाता है, हर दिशा में एक बार। K₆ में 5!/2 = 60 और K₁₀ में 181,440 हैं। ये वही चक्कर हैं जिनमें से किसी फेरीवाले को चुनना होता है, और इसीलिए सब आज़माना इतनी जल्दी असंभव हो जाता है।

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

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

    एडिटर पर जाएँ