संयुक्त गणित

ग्राफ सिद्धांत के अनुप्रयोग

प्लेनर रेखांकन

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

कहा जाता है कि दो रेखांकन होमियोमॉर्फिक हैं यदि दोनों को एक ही ग्राफ से किनारों के उपखंड द्वारा प्राप्त किया जा सकता है। उदाहरण के लिए, चित्रा 4 ए और चित्रा 4 बी में रेखांकन होमियोमॉर्फिक हैं।

K _{m, n} ग्राफ एक ग्राफ है जिसके लिए वर्टेक्स सेट को दो सबसेट में विभाजित किया जा सकता है, एक m कोने से और दूसरा n कोने से। एक ही उपसमुच्चय के किसी भी दो कोने अविकसित होते हैं, जबकि विभिन्न उपसमूह के किसी भी दो कोने आसन्न होते हैं। 1930 में पोलिश गणितज्ञ काज़िमिएरज़ कुराटोव्स्की ने निम्नलिखित प्रसिद्ध प्रमेय को सिद्ध किया:

ग्राफ जी होने के लिए एक ग्राफ जी के लिए एक आवश्यक और पर्याप्त शर्त यह है कि इसमें चित्र 5 में दिखाए गए K ₅ या K _3,3 में से एक सबग्राफ होम्योमोर्फिक शामिल नहीं है ।

ग्राफ G का एक प्रारंभिक संकुचन G का एक नया ग्राफ G _{1 में} परिवर्तन है, जैसे कि G के दो आसन्न कोने U और u को G ₁ में एक नए वर्टेक्स w से बदल दिया जाता है और W G ₁ से सभी वर्टिकल में आसन्न होता है। जो या तो either या G में समीप है। एक ग्राफ G * को G का संकुचन कहा जाता है यदि G * को G से प्राप्त किया जा सकता है जो प्रारंभिक संकुचन के अनुक्रम से प्राप्त किया जा सकता है। 1937 में जर्मन गणितज्ञ के। वैगनर के कारण प्लानेर ग्राफ का एक और लक्षण वर्णन है।

एक ग्राफ प्लानर है यदि और केवल यदि यह K ₅ या K _{3,3 के} लिए अनुबंधित नहीं है ।

चार-रंग नक्शा समस्या

एक सदी से भी अधिक समय तक चार रंगों के मानचित्र की समस्या का हल हर उस विश्लेषक को मिला जिसने यह प्रयास किया। समस्या ने मोबीस का ध्यान आकर्षित किया होगा, लेकिन इसका पहला लिखित संदर्भ 1852 में ऑगस्टस डी मॉर्गन के एक छात्र फ्रांसिस गुथ्री के एक पत्र से लगता है।

समस्या यह है कि प्लानेर मैप्स की चिंता करता है - यानी प्लेन के सबडिवीजन को नॉनवर्लेपिंग क्षेत्रों में सरल बंद वक्रों से घिरा हुआ। भौगोलिक मानचित्रों में इसे अनुभवजन्य रूप से देखा गया है, जितने विशेष मामलों में कोशिश की गई है, कि, क्षेत्रों को रंगने के लिए, अधिकतम चार रंगों की आवश्यकता होती है, ताकि एक सामान्य सीमा साझा करने वाले दो क्षेत्र हमेशा अलग-अलग रंग में हों, और में कुछ मामलों में कम से कम चार रंग आवश्यक हैं। (क्षेत्र जो केवल एक बिंदु पर मिलते हैं, जैसे संयुक्त राज्य अमेरिका में कोलोराडो और एरिज़ोना के राज्य, एक सामान्य सीमा नहीं मानी जाती है)। इस अनुभवजन्य अवलोकन की एक औपचारिकता का गठन "चार-रंग प्रमेय" कहा जाता है। समस्या यह साबित करने या असत्य साबित करने के लिए है कि यह हर प्लानर के नक्शे के लिए है। यह कि तीन रंग पर्याप्त नहीं होंगे, आसानी से प्रदर्शित होते हैं, जबकि पांच रंगों की पर्याप्तता 1890 में ब्रिटिश गणितज्ञ पीजे हेवुड ने साबित की थी।

