ऑयलर पथ और परिपथ की व्याख्या
कुछ आकृतियाँ एक ही लकीर में बन जाती हैं, पेंसिल उठाए बिना और किसी रेखा पर दोबारा चले बिना, और कुछ नहीं बनतीं, चाहे कितनी भी देर कोशिश करें। कोशिश की ज़रूरत भी नहीं: हर कोने पर रेखाएँ गिन लीजिए। यदि अधिक से अधिक दो कोनों पर विषम संख्या में रेखाएँ हों, तो आकृति बन सकती है, और लकीर को उन्हीं कोनों पर शुरू और ख़त्म होना होगा। लेओनार्ड ऑयलर ने 1736 में यह नियम खोजा और इसी से ग्राफ़ सिद्धांत की नींव रखी।
कोनिग्सबर्ग के सात पुल
प्रशा का शहर कोनिग्सबर्ग, आज का कालिनिनग्राद, प्रेगेल नदी के दोनों किनारों और उसमें बने दो टापुओं, क्नाइपहोफ़ और लोम्ज़े, पर बसा था। सात पुल चारों हिस्सों को जोड़ते थे: क्नाइपहोफ़ से हर किनारे तक दो-दो, दोनों टापुओं के बीच एक, और लोम्ज़े से हर किनारे तक एक-एक। नगरवासी सोचते थे कि क्या कोई सैर हर पुल को ठीक एक बार पार कर सकती है। ऑयलर ने 1735 में सेंट पीटर्सबर्ग की अकादमी को दिए और 1741 में छपे शोधपत्र में उत्तर दिया: नहीं कर सकती। उनका निर्णायक क़दम यह था कि शहर के हिस्सों और उनके बीच के पुलों के सिवा सब कुछ हटा दिया जाए, और ग्राफ़ यही करता है: हर भूभाग के लिए एक शीर्ष और हर पुल के लिए एक किनारा, और जहाँ दो पुल एक ही जगहों को जोड़ते हैं वहाँ दो किनारे।
घात नियम
शीर्ष की घात उस पर आने वाले किनारों की संख्या है। किसी शीर्ष से गुज़रने वाली लकीर एक किनारे से आती है और दूसरे किनारे से निकलती है, यानी वह उस शीर्ष के किनारे जोड़े में ख़र्च करती है। बिना जोड़े का किनारा केवल लकीर का पहला और आख़िरी शीर्ष ही रख सकता है। इसलिए विषम घात वाला शीर्ष लकीर का आरंभ या अंत होना ही चाहिए। क्नाइपहोफ़ पर पाँच पुल थे और बाक़ी तीन हिस्सों पर तीन-तीन: चार विषम शीर्ष, दो अधिक। सामान्यतः संबद्ध ग्राफ़ में ऑयलर परिपथ तब होता है, यानी वह लकीर जो वहीं ख़त्म हो जहाँ से शुरू हुई, जब हर घात सम हो, और ऑयलर पथ तब जब ठीक दो घातें विषम हों, एक से दूसरे तक। विषम शीर्षों की संख्या कभी एक या कोई और विषम संख्या नहीं होती: हर किनारा सभी घातों के योग में 2 जोड़ता है, इसलिए यह योग सम होता है। ऑयलर ने यह भी देखा था, और आज इसे हस्तमिलन प्रमेयिका कहते हैं।
यह नियम पर्याप्त क्यों है
ऑयलर ने दिखाया कि दो से अधिक विषम शीर्षों वाली आकृति नहीं बनाई जा सकती, और बिना प्रमाण के कहा कि हर दूसरी संबद्ध आकृति बनाई जा सकती है। प्रमाण कार्ल हीरहोल्त्सर से आया, जो जर्मन गणितज्ञ थे और 1871 में कम उम्र में चल बसे; उनका शोधपत्र 1873 में छपा। विषम शीर्ष हो तो वहाँ से, नहीं तो कहीं से भी शुरू करें और बिना चले किनारों पर जहाँ तक बने चलते जाएँ। चूँकि बाक़ी हर शीर्ष की घात सम है, आप केवल अंतिम शीर्ष पर ही अटक सकते हैं। यदि किनारे बचे हों तो उनमें से कुछ अब तक के रास्ते को छूते हैं, क्योंकि आकृति संबद्ध है। ऐसे शीर्ष से फिर चलें जब तक रास्ता बंद न हो, जो अब उसी शीर्ष पर लौटकर होता है, और उस फंदे को वहीं रास्ते में जोड़ दें। जब तक कोई किनारा न बचे, यही दोहराएँ। यह प्रमाण ही सबसे तेज़ कलनविधि भी है: हर किनारे को गिनी-चुनी बार ही देखा जाता है।
फ्लूरी की कलनविधि: अपने पुल मत जलाइए
जो आकृति बन सकती है, उस पर भी एक लकीर नाकाम हो सकती है। एक ही किनारे से जुड़े दो त्रिभुज लीजिए और पहले त्रिभुज के किसी कोने से शुरू कीजिए: यदि पहला पूरा होने से पहले दूसरे त्रिभुज में चले गए, तो कभी लौट नहीं पाएँगे। जोड़ने वाला वह किनारा एक पुल है: उसे हटाने पर आकृति दो हिस्सों में बँट जाती है। फ्लूरी की 1883 की कलनविधि एक नियम देती है: हर शीर्ष पर ऐसा किनारा चुनें जो बचे हुए किनारों के लिए पुल न हो, बशर्ते कोई और किनारा हो। इसे मानने पर हमेशा काम पूरा होता है। पुल की जाँच में समय लगता है, इसलिए फ्लूरी की कलनविधि हीरहोल्त्सर की तुलना में धीमी है, पर पेंसिल लेकर जिसका अनुसरण किया जा सके वह यही है, और ऐप का संकेत इसी का उपयोग करता है।
आकृति को सुधारना
k विषम शीर्षों वाली आकृति के लिए k/2 लकीरें चाहिए। उसे एक ही लकीर में बनाने के लिए ऐसे किनारे जोड़िए जो विषम शीर्षों को जोड़े में बाँध दें: हर नया किनारा दो विषम शीर्षों को सम बना देता है। k/2 − 1 किनारे जोड़ने पर दो विषम शीर्ष बचते हैं और पथ मिलता है; k/2 जोड़ने पर एक भी नहीं बचता और परिपथ मिलता है। कोनिग्सबर्ग में चारों हिस्सों में से किन्हीं दो के बीच एक और पुल होता तो सैर संभव हो जाती, और दो होते तो पूरा चक्कर भी लगाया जा सकता था। इतिहास ने कुछ ऐसा ही किया: दो पुल दूसरे विश्वयुद्ध में चले गए और दो की जगह आधुनिक सड़क बनी, और आज पुराने स्थानों पर खड़े पाँच पुल एक-एक बार पार किए जा सकते हैं, एक टापू से दूसरे टापू तक।
तरीक़े गिनना
संत निकोलस का घर, यानी दोनों विकर्णों और एक छत वाला वर्ग, इस पहेली का जर्मन बच्चों वाला रूप है: „Das ist das Haus vom Ni-ko-laus” में आठ अक्षर हैं, हर रेखा के लिए एक। इसके नीचे के दो कोने ही एकमात्र विषम शीर्ष हैं, और हर कोने से इसे बनाने के ठीक 44 तरीक़े हैं, कुल 88। दिष्ट ग्राफ़ों के लिए ऑयलर परिपथों की संख्या का एक सूत्र है, BEST प्रमेय, जिसका नाम दे ब्राइन, फ़ान आर्डेने-एरेनफ़ेस्ट, स्मिथ और टट पर है। साधारण ग्राफ़ों के लिए ऐसा कोई सूत्र ज्ञात नहीं है और गिनना सामान्यतः कठिन माना जाता है, इसलिए ऐप छोटी आकृतियों के लिए हर तरीक़ा आज़माकर गिनता है और उन चालों को छोड़ देता है जो आकृति को दो हिस्सों में बाँट देंगी।
ऑयलर पथ कहाँ काम आते हैं
बर्फ़ हटाने वाली गाड़ी, सफ़ाई गाड़ी या डाकिया हर गली से एक बार गुज़रकर लौटना चाहते हैं। यदि हर चौराहे पर गलियों की संख्या सम हो तो एक ऑयलर परिपथ काम कर देता है; नहीं तो कुछ गलियों से दो बार गुज़रना पड़ता है, और सबसे कम ख़र्च वाली गलियाँ चुनना चीनी डाकिया समस्या है, जिसे क्वान मेइगू ने 1962 में रखा था। पेन प्लॉटर या लेज़र कटर भी उपकरण उठाए बिना जितनी हो सकें उतनी रेखाएँ खींचकर समय बचाते हैं। जीनोम अनुक्रमण में डीएनए के लाखों छोटे टुकड़े दे ब्राइन ग्राफ़ में ऑयलर पथ खोजकर जोड़े जाते हैं, जहाँ हर टुकड़ा एक किनारा होता है। और यही नियम बताता है कि पहेली पुस्तिका के कौन-से रेखाचित्र आज़माने लायक़ हैं।
ख़ुद आज़माएँ
ऑयलर पथ खोजक खोलिए और बारह आकृतियाँ ख़ुद बनाइए, 1736 के और आज के कोनिग्सबर्ग से लेकर तारों, एक में एक वर्गों और एक घन तक, या समांतर किनारों के साथ अपनी आकृतियाँ रचिए। विषम शीर्ष भरे हुए दिखते हैं, हर शीर्ष अपनी घात दिखाता है, और आकृति के नीचे घात नियम बताता है कि क्या संभव है और कौन-से किनारे आकृति को सुधार देंगे। अटक जाएँ तो ऐप बताता है कि आपने ग़लत शीर्ष से शुरू किया या पुल बहुत जल्दी पार कर लिया, और वह कौन-सा चरण था। संकेत एक सुरक्षित किनारा देता है, और हल करें आकृति को फ्लूरी की कलनविधि से बनाता है, जिसमें पुल की जाँच दिखती है, या हीरहोल्त्सर की कलनविधि से, जिसमें हर जोड़ दिखता है।
अक्सर पूछे जाने वाले प्रश्न
क्या ऑयलर पथ और हैमिल्टन पथ एक ही हैं?
नहीं। ऑयलर पथ हर किनारे को एक बार चलता है और किसी शीर्ष पर कई बार जा सकता है; हैमिल्टन पथ हर शीर्ष पर एक बार जाता है और हर किनारे का उपयोग ज़रूरी नहीं। किसी ग्राफ़ में ऑयलर पथ है या नहीं, यह विषम शीर्ष गिनते ही पता चल जाता है, पर हैमिल्टन पथ के लिए कोई तेज़ जाँच ज्ञात नहीं है, और एक पथ खोजना कंप्यूटर विज्ञान की उत्कृष्ट कठिन समस्याओं में से एक है।
जब दो शीर्ष एक से अधिक किनारों से जुड़े हों तब भी घात नियम चलता है?
हाँ। हर किनारा अपने दोनों सिरों की घात में गिना जाता है, चाहे उन्हीं दो शीर्षों को कोई और किनारा जोड़ता हो या नहीं। कोनिग्सबर्ग ऐसा ही बहुग्राफ़ है, जिसमें क्नाइपहोफ़ से हर किनारे तक दो-दो पुल हैं। किसी शीर्ष से उसी तक जाने वाला किनारा, यानी फंदा, उसकी घात में 2 जोड़ता है और उसके विषम होने को कभी नहीं बदलता।
एकतरफ़ा सड़कों का क्या?
दिष्ट ग्राफ़ में हर किनारे की एक दिशा होती है, और नियम हर शीर्ष में आने वाले किनारों की तुलना बाहर जाने वालों से करता है। ऑयलर परिपथ तब होता है जब हर शीर्ष पर आने और जाने वाले किनारे बराबर हों और किनारे आपस में जुड़े हों, और ऑयलर पथ तब जब एक शीर्ष पर जाने वाला किनारा एक अधिक हो, दूसरे पर आने वाला एक अधिक हो, और बाक़ी सब संतुलित हों। तब पथ पहले से दूसरे तक जाता है।
क्या ठीक एक विषम शीर्ष वाली आकृति हो सकती है?
नहीं। सभी शीर्षों की घातों का योग किनारों की संख्या का दोगुना होता है, क्योंकि हर किनारे के दो सिरे होते हैं। यह योग सम है, इसलिए इसमें विषम घातों की संख्या भी सम होनी चाहिए: 0, 2, 4 इत्यादि, कभी 1 या 3 नहीं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
ऑयलर पथ खोजक खोलें