रेखांकन और नेटवर्ककोनिग्सबर्ग का पुल

ग्राफ़ और नेटवर्क के बारे में सोचने वाले पहले गणितज्ञों में से एक लियोनहार्ड यूलर थे

। बाल्टिक सागर के पास कोनिग्सबर्ग शहर के बारे में यूलर को एक पुरानी समस्या से घेर लिया गया था।

प्रागेल को कोनिग्सबर्ग को चार अलग-अलग हिस्सों में विभाजित किया गया है, जो सात पुलों से जुड़े हैं। क्या शहर के चारों ओर घूमना संभव है, एक बार में सभी पुलों को पार करना - लेकिन एक बार से अधिक नहीं? (आप कहीं भी शुरू कर सकते हैं और खत्म कर सकते हैं, जरूरी नहीं कि एक ही जगह पर हो।)

इन मानचित्रों पर आरेखण करके एक मान्य मार्ग खोजने का प्रयास करें:

Map 1

Map 2

Map 3

Map 4

Well done!

कोनिग्सबर्ग के मामले में एक वैध मार्ग खोजना असंभव प्रतीत होता है, लेकिन कुछ अन्य शहर काम करते हैं। यूलर एक सरल नियम खोजने में कामयाब रहा, जो कि किसी भी शहर में लागू हो सकता है, बिना बहुत संभावनाएं आज़माने के लिए - ग्राफ सिद्धांत का उपयोग करके।

सबसे पहले, हमें शहर के नक्शे को किनारों और कोने के साथ रेखांकन में बदलने की आवश्यकता है। प्रत्येक द्वीप या भूमि का क्षेत्र द्वारा दर्शाया गया ???

और दो क्षेत्रों को जोड़ने वाला प्रत्येक पुल एक संबंधित द्वारा दर्शाया गया है ??? ।

अब "हर पुल को एक बार पार करते समय एक शहर का दौरा" की समस्या "हर किनारे को एक बार ठीक करने के दौरान एक निरंतर स्ट्रोक के साथ एक ग्राफ खींचना" की समस्या बन गई है।

कागज पर, कुछ अलग रेखांकन के साथ आते हैं और फिर काम करने की कोशिश करते हैं कि किन लोगों को एक एकल, निरंतर स्ट्रोक के साथ खींचा जा सकता है।

बस शहर के नक्शे के लिए पहले की तरह, हम पाते हैं कि कुछ रेखांकन संभव है जबकि अन्य नहीं हैं। हमें यह समझने में मदद करने के लिए कि क्यों, हमें हर डिग्री

को उसकी डिग्री के साथ लेबल करना चाहिए। फिर हम विभिन्न तरीकों से रंगों को रंग सकते हैं, और एक पैटर्न प्रकट करने का प्रयास कर सकते हैं:

Value

Size

Prime Numbers

Even and Odd

These graphs are possible:

These graphs are not possible:

ग्राफ़ के लिए इन नंबरों की तुलना करना जो संभव हैं और जो संभव नहीं हैं, ऐसा लगता है कि एक ग्राफ खींचा जा सकता है अगर इसमें ???

। इस स्थिति को समझाया जा सकता है यदि हम ग्राफ में केवल एक शीर्ष को देखें:

Here you can see a single, magnified vertex in a graph.

If we draw the graph, we will eventually have an edge leading towards this vertex, and then another one leading away. This makes two edges meeting at the vertex.

Maybe the vertex is a crossing rather than a corner. In that case there will be another edge leading towards the vertex, and another edge leading away. Now we have four edges.

And in some graphs, there may even be a third pair of edges leading towards and away from the vertex. Now there are six edges.

Notice that, either way, there always is an even number of edges meeting at the vertex.

The only two exceptions are the vertices where the path starts, and where it ends – these two may have an odd number of edges. If the start and end point are the same, all vertices in the graph are even.

यदि आप कोनिग्सबर्ग के मानचित्र पर वापस स्क्रॉल करते हैं, तो आप पाएंगे कि विषम पुलों की संख्या के साथ दो से अधिक द्वीप हैं। इसलिए एक मार्ग जो हर पुल को एक बार पार करता है वह वास्तव में असंभव है - और यही लियोनार्ड यूलर ने खोजा था।

यूलर की खोज वास्तविक जीवन में विशेष रूप से उपयोगी नहीं लग सकती है, लेकिन रेखांकन कई अन्य भौगोलिक समस्याओं की नींव पर हैं, जैसे कि दो स्थानों के बीच निर्देशन। हम बाद में इनमें से अधिक अनुप्रयोगों की खोज करेंगे।