1879 में, एक अंग्रेज ए बी केम्पे ने चार-रंग की समस्या के समाधान का प्रस्ताव रखा। हालांकि हेवुड ने दिखाया कि केम्पे का तर्क त्रुटिपूर्ण था, इसकी दो अवधारणाएँ बाद की जांच में फलदायी साबित हुईं। इनमें से एक, जिसे अपरिग्रह कहा जाता है, एक मानचित्र के निर्माण की असंभवता को सही ढंग से बताता है जिसमें हर चार कॉन्फ़िगरेशन अनुपस्थित हैं (इन कॉन्फ़िगरेशनों में दो पड़ोसियों के साथ एक क्षेत्र होता है, तीन में से एक, चार के साथ एक, और पांच से एक के साथ एक)। दूसरी अवधारणा, कि अतिसूक्ष्मता, इसका नाम केम्पे के वैध प्रमाण से लिया गया है कि यदि कोई ऐसा मानचित्र है जिसमें कम से कम पांच रंगों की आवश्यकता होती है और जिसमें चार (या तीन या दो) पड़ोसियों वाला क्षेत्र होता है, तो पांच के लिए एक मानचित्र होना चाहिए। क्षेत्रों की एक छोटी संख्या के लिए रंग। पांच पड़ोसियों के साथ एक क्षेत्र वाले नक्शे के पुनर्विकास को साबित करने के लिए केम्पे का प्रयास गलत था, लेकिन इसे 1976 में संयुक्त राज्य अमेरिका के केनेथ एपेल और वोल्फगैंग हेक द्वारा प्रकाशित एक प्रमाण में ठीक किया गया था। उनके प्रमाण ने कुछ आलोचनाओं को आकर्षित किया क्योंकि इसमें 1,936 अलग-अलग मामलों के मूल्यांकन की आवश्यकता थी, प्रत्येक में 500,000 तार्किक संचालन शामिल थे। Appel, Haken, और उनके सहयोगियों ने उन कार्यक्रमों को तैयार किया जिन्होंने इन विवरणों को संभालने के लिए एक बड़े डिजिटल कंप्यूटर के लिए संभव बनाया। कंप्यूटर को कार्य करने के लिए 1,000 घंटे से अधिक की आवश्यकता होती है, और परिणामस्वरूप औपचारिक प्रमाण कई सौ पृष्ठों लंबा होता है।

Eulerian चक्र और कोनिग्सबर्ग पुल समस्या

एक मल्टीग्राफ G में एक गैर-खाली सेट V (G) का वर्टिकल और एक सबसेट E (G) होता है जिसमें V (G) के अलग-अलग तत्वों के अलग-अलग युग्मों का सेट होता है, जिसमें प्रत्येक जोड़ी से जुड़ी आवृत्ति f attached 1 होती है। यदि आवृत्ति f के साथ युग्म (x ₁, x ₂) E (G) से संबंधित है, तो कोने x ₁ और x ₂ f किनारों से जुड़ जाते हैं।

मल्टीग्राफ जी का एक Eulerian चक्र एक बंद श्रृंखला है जिसमें प्रत्येक किनारे एक बार बिल्कुल दिखाई देता है। यूलर ने दिखाया कि एक मल्टीग्राफ के पास एक यूलरियन चक्र होता है अगर और केवल अगर यह जुड़ा हुआ है (पृथक बिंदुओं के अलावा) और विषम डिग्री के कोने की संख्या या तो शून्य या दो है।

यह समस्या पहले निम्नलिखित तरीके से उत्पन्न हुई। प्रागेल नदी, अपनी दो शाखाओं के संगम से बनी, कोनिग्सबर्ग शहर से गुजरती है और Kneiphof द्वीप के दोनों ओर बहती है। सात पुल थे, जैसा कि चित्र 6 ए में दिखाया गया है। शहरवासी आश्चर्यचकित थे कि क्या टहलने जाना और प्रत्येक पुल को एक बार और केवल एक बार पार करना संभव है। यह चित्र 6B में मल्टीग्राफ के लिए एक युलरियन चक्र खोजने के बराबर है। यूलर ने इसे असंभव दिखाया क्योंकि विषम क्रम के चार कोने हैं।