कनेक्टिविटी (ग्राफ सिद्धांत)
गणित और कंप्यूटर विज्ञान में कनेक्टिविटी ग्राफ़ सिद्धांत की मूल अवधारणाओं में से एक है| यह तत्वों की न्यूनतम संख्या (नोड्स या किनारों) के लिए पूछता है| जिन्हें शेष नोड्स को दो या अधिक कनेक्टेड घटक (ग्राफ़ सिद्धांत) में अलग करने के लिए निकालने की आवश्यकता होती है।[1] यह प्रवाह नेटवर्क समस्याओं के सिद्धांत से निकटता से संबंधित है। नेटवर्क के रूप में ग्राफ की कनेक्टिविटी इसकी कोमलता का महत्वपूर्ण उपाय है।
जुड़े हुए शिखर और रेखांकन
अप्रत्यक्ष ग्राफ G में दो शीर्ष (ग्राफ सिद्धांत) u और v को कनेक्टेड कहा जाता है| यदि G में u से v तक का एक पथ सम्मिलित है| अन्यथा उन्हें डिस्कनेक्टेड कहा जाता है। यदि दो शीर्षों को अतिरिक्त रूप से लंबाई 1 के पथ से जोड़ा जाता है| अर्थात किनारे से शीर्षों को आसन्न कहा जाता हैं।
एक ग्राफ़ को कनेक्टेड कहा जाता है यदि ग्राफ़ में हर जोड़ी को जोड़ा जाता है। इसका अर्थ है कि हर जोड़ी के शीर्ष के बीच एक रास्ता है। अप्रत्यक्ष ग्राफ जो जुड़ा नहीं है डिस्कनेक्टेड कहलाता है। एक अप्रत्यक्ष ग्राफ G इसलिए डिस्कनेक्ट हो जाता है यदि G में दो वर्टिकल उपस्थित हैं जैसे कि G में कोई भी पथ इन वर्टिकल को एंडपॉइंट के रूप में नहीं रखता है। केवल एक शीर्ष वाला ग्राफ जुड़ा हुआ है। दो या दो से अधिक शीर्षों वाला शून्य ग्राफ डिस्कनेक्ट हो गया है।
निर्देशित ग्राफ को कमजोर रूप से जुड़ा हुआ कहा जाता है| यदि इसके सभी निर्देशित किनारों को अप्रत्यक्ष किनारों से बदलकर जुड़ा हुआ (अप्रत्यक्ष) ग्राफ प्राप्त होता है। यह एकपक्षीय रूप से जुड़ा हुआ है| एकपक्षी जिसे सेमीकनेक्टेड भी कहा जाता है| यदि इसमें u से v तक निर्देशित पथ सम्मिलित है या v से u तक निर्देशित पथ u. , v. शीर्षों के प्रत्येक जोड़े के लिए है|[2] यह दृढ़ता से जुड़ा हुआ है या मजबूत है यदि इसमें u से v तक निर्देशित पथ और v से u तक निर्देशित पथ u, v की प्रत्येक जोड़े के लिए है|
अवयव और कटौती
एक कनेक्टेड कंपोनेंट (ग्राफ थ्योरी) एक अप्रत्यक्ष ग्राफ का एक मैक्सिमम कनेक्टेड सबग्राफ है। प्रत्येक शीर्ष ठीक एक जुड़े हुए घटक से संबंधित है, जैसा कि प्रत्येक किनारा करता है। एक ग्राफ जुड़ा हुआ है यदि और केवल यदि इसमें ठीक एक जुड़ा हुआ घटक है।
दृढ़ता से जुड़े हुए घटक एक निर्देशित ग्राफ के अधिकतम दृढ़ता से जुड़े हुए सबग्राफ हैं।
एक कट (ग्राफ सिद्धांत) या कनेक्टेड ग्राफ का अलग करने वाला सेट G वर्टिकल का एक सेट है जिसका निष्कासन रेंडर करता है G डिस्कनेक्ट किया गया। के-वर्टेक्स-कनेक्टेड ग्राफ κ(G) (कहाँ G पूर्ण ग्राफ़ नहीं है) एक न्यूनतम वर्टेक्स कट का आकार है। एक ग्राफ कहा जाता है k-वर्टेक्स-कनेक्टेड' या 'k-कनेक्टेड' यदि इसकी वर्टेक्स कनेक्टिविटी है k या बड़ा।
अधिक सटीक, कोई ग्राफ G (पूर्ण या नहीं) कहा जाता हैk-वर्टेक्स-कनेक्टेड यदि इसमें कम से कम सम्मिलित है k+1 शीर्ष, लेकिन का एक सेट सम्मिलित नहीं है k − 1 शीर्ष जिनका निष्कासन ग्राफ़ को डिस्कनेक्ट करता है; और κ(G) को सबसे बड़े के रूप में परिभाषित किया गया है k ऐसा है कि G है k-जुड़े हुए। विशेष रूप से, के साथ एक पूरा ग्राफ n कोने, निरूपित Kn, कोई शीर्ष कट बिल्कुल नहीं है, लेकिन κ(Kn) = n − 1.
दो शीर्षों के लिए एक शीर्ष काटा गया u और v वर्टिकल का एक सेट है जिसका ग्राफ़ से निष्कासन डिस्कनेक्ट हो जाता है u और v. स्थानीय कनेक्टिविटी κ(u, v) अलग करने वाले सबसे छोटे वर्टेक्स कट का आकार है u और v. अप्रत्यक्ष रेखांकन के लिए स्थानीय कनेक्टिविटी सममित है; वह है, κ(u, v) = κ(v, u). इसके अलावा, पूर्ण रेखांकन को छोड़कर, κ(G) न्यूनतम के बराबर है κ(u, v) शीर्षों के सभी असन्निकट युग्मों पर u, v.
2-कनेक्टिविटी को द्विसंबद्ध ग्राफ भी कहा जाता है और 3-कनेक्टिविटी को ट्राइकनेक्टिविटी भी कहा जाता है। एक ग्राफ G जो जुड़ा हुआ है लेकिन नहीं 2-कनेक्टेड को कभी-कभी वियोज्य कहा जाता है।
किनारों के लिए अनुरूप अवधारणाओं को परिभाषित किया जा सकता है। साधारण मामले में जिसमें एक एकल, विशिष्ट किनारे को काटने से ग्राफ अलग हो जाता है, उस किनारे को पुल (ग्राफ सिद्धांत) कहा जाता है। अधिक आम तौर पर, का एक किनारा कट जाता है G किनारों का एक सेट है जिसके हटाने से ग्राफ़ डिस्कनेक्ट हो जाता है। बढ़त-कनेक्टिविटी λ(G) सबसे छोटे एज कट का आकार और स्थानीय एज-कनेक्टिविटी है λ(u, v) दो शीर्षों का u, v सबसे छोटे किनारे के कट का आकार है जो डिस्कनेक्ट हो रहा है u से v. फिर से, स्थानीय एज-कनेक्टिविटी सममित है। ग्राफ कहा जाता हैk-एज-कनेक्टेड यदि इसकी एज कनेक्टिविटी है k या बड़ा।
एक ग्राफ को अधिकतम रूप से जुड़ा हुआ कहा जाता है यदि इसकी कनेक्टिविटी इसकी न्यूनतम डिग्री के बराबर होती है। एक ग्राफ को अधिकतम किनारे से जुड़ा हुआ कहा जाता है यदि इसकी बढ़त-कनेक्टिविटी इसकी न्यूनतम डिग्री के बराबर होती है।[3]
सुपर- और हाइपर-कनेक्टिविटी
एक ग्राफ को सुपर-कनेक्टेड या सुपर-κ कहा जाता है यदि प्रत्येक न्यूनतम वर्टेक्स कट एक वर्टेक्स को अलग करता है। एक ग्राफ को हाइपर-कनेक्टेड या हाइपर-κ कहा जाता है यदि प्रत्येक न्यूनतम वर्टेक्स कट को हटाने से वास्तव में दो घटक बनते हैं, जिनमें से एक पृथक शीर्ष है। एक ग्राफ सेमी-हाइपर-कनेक्टेड या सेमी-हाइपर-κ है यदि कोई न्यूनतम वर्टेक्स कट ग्राफ को बिल्कुल दो घटकों में अलग करता है।[4] अधिक सटीक: ए G कनेक्टेड ग्राफ़ को सुपर-कनेक्टेड या सुपर-κ कहा जाता है यदि सभी न्यूनतम वर्टेक्स-कट में एक (न्यूनतम-डिग्री) वर्टेक्स से सटे कोने होते हैं। ए G कनेक्टेड ग्राफ़ को सुपर-एज-कनेक्टेड या सुपर-λ कहा जाता है यदि सभी न्यूनतम एज-कट में कुछ (न्यूनतम-डिग्री) वर्टेक्स पर किनारों की घटना होती है।[5] एक कटसेट X का G को गैर-तुच्छ कटसेट कहा जाता है यदि X में पड़ोस सम्मिलित नहीं है N(u) किसी शीर्ष का u ∉ X. तब G की सुपरकनेक्टिविटी κ1 है:
- κ1 (जी) = न्यूनतम{|एक्स| : X एक गैर-तुच्छ कटसेट है}।
एक गैर-तुच्छ एज-कट और एज-सुपरकनेक्टिविटी λ1(G) को समान रूप से परिभाषित किया गया है।[6]
मेंजर की प्रमेय
ग्राफ़ में कनेक्टिविटी के बारे में सबसे महत्वपूर्ण तथ्यों में से एक मेन्जर की प्रमेय है, जो कोने के बीच स्वतंत्र पथों की संख्या के संदर्भ में एक ग्राफ की कनेक्टिविटी और किनारे-कनेक्टिविटी की विशेषता है।
यदि u और v ग्राफ़ के शीर्ष हैं G, फिर बीच के रास्तों का संग्रह u और v को स्वतंत्र कहा जाता है यदि उनमें से कोई भी दो शीर्ष साझा नहीं करता है (इसके अलावा u और v खुद)। इसी तरह, यदि संग्रह में कोई भी दो पथ किनारे साझा नहीं करते हैं तो संग्रह किनारे से स्वतंत्र है। के बीच परस्पर स्वतंत्र पथों की संख्या u और v के रूप में लिखा गया है κ′(u, v), और परस्पर एज-स्वतंत्र पथों की संख्या u और v के रूप में लिखा गया है λ′(u, v).
मेंजर की प्रमेय का दावा है कि अलग-अलग शीर्षों के लिए u,v, λ(u, v) बराबर है λ′(u, v), और यदि u भी v के सन्निकट नहीं है तो κ(u, v) बराबर है κ′(u, v).[7][8] यह तथ्य वास्तव में मैक्स-फ्लो मिन-कट प्रमेय का एक विशेष मामला है।
कम्प्यूटेशनल पहलू
यह निर्धारित करने की समस्या कि क्या किसी ग्राफ़ में दो कोने जुड़े हुए हैं, खोज एल्गोरिदम, जैसे चौड़ाई-प्रथम खोज का उपयोग करके कुशलतापूर्वक हल किया जा सकता है। अधिक आम तौर पर, कम्प्यूटेशनल रूप से यह निर्धारित करना आसान होता है कि कोई ग्राफ़ कनेक्ट है या नहीं (उदाहरण के लिए, डिसजॉइंट-सेट डेटा स्ट्रक्चर#एप्लिकेशन|डिसजॉइंट-सेट डेटा स्ट्रक्चर का उपयोग करके), या कनेक्टेड घटकों की संख्या की गणना करने के लिए। छद्म कोड में एक साधारण एल्गोरिदम निम्नानुसार लिखा जा सकता है:
- ग्राफ के किसी भी मनमाना नोड पर शुरू करें, G
- उस नोड से या तो डेप्थ-फर्स्ट या विड्थ-फर्स्ट सर्च का उपयोग करके आगे बढ़ें, सभी नोड्स की गिनती करें।
- एक बार ग्राफ़ को पूरी तरह से पार कर लिया गया है, यदि गिने जाने वाले नोड्स की संख्या के नोड्स की संख्या के बराबर है G, ग्राफ जुड़ा हुआ है; अन्यथा यह डिस्कनेक्ट हो गया है।
मेन्जर के प्रमेय द्वारा किन्हीं दो शीर्षों के लिए u और v एक जुड़े ग्राफ में G, संख्या κ(u, v) और {{math|λ(u, v)}मैक्स फ्लो मिन कट|मैक्स-फ्लो मिन-कट एल्गोरिथम का उपयोग करके } को कुशलतापूर्वक निर्धारित किया जा सकता है। की कनेक्टिविटी और एज-कनेक्टिविटी G की गणना तब के न्यूनतम मानों के रूप में की जा सकती है κ(u, v) और λ(u, v), क्रमश।
कम्प्यूटेशनल जटिलता सिद्धांत में, [[एसएल (जटिलता)]] लॉग-स्पेस समस्याओं का वर्ग है जो यह निर्धारित करने की समस्या के लिए कम हो जाता है कि ग्राफ में दो कोने जुड़े हुए हैं, जो 2004 में ओमर रीनॉल्ड द्वारा एल (जटिलता) के बराबर साबित हुआ था।[9] इसलिए, अप्रत्यक्ष ग्राफ कनेक्टिविटी को हल किया जा सकता है O(log n) अंतरिक्ष।
संभाव्यता की गणना करने की समस्या है कि एक बर्नौली वितरण यादृच्छिक ग्राफ जुड़ा हुआ है जिसे नेटवर्क विश्वसनीयता कहा जाता है और यह गणना करने की समस्या है कि दो दिए गए कोने एसटी-विश्वसनीयता समस्या से जुड़े हैं या नहीं। ये दोनों तेज-पी|#पी-हार्ड हैं।[10]
जुड़े हुए रेखांकन की संख्या
एन नोड्स के साथ अलग-अलग जुड़े लेबल वाले ग्राफ़ की संख्या अनुक्रम के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में सारणीबद्ध है A001187. पहले कुछ गैर-तुच्छ शब्द हैं
| n | graphs |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 4 |
| 4 | 38 |
| 5 | 728 |
| 6 | 26704 |
| 7 | 1866256 |
| 8 | 251548592 |
उदाहरण
- एक डिस्कनेक्ट किए गए ग्राफ़ के वर्टेक्स- और एज-कनेक्टिविटी दोनों हैं 0.
- 1-कनेक्टनेस कम से कम 2 सिरों के ग्राफ़ के लिए कनेक्टिविटी के बराबर है।
- पूरा ग्राफ चालू n वर्टिकल में एज-कनेक्टिविटी बराबर है n − 1. हर दूसरे साधारण ग्राफ पर n वर्टिकल में सख्ती से छोटी एज-कनेक्टिविटी है।
- एक पेड़ (ग्राफ सिद्धांत) में, हर जोड़ी के बीच स्थानीय बढ़त-कनेक्टिविटी होती है 1.
कनेक्टिविटी पर सीमा
- किसी ग्राफ की वर्टेक्स-कनेक्टिविटी उसके एज-कनेक्टिविटी से कम या उसके बराबर होती है। वह है, κ(G) ≤ λ(G). दोनों ग्राफ़ की डिग्री (ग्राफ़ सिद्धांत) से कम या उसके बराबर हैं, क्योंकि न्यूनतम डिग्री के शीर्ष के सभी पड़ोसियों को हटाने से उस शीर्ष को बाकी ग्राफ़ से अलग कर दिया जाएगा।[1]
- डिग्री के शीर्ष-सकर्मक ग्राफ के लिए (ग्राफ सिद्धांत) d, अपने पास: 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d.[11]
- डिग्री के शीर्ष-सकर्मक ग्राफ के लिए (ग्राफ सिद्धांत) d ≤ 4, या किसी भी (अप्रत्यक्ष) डिग्री के न्यूनतम केली ग्राफ (ग्राफ सिद्धांत) के लिए d, या डिग्री के किसी सममित ग्राफ के लिए (ग्राफ सिद्धांत) d, दोनों प्रकार की कनेक्टिविटी समान हैं: κ(G) = λ(G) = d.[12]
अन्य गुण
- जुड़ाव को ग्राफ समरूपता द्वारा संरक्षित किया जाता है।
- यदि G जुड़ा हुआ है तो इसका लाइन ग्राफ L(G) भी जुड़ा हुआ है।
- एक ग्राफ G है 2-एज-कनेक्टेड यदि और केवल यदि इसमें एक ओरिएंटेशन है जो दृढ़ता से जुड़ा हुआ है।
- बालिंस्की के प्रमेय में कहा गया है कि पॉलीटॉपल ग्राफ (1-कंकाल (टोपोलॉजी)) का a k-विमीय उत्तल polytope एक है k-वर्टेक्स-कनेक्टेड ग्राफ।[13] अर्नेस्ट स्टीनिट्ज़ का पिछला प्रमेय कि कोई भी 3-वर्टेक्स-कनेक्टेड प्लेनर ग्राफ ़ एक पॉलीटोपल ग्राफ़ है (स्टीनिट्ज़ प्रमेय) एक आंशिक बातचीत देता है।
- गेब्रियल एंड्रयू डिराक के एक प्रमेय के अनुसार | जी। ए Dirac, यदि एक ग्राफ है k-के लिए जुड़ा हुआ है k ≥ 2, फिर प्रत्येक सेट के लिए k ग्राफ़ में शीर्षों पर एक चक्र होता है जो सेट के सभी शीर्षों से होकर गुजरता है।[14][15] विलोम सत्य है जब k = 2.
यह भी देखें
- बीजगणितीय कनेक्टिविटी
- चीजर स्थिरांक (ग्राफ सिद्धांत)
- गतिशील कनेक्टिविटी, विसंधित-सेट डेटा संरचना
- विस्तारक ग्राफ
- एक ग्राफ की ताकत
संदर्भ
- ↑ 1.0 1.1 Diestel, R. (2005). "ग्राफ थ्योरी, इलेक्ट्रॉनिक संस्करण". p. 12.
- ↑ Chapter 11: Digraphs: Principle of duality for digraphs: Definition
- ↑ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.
- ↑ Liu, Qinghai; Zhang, Zhao (2010-03-01). "दो प्रकार की प्रतिबंधित कनेक्टिविटी के लिए अस्तित्व और ऊपरी सीमा". Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.
- ↑ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.
- ↑ Balbuena, Camino; Carmona, Angeles (2001-10-01). "द्विपक्षीय डिग्राफ और ग्राफ की कनेक्टिविटी और सुपरकनेक्टिविटी पर". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
- ↑ Gibbons, A. (1985). एल्गोरिथम ग्राफ थ्योरी. Cambridge University Press.
- ↑ Nagamochi, H.; Ibaraki, T. (2008). ग्राफ कनेक्टिविटी के एल्गोरिदमिक पहलू. Cambridge University Press.
- ↑ Reingold, Omer (2008). "लॉग-स्पेस में अप्रत्यक्ष कनेक्टिविटी". Journal of the ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478.
- ↑ Provan, J. Scott; Ball, Michael O. (1983). "The complexity of counting cuts and of computing the probability that a graph is connected". SIAM Journal on Computing. 12 (4): 777–788. doi:10.1137/0212053. MR 0721012..
- ↑ Godsil, C.; Royle, G. (2001). बीजगणितीय ग्राफ सिद्धांत. Springer Verlag.
- ↑ Babai, L. (1996). ऑटोमोर्फिज्म समूह, आइसोमोर्फिज्म, पुनर्निर्माण. Technical Report TR-94-10. University of Chicago. Archived from the original on 2010-06-11. Chapter 27 of The Handbook of Combinatorics.
- ↑ Balinski, M. L. (1961). "On the graph structure of convex polyhedra in n[[Category: Templates Vigyan Ready]]-space". Pacific Journal of Mathematics. 11 (2): 431–434. doi:10.2140/pjm.1961.11.431.
{{cite journal}}: URL–wikilink conflict (help) - ↑ Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311..
- ↑ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). "A generalization of Dirac's theorem on cycles through k[[Category: Templates Vigyan Ready]] vertices in k[[Category: Templates Vigyan Ready]]-connected graphs". Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. MR 2297171.
{{cite journal}}: URL–wikilink conflict (help).
