ग्राफ के मूल सिद्धांत और संयोजकता
ग्राफ सिद्धांत के मूल सिद्धांत ग्राफ, उनके बुनियादी मापदंडों और संयोजकता तथा अनुक्रमण की धारणाओं का परिचय देते हैं जो यह वर्णन करते हैं कि एक ग्राफ कैसे एक साथ जुड़ा रहता है।
Definition
एक ग्राफ में शीर्षों का एक समुच्चय और शीर्षों के युग्मों को जोड़ने वाले किनारों का एक समुच्चय होता है; संयोजकता उस सीमा को मापती है जिस तक शीर्षों या किनारों को हटाने पर ग्राफ एक ही टुकड़े में रहता है।
Scope
यह विषय ग्राफ और डिग्राफ की परिभाषाओं, डिग्री और हैंडशेकिंग लेम्मा, सबग्राफ और आइसोमोर्फिज्म, वॉक, पाथ और साइकिल, संयोजकता और घटकों, और यूलरियन और हैमिल्टनियन ग्राफ के शास्त्रीय लक्षण वर्णन को शामिल करता है। यह ग्राफ सिद्धांत में उपयोग की जाने वाली शब्दावली और मुख्य संरचनात्मक परिणामों को स्थापित करता है।
Core questions
- एक ग्राफ के मूल पैरामीटर - क्रम, आकार और डिग्री - क्या हैं?
- एक ग्राफ कब जुड़ा होता है, और विलोपन के प्रति उसकी संयोजकता कितनी मजबूत होती है?
- एक ग्राफ कब हर किनारे का ठीक एक बार उपयोग करके एक बंद वॉक को स्वीकार करता है?
- पाथ और साइकिल पहुंच और संरचना को कैसे एन्कोड करते हैं?
Key concepts
- शीर्ष, किनारे और डिग्री
- वॉक, पाथ और साइकिल
- जुड़े हुए घटक
- शीर्ष और किनारे की संयोजकता
- यूलरियन परिपथ
- हैमिल्टनियन साइकिल
Key theories
- हैंडशेकिंग लेम्मा
- किसी भी ग्राफ में सभी शीर्ष डिग्रियों का योग किनारों की संख्या के दोगुने के बराबर होता है, जिसका तुरंत अर्थ है कि विषम डिग्री वाले शीर्षों की संख्या सम होती है।
- यूलरियन परिपथों पर यूलर का प्रमेय
- एक जुड़े हुए ग्राफ में एक बंद वॉक होता है जो हर किनारे को ठीक एक बार पार करता है यदि और केवल यदि हर शीर्ष की डिग्री सम हो, यह परिणाम कोनिग्सबर्ग पुलों के यूलर के समाधान का आधार है।
Clinical relevance
संयोजकता विश्लेषण नेटवर्क विश्वसनीयता, रूटिंग और दोष-सहिष्णु संचार और परिवहन प्रणालियों के डिजाइन के लिए केंद्रीय है, जबकि यूलरियन और हैमिल्टनियन संरचनाएं रूटिंग और अनुक्रमण समस्याओं में उत्पन्न होती हैं।
History
यूलर के 1736 के कोनिग्सबर्ग पेपर ने ग्राफ अनुक्रमण की शुरुआत की; मेंगर के 1927 के प्रमेय ने संयोजकता और असंयुक्त पाथों के बीच मौलिक द्वैत दिया जो आधुनिक सिद्धांत को आधार प्रदान करता है।
Key figures
- Leonhard Euler
- Karl Menger
Related topics
Seminal works
- diestel2017
Frequently asked questions
- यूलरियन और हैमिल्टनियन साइकिल में क्या अंतर है?
- एक यूलरियन परिपथ हर किनारे का ठीक एक बार उपयोग करता है, जबकि एक हैमिल्टनियन साइकिल हर शीर्ष पर ठीक एक बार जाती है; पूर्व में एक सरल डिग्री लक्षण वर्णन होता है, लेकिन बाद वाले का निर्णय करना कम्प्यूटेशनल रूप से कठिन है।
- एक ग्राफ के k-कनेक्टेड होने का क्या अर्थ है?
- एक ग्राफ k-कनेक्टेड होता है यदि k से कम शीर्षों को हटाने पर भी वह जुड़ा रहता है, जो शीर्ष विफलताओं के प्रति उसके लचीलेपन को मापता है।