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

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

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

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

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

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

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

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

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

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

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

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

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

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