कोनिग्सबर्ग के सात पुल
18वीं शताब्दी में कोनिग्सबर्ग (Königsberg) शहर के लोग लंबे समय तक एक पहेली पर माथापच्ची करते रहे। शहर से प्रेगेल नदी बहती है, जो दो द्वीप बनाती है। इस नदी पर द्वीपों तक कुल सात पुल हैं। क्या रविवार की एक सैर में सभी पुलों को इस तरह पार किया जा सकता है कि हर पुल केवल एक बार पार हो? आइए देखें कि नदी पर पुल किस तरह बने थे:
क्या ऐसा हो सकता है कि हम अपनी सैर किसी जगह से शुरू करें और हर पुल को केवल एक बार पार करें? कोशिश करते हैं: नीचे बाईं ओर से शुरू करके ऊपर जाएँगे और फिर धीरे-धीरे दाईं ओर, इस तरह:
हम देखते हैं कि हमने सात में से छह पुल पार किए, एक पुल छूट गया। हम कोई दूसरा रास्ता आज़मा सकते हैं…
फिर से हमने अपने कोनिग्सबर्ग के सात में से केवल छह पुल पार किए। लगभग ऐसा लगता है कि एक सैर में हर पुल को केवल एक बार पार करना संभव नहीं है। एक दिन इस समस्या पर प्रसिद्ध गणितज्ञ लियोनहार्ड आयलर (Leonhard Euler) की नज़र पड़ी। प्रसिद्ध ही क्या, आयलर गणित के सच्चे दिग्गज थे, जिनके नाम पर आयलर संख्या भी रखी गई है। आयलर ने ठान लिया कि वे यह पहेली सुलझाएँगे। शुरुआत उन्होंने शहर के उन अलग-अलग द्वीपों या भागों पर नाम लिखने से की, जहाँ से और जहाँ तक पुल जाते थे:
अब आयलर ने यह तर्क दिया: यदि किसी द्वीप पर सम संख्या में पुल जाते हैं, तो इन पुलों को एक सैर में पार किया जा सकता है, चाहे हम कहीं से भी शुरू करें। सीधी-सी बात है: एक पुल से हम द्वीप पर आते हैं और दूसरे से चले जाते हैं, और पार करने के लिए बचे पुलों की संख्या दो कम हो जाती है। एक पुल से द्वीप पर आने और दूसरे से जाने के लिए हमें दो पुल चाहिए। यदि किसी द्वीप पर छह पुल जाते हैं, तो हम उस द्वीप पर तीन बार जाएँगे। उदाहरण के लिए, मान लीजिए द्वीप B पर चार पुल इस तरह जाते:
तब हम रविवार की एक सैर में सभी पुल पार कर सकते हैं, चाहे कहीं से भी शुरू करें। ख़ुद आज़माइए! चित्र में एक रास्ता दिखाया गया है। अब मान लीजिए कि द्वीप B पर द्वीप D से एक और पुल आता:
हम देखते हैं कि हमारा चुना हुआ रास्ता अब हमें सभी पुलों को एक-एक बार पार नहीं करने देता। हमें किसी पुल से द्वीप B पर लौटना पड़ता और फिर द्वीप D पर जाना पड़ता। पर हम दूसरा रास्ता चुन सकते हैं। हम अपनी सैर द्वीप B से शुरू कर सकते हैं, और तब सभी पुलों को एक-एक बार पार कर सकते हैं:
हमने सैर द्वीप B से शुरू की, ऊपर क्षेत्र A पर गए, फिर पुल से वापस B पर, क्षेत्र C पर, फिर वापस द्वीप B पर और अंत में द्वीप D पर। यानी यदि हम विषम संख्या में पुलों वाले द्वीप से शुरू करें, तो उसके सभी पुलों को एक-एक बार पार कर सकते हैं। या हम बिलकुल उलटा भी चल सकते हैं: द्वीप D से शुरू करके द्वीप B पर ख़त्म कर सकते हैं।
इस तरह आयलर ने ध्यान दिया कि सभी पुलों को एक-एक बार पार करना तभी संभव है, जब या तो सभी द्वीपों पर पुलों की संख्या सम हो, या फिर केवल दो द्वीप ऐसे हों जिन पर पुलों की संख्या विषम हो: विषम संख्या में पुलों वाले एक द्वीप से हम शुरू करेंगे और दूसरे पर ख़त्म करेंगे। बाकी सभी द्वीपों पर पुलों की संख्या सम होनी चाहिए। यदि हम कोनिग्सबर्ग के असली सात पुलों को देखें:
तो हम देखते हैं कि हर द्वीप पर पुलों की संख्या विषम है! द्वीप A पर 3 हैं, B पर 5, C पर 3 और D पर भी 3। इसलिए पहेली का कोई हल नहीं है: रविवार की एक सैर में सातों पुलों को एक-एक बार पार करना संभव नहीं है। यदि हम कोई भी एक पुल गिरा दें, तो पहेली का अचानक हल निकल आएगा। उदाहरण के लिए, द्वीपों B और C के बीच के पुलों में से एक को गिरा देते हैं:
हम देखते हैं कि अब अचानक द्वीप B पर 4 पुल हैं और द्वीप C पर दो पुल। द्वीपों A और D पर पुलों की संख्या नहीं बदली। अब हमारे पास सम संख्या में पुलों वाले दो द्वीप हैं और विषम संख्या में पुलों वाले दो द्वीप। यदि हम अपनी सैर विषम संख्या में पुलों वाले किसी एक द्वीप से शुरू करें, तो सभी पुलों को एक-एक बार पार कर सकते हैं। चित्र में हमने द्वीप A से शुरू किया और द्वीप D पर ख़त्म किया।
इस तरह लियोनहार्ड आयलर ने एक और प्रसिद्ध गणितीय समस्या हल की और कमोबेश उस विषय की नींव रखी, जिसे आज हम ग्राफ़ सिद्धांत कहते हैं। उनके सम्मान में ग्राफ़ सिद्धांत की भाषा में उस ग्राफ़ को, जिसके सभी किनारों (edges) को एक-एक बार पार किया जा सके, आयलर ग्राफ़ कहते हैं।