रेखांकन और नेटवर्कप्लेनर रेखांकन

यहां एक और पहेली है जो ग्राफ सिद्धांत से संबंधित है।

एक छोटे से गांव में तीन घर और तीन उपयोगिता संयंत्र हैं जो पानी, बिजली और गैस का उत्पादन करते हैं। हमें प्रत्येक पाठ्यक्रम को प्रत्येक उपयोगिता पौधों से जोड़ना है, लेकिन गांव के लेआउट के कारण, विभिन्न पाइपों और केबलों को पार करने की अनुमति नहीं है।

नीचे दी गई सभी यूटिलिटी कंपनियों में से प्रत्येक को, आपकी किसी भी पंक्तियों को जोड़ने के बिना, घरों को जोड़ने की कोशिश करें:

पहले की तरह ही कोनिग्सबर्ग पुल, आपको जल्दी पता चलता है कि यह समस्या भी असंभव है। ऐसा लगता है कि ओवरलैपिंग किनारों के बिना कुछ ग्राफ खींचे जा सकते हैं - इन्हें प्लानर ग्राफ कहा जाता है - लेकिन अन्य नहीं कर सकते।

K3 प्लानर है।

K4 ???

।

K5 ???

।

पूरा ग्राफ

K5 सबसे छोटा ग्राफ है जो प्लानेर नहीं है। कोई अन्य ग्राफ़ जिसमें सम्‍मिलित है K5 किसी तरह से सबग्राफ के रूप में भी प्लानर नहीं है। यह भी शामिल है K6 , K7 , और सभी बड़े पूर्ण रेखांकन।

तीन उपयोगिताओं पहेली में ग्राफ द्विदलीय ग्राफ है

K3,3 । यह पता चला है कि किसी भी गैर-प्लानर ग्राफ में या तो एक होना चाहिए K5 या ए K3,3 (या इन दो रेखांकन का एक उपखंड ) एक उपसमूह के रूप में। इसे कुराटोस्की की प्रमेय कहा जाता है ।

planarity

Well done!

यह एक प्लानर ग्राफ है, लेकिन

कोने को खुरच दिया गया है। कोने को फिर से व्यवस्थित करें ताकि किनारों में से कोई भी ओवरलैप न हो।

यूलर का फॉर्मूला

सभी प्लेन ग्राफ उन विमानों को विभाजित करते हैं जिन्हें वे कई क्षेत्रों में खींचते हैं, जिन्हें चेहरे कहा जाता है ।

लम्बवत चेहरे किनारों 11 वृतियाँ + चेहरे

लम्बवत चेहरे किनारों 15 वर्टिकल + फेस

चक्कर चेहरे किनारों 25 वर्टिस + फेस

इन संख्याओं की तुलना करते समय, आप देखेंगे कि किनारों की संख्या हमेशा ???

फलकों की संख्या के साथ साथ कोने की संख्या की तुलना में दूसरे शब्दों में, एफ + वी = E + 1. इस परिणाम को Euler का समीकरण कहा जाता है और इसका नाम उसी गणितज्ञ के नाम पर रखा गया है जिसने कोनिग्सबर्ग ब्रिजेस समस्या को हल किया।

दुर्भाग्य से, अनंत रूप से कई ग्राफ हैं और हम यह देखने के लिए हर एक की जांच नहीं कर सकते हैं कि क्या यूलर का समीकरण काम करता है। इसके बजाय हम एक सरल प्रमाण

खोजने की कोशिश कर सकते हैं जो किसी भी ग्राफ के लिए काम करता है ...

0 + 1 = 0 + 1

The simplest graph consists of a single vertex. We can easily check that Euler’s equation works.

Let us add a new vertex to our graph. We also have to add an edge, and Euler’s equation still works.

If we want to add a third vertex to the graph we have two possibilities. We could create a small triangle: this adds one vertex, one face and two edges, so Euler’s equation still works.

Instead we could simply extend the line by one: this adds one vertex and one edge, and Euler’s equation works.

Let’s keep going: if we now create a quadrilateral we add one vertex, two edges and one face. Euler’s equation still works.

किसी भी (परिमित) ग्राफ का निर्माण एक शीर्ष के साथ शुरू करके और एक-एक करके अधिक शीर्ष जोड़कर किया जा सकता है। हमने दिखाया है कि, जो भी हम नए कोने जोड़ते हैं, यूलर का समीकरण मान्य है। इसलिए यह सभी ग्राफ के लिए मान्य है।

हमने जिस प्रक्रिया का उपयोग किया है उसे गणितीय प्रेरण कहा जाता है। यह बहुत से मामलों में परिणाम साबित करने के लिए एक बहुत ही उपयोगी तकनीक है, बस सबसे सरल मामले से शुरू करके, और यह दिखाते हुए कि अधिक जटिल मामलों का निर्माण करते समय परिणाम हर कदम पर होता है।

कई प्लानर रेखांकन बहुत बहुकोणीय आकृति

का जाल, बहुभुज चेहरों के साथ तीन आयामी आकार के समान दिखाई। यदि हम पॉलीहेड्रा को लोचदार बैंड से बना मानते हैं, तो हम उन्हें सपाट होने तक कल्पना कर सकते हैं, जब तक कि वे फ्लैट नहीं हो जाते, प्लैनर ग्राफ:

इसका अर्थ है कि हम यूलर के फार्मूले का उपयोग न केवल प्लानर ग्राफ के लिए, बल्कि सभी पॉलीहेड्रा के लिए भी कर सकते हैं - एक छोटे अंतर के साथ। पॉलीहेड्रा को रेखांकन में बदलने पर, चेहरों में से एक गायब हो जाता है: पॉलीहेड्रा का सबसे ऊपरी चेहरा "बाहर" बन जाता है; रेखांकन के।

दूसरे शब्दों में, यदि आप की संख्या गिनते हैं किनारों , चेहरे और किसी भी पॉलीहेड्रॉन के कोने , आप पाएंगे एफ + वी = ई + ।

विंशतिफलक 20 चेहरे 12 चक्कर 30 किनारों

Rhombicosidodecahedron 62 चेहरे 60 चक्कर 120 किनारों

कटे हुए इकोसाहेड्रॉन 32 चेहरे (12 काले, 20 सफेद) 60 चक्कर 90 किनारों