कनेक्टिविटी (ग्राफ सिद्धांत): Difference between revisions
No edit summary |
No edit summary |
||
| Line 79: | Line 79: | ||
# एक बार ग्राफ़ को पूरी तरह से पार हो जाने के बाद यदि गिने हुए नोड्स की संख्या {{mvar|G}} के नोड्स की संख्या के बराबर है तो ग्राफ जुड़ा हुआ है| अन्यथा यह डिस्कनेक्ट हो गया है। | # एक बार ग्राफ़ को पूरी तरह से पार हो जाने के बाद यदि गिने हुए नोड्स की संख्या {{mvar|G}} के नोड्स की संख्या के बराबर है तो ग्राफ जुड़ा हुआ है| अन्यथा यह डिस्कनेक्ट हो गया है। | ||
मेन्जर के प्रमेय | मेन्जर के प्रमेय के अनुसार कनेक्टेड ग्राफ़ G में किन्हीं दो शीर्षों u और v के लिए संख्या κ(u, v) और λ(u, v) को अधिकतम-प्रवाह न्यूनतम-कट एल्गोरिथम का उपयोग करके कुशलता से निर्धारित किया जा सकता है। {{mvar|G}} की कनेक्टिविटी और एज कनेक्टिविटी की गणना क्रमशः {{math|''κ''(''u'', ''v'')}} और {{math|''λ''(''u'', ''v'')}} के न्यूनतम मूल्यों के रूप में की जा सकती है। | ||
कम्प्यूटेशनल जटिलता सिद्धांत में, [[एस[[एल (जटिलता)]]]] लॉग-स्पेस समस्याओं का वर्ग है जो यह निर्धारित करने की समस्या के लिए कम हो जाता है कि ग्राफ में दो कोने जुड़े हुए हैं, जो 2004 में [[ओमर रीनॉल्ड]] द्वारा एल (जटिलता) के बराबर साबित हुआ था।<ref>{{Cite journal|first=Omer|last=Reingold|author-link=Omer Reingold|title=लॉग-स्पेस में अप्रत्यक्ष कनेक्टिविटी|journal=[[Journal of the ACM]]|year=2008|volume=55|issue=4|pages=1–24| doi=10.1145/1391289.1391291|s2cid=207168478}}</ref> इसलिए, अप्रत्यक्ष ग्राफ कनेक्टिविटी को हल किया जा सकता है {{math|O(log ''n'')}} अंतरिक्ष। | कम्प्यूटेशनल जटिलता सिद्धांत में, [[एस[[एल (जटिलता)]]]] लॉग-स्पेस समस्याओं का वर्ग है जो यह निर्धारित करने की समस्या के लिए कम हो जाता है कि ग्राफ में दो कोने जुड़े हुए हैं, जो 2004 में [[ओमर रीनॉल्ड]] द्वारा एल (जटिलता) के बराबर साबित हुआ था।<ref>{{Cite journal|first=Omer|last=Reingold|author-link=Omer Reingold|title=लॉग-स्पेस में अप्रत्यक्ष कनेक्टिविटी|journal=[[Journal of the ACM]]|year=2008|volume=55|issue=4|pages=1–24| doi=10.1145/1391289.1391291|s2cid=207168478}}</ref> इसलिए, अप्रत्यक्ष ग्राफ कनेक्टिविटी को हल किया जा सकता है {{math|O(log ''n'')}} अंतरिक्ष। | ||
Revision as of 22:52, 16 May 2023
गणित और कंप्यूटर विज्ञान में कनेक्टिविटी ग्राफ़ सिद्धांत की मूल अवधारणाओं में से एक है| यह तत्वों की न्यूनतम संख्या (नोड्स या किनारों) के लिए पूछता है| जिन्हें शेष नोड्स को दो या अधिक कनेक्टेड घटक (ग्राफ़ सिद्धांत) में अलग करने के लिए निकालने की आवश्यकता होती है।[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) = κ(v, u) है| इसके अतिरिक्त पूर्ण रेखांकन को छोड़कर κ(G) न्यूनतम κ(u, v) के बराबर है| शीर्षों के सभी अनिकट युग्म u, v पर है|
2-कनेक्टिविटी को बाइकनेक्टिविटी भी कहा जाता है और 3-कनेक्टिविटी को ट्राइकनेक्टिविटी भी कहा जाता है। ग्राफ G जो जुड़ा हुआ है लेकिन 2-कनेक्टेड नहीं है| उसे कभी-कभी वियोज्य कहा जाता है।
किनारों के लिए अनुरूप अवधारणाओं को परिभाषित किया जा सकता है। साधारण स्थितियों में जिसमें एकल विशिष्ट किनारे को काटने से ग्राफ अलग हो जाता है| उस किनारे को पुल (ग्राफ सिद्धांत) कहा जाता है। सामान्यतः G का किनारा कट किनारों का समुच्चय होता है| जिसका निष्कासन ग्राफ़ को डिस्कनेक्ट करता है। एज-कनेक्टिविटी λ(G) सबसे छोटे एज कट का आकार है| और स्थानीय एज-कनेक्टिविटी λ(u, v) दो शीर्षों का u, v सबसे छोटे किनारे के कट का आकार है| जो u से v डिस्कनेक्ट हो रहा है| फिर से स्थानीय एज-कनेक्टिविटी सममित है। ग्राफ को k-एज-कनेक्टेड कहा जाता है| यदि इसकी एज कनेक्टिविटी k या अधिक है।
ग्राफ को अधिकतम रूप से जुड़ा हुआ कहा जाता है यदि इसकी कनेक्टिविटी न्यूनतम डिग्री के बराबर होती है। ग्राफ को अधिकतम किनारे से जुड़ा हुआ कहा जाता है| यदि इसकी बढ़त-कनेक्टिविटी इसकी न्यूनतम डिग्री के बराबर होती है।[3]
सुपर- और हाइपर-कनेक्टिविटी
ग्राफ को सुपर-कनेक्टेड या सुपर-κ कहा जाता है| यदि प्रत्येक न्यूनतम वर्टेक्स कट एक वर्टेक्स को अलग करता है। ग्राफ को हाइपर-कनेक्टेड या हाइपर-κ कहा जाता है| यदि प्रत्येक न्यूनतम वर्टेक्स कट को हटाने से वास्तव में दो घटक बनते हैं| जिनमें से एक पृथक शीर्ष है। ग्राफ सेमी-हाइपर-कनेक्टेड या सेमी-हाइपर-κ है यदि कोई न्यूनतम वर्टेक्स कट ग्राफ को दो घटकों में अलग करता है।[4]
अधिक स्पष्ट रूप से a G कनेक्टेड ग्राफ़ को सुपर-कनेक्टेड या सुपर-κ कहा जाता है| यदि सभी न्यूनतम वर्टेक्स-कट में (न्यूनतम-डिग्री) वर्टेक्स से सटे कोने होते हैं।
a G कनेक्टेड ग्राफ़ को सुपर-एज-कनेक्टेड या सुपर-λ कहा जाता है| यदि सभी न्यूनतम एज-कट में कुछ (न्यूनतम-डिग्री) वर्टेक्स पर किनारों की घटना होती है।[5]
G के कटसेट X को गैर-तुच्छ कटसेट कहा जाता है| यदि X में किसी शीर्ष u ∉ X का पड़ोस N(u) नहीं है। तो G की सुपरकनेक्टिविटी κ1 है:
- κ1 (G) = न्यूनतम{|एक्स| : 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 के नोड्स की संख्या के बराबर है तो ग्राफ जुड़ा हुआ है| अन्यथा यह डिस्कनेक्ट हो गया है।
मेन्जर के प्रमेय के अनुसार कनेक्टेड ग्राफ़ G में किन्हीं दो शीर्षों u और v के लिए संख्या κ(u, v) और λ(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).
