- 0 विषम शीर्ष: एक परिपथ, किसी भी शीर्ष से चलकर उसी पर वापस
- 2 विषम शीर्ष: एक से दूसरे तक एक पथ
- 4 या अधिक: एक लकीर में असंभव
ऑयलर पथ खोजक
क्या आप संत निकोलस का घर पेंसिल उठाए बिना और किसी रेखा पर दोबारा चले बिना बना सकते हैं? बना सकते हैं, पर तभी जब नीचे के दो कोनों में से किसी एक से शुरू करें, और हर कोने से 44 तरीक़े हैं। कारण है शीर्ष की घात, यानी वहाँ मिलने वाली रेखाओं की संख्या: पेंसिल जब भी किसी शीर्ष से गुज़रती है, उसकी दो रेखाएँ ख़र्च कर देती है। लेओनार्ड ऑयलर ने यह नियम 1736 में कोनिग्सबर्ग के सात पुलों से निकाला था। कोई आकृति ख़ुद बनाएँ, देखें कि आप कहाँ और क्यों अटकते हैं, संकेत माँगें, या किसी कलनविधि को उसे बनाते देखें। कोई आकृति चुनें और उसे बनाएँ: शुरू करने के लिए किसी शीर्ष पर टैप करें, फिर क्रम से किनारों या अगले शीर्षों पर टैप करें, या शीर्ष से शीर्ष तक खींचें। हर किनारा केवल एक बार ही चल सकता है। पीछे एक चाल वापस लेता है, संकेत अगला सुरक्षित किनारा दिखाता है, और हल करें फ्लूरी या हीरहोल्त्सर की कलनविधि को चरण दर चरण चलाता है। विषम शीर्ष भरे हुए दिखते हैं, और हर शीर्ष पर लगा अंक उसकी घात है। बनाएँ मोड में खाली जगह पर टैप करने से शीर्ष जुड़ता है और दो शीर्षों पर टैप करने से वे जुड़ जाते हैं, एक बार और टैप करने पर दूसरा किनारा बनता है; शीर्ष को खींचकर हटाया जा सकता है। मिटाएँ शीर्ष और किनारे हटाता है। जब विषम शीर्ष दो से अधिक हों, तो जोड़ें वे किनारे डाल देता है जिनसे आकृति एक ही लकीर में बन सके।
यह कैसे काम करता है
- कोई आकृति चुनें, जैसे कोनिग्सबर्ग के सात पुल, संत निकोलस का घर या कोई तारा, या रचें मोड में अपनी आकृति बनाएँ, जिसमें दो शीर्षों के बीच जितने चाहें उतने किनारे हों।
- शुरू करने के लिए किसी शीर्ष पर टैप करें, फिर क्रम से किनारों या शीर्षों पर टैप करें, या शीर्ष से शीर्ष तक खींचें। अटक जाएँ तो स्थिति पंक्ति कारण बताती है; पीछे एक चाल वापस लेता है और संकेत एक सुरक्षित किनारा दिखाता है।
- आकृति के नीचे घात नियम पढ़ें, असंभव आकृति में सुझाए गए किनारे जोड़ें, या हल करें दबाकर देखें कि फ्लूरी या हीरहोल्त्सर की कलनविधि उसे चरण दर चरण कैसे बनाती है।
विषम शीर्ष ही क्यों तय करते हैं
किसी शीर्ष से गुज़रने वाली लकीर एक रेखा से आती है और दूसरी रेखा से निकलती है, यानी वह उस शीर्ष की रेखाएँ जोड़े में ख़र्च करती है। कोई रेखा बिना जोड़े के केवल वहीं बच सकती है जहाँ लकीर शुरू या ख़त्म होती है। इसलिए विषम संख्या में रेखाओं वाला शीर्ष या तो आरंभ होगा या अंत। कोई विषम शीर्ष न हो तो लकीर वहीं ख़त्म होती है जहाँ से शुरू हुई थी: यह ऑयलर परिपथ है। दो हों तो वह एक से दूसरे तक जाती है: यह ऑयलर पथ है। चार या अधिक हों तो एक लकीर के लिए सिरे बहुत अधिक हो जाते हैं, और k विषम शीर्षों के लिए k/2 लकीरें चाहिए। कोनिग्सबर्ग में चार भूभाग थे, जिन पर पाँच, तीन, तीन और तीन पुल थे: चारों विषम, इसलिए कोई सैर हर पुल को एक बार पार नहीं कर सकती थी। इनमें से दो के बीच एक नया पुल होता तो सैर संभव हो जाती।
फ्लूरी और हीरहोल्त्सर की कलनविधियाँ
यह जान लेना कि आकृति बन सकती है, और उसे बना लेना, दो अलग बातें हैं: लापरवाह लकीर ख़ुद को उन्हीं रेखाओं से काट सकती है जिनकी उसे अभी ज़रूरत है। फ्लूरी की 1883 की कलनविधि इसे एक नियम से रोकती है: कभी किसी पुल को पार न करें, यानी ऐसी रेखा को नहीं जिसे हटाने पर बची रेखाएँ दो टुकड़ों में बँट जाएँ, बशर्ते कोई दूसरी रेखा हो। हीरहोल्त्सर की कलनविधि, जो 1873 में छपे एक शोधपत्र से आई, और तेज़ है: पहले जहाँ चाहें वहाँ तब तक चलें जब तक रास्ता बंद न हो (यह केवल आरंभ बिंदु पर हो सकता है), फिर चक्र के किसी ऐसे शीर्ष से, जिस पर अब भी खाली रेखाएँ हैं, एक और बंद फंदा चलकर उसे चक्र में जोड़ दें। इसका समय किनारों की संख्या के अनुपात में बढ़ता है, और कंप्यूटर इसी तरह ऑयलर पथ खोजते हैं।
अक्सर पूछे जाने वाले प्रश्न
ऑयलर पथ और ऑयलर परिपथ में क्या अंतर है?
दोनों ग्राफ़ के हर किनारे को ठीक एक बार चलते हैं। ऑयलर परिपथ वहीं ख़त्म होता है जहाँ से शुरू हुआ था; ऑयलर पथ कहीं और ख़त्म होता है। संबद्ध ग्राफ़ में परिपथ तब होता है जब हर शीर्ष की घात सम हो, और पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक से दूसरे तक जाता है।
कोनिग्सबर्ग के सात पुल एक-एक बार क्यों पार नहीं किए जा सकते?
हर भूभाग को शीर्ष और हर पुल को किनारा मानकर बनाइए। क्नाइपहोफ़ टापू पर पाँच पुल थे और बाक़ी तीन भूभागों पर तीन-तीन, इसलिए चारों शीर्ष विषम हैं। सैर केवल विषम शीर्ष पर ही शुरू या ख़त्म हो सकती है, और चार बहुत अधिक हैं। इनमें से दो के बीच एक पुल जोड़ने पर दो विषम शीर्ष बचते हैं और सैर संभव हो जाती है।
संत निकोलस का घर कितने तरीक़ों से बनाया जा सकता है?
नीचे के दोनों कोनों में से हर एक से 44, कुल 88, यदि अलग क्रम या अलग दिशा को अलग तरीक़ा गिनें। किसी और शीर्ष से यह नहीं बनता, क्योंकि विषम संख्या में रेखाएँ केवल इन्हीं दो कोनों पर हैं। ऐप छोटी आकृतियों के तरीक़े इसी ढंग से गिनता है।
ग्राफ़ में पुल क्या होता है?
ऐसा किनारा जिसे हटाने पर संबद्ध ग्राफ़ दो टुकड़ों में बँट जाए। जब तक कोई दूसरा विकल्प है, फ्लूरी की कलनविधि बचे हुए किनारों में से किसी पुल को कभी पार नहीं करती, क्योंकि आकृति का एक हिस्सा पीछे छूट जाएगा। इस ऐप में, पुल बहुत जल्दी पार करने से अटकी लकीर को बताया जाता है कि वह कौन-सा चरण था।
क्या दो शीर्षों के बीच एक से अधिक किनारे हो सकते हैं?
हाँ। समांतर किनारों वाले ग्राफ़ को बहुग्राफ़ कहते हैं, और कोनिग्सबर्ग को इसकी ज़रूरत है: क्नाइपहोफ़ को हर किनारे से दो-दो पुल जोड़ते थे। रचें मोड में दो शीर्षों पर फिर से टैप करके उनके बीच एक और किनारा जोड़ें, अधिकतम चार तक। घात नियम वैसे ही लागू होता है और हर किनारे को गिनता है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