कनेक्टिविटी (ग्राफ सिद्धांत): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(14 intermediate revisions by 3 users not shown)
Line 4: Line 4:


== जुड़े हुए शिखर और रेखांकन ==
== जुड़े हुए शिखर और रेखांकन ==
[[File:UndirectedDegrees.svg|thumb|वर्टेक्स 0 के साथ, यह ग्राफ डिस्कनेक्ट हो गया है। बाकी ग्राफ जुड़ा हुआ है।]][[अप्रत्यक्ष ग्राफ]] {{mvar|G}} में दो शीर्ष (ग्राफ सिद्धांत) {{mvar|u}} और {{mvar|v}} को कनेक्टेड कहा जाता है| यदि {{mvar|G}} में {{mvar|u}} से {{mvar|v}} तक का एक पथ सम्मिलित है| अन्यथा उन्हें डिस्कनेक्टेड कहा जाता है। यदि दो शीर्षों को अतिरिक्त रूप से लंबाई {{math|1}} के पथ से जोड़ा जाता है| अर्थात किनारे से शीर्षों को आसन्न कहा जाता हैं।
[[File:UndirectedDegrees.svg|thumb|वर्टेक्स 0 के साथ यह ग्राफ डिस्कनेक्ट हो गया है। बाकी ग्राफ जुड़ा हुआ है।]][[अप्रत्यक्ष ग्राफ]] {{mvar|G}} में दो शीर्ष (ग्राफ सिद्धांत) {{mvar|u}} और {{mvar|v}} को कनेक्टेड कहा जाता है| यदि {{mvar|G}} में {{mvar|u}} से {{mvar|v}} तक का एक पथ सम्मिलित है| अन्यथा उन्हें डिस्कनेक्टेड कहा जाता है। यदि दो शीर्षों को अतिरिक्त रूप से लंबाई {{math|1}} के पथ से जोड़ा जाता है| अर्थात किनारे से शीर्षों को आसन्न कहा जाता हैं।


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


[[निर्देशित ग्राफ]] को कमजोर रूप से जुड़ा हुआ कहा जाता है| यदि इसके सभी निर्देशित किनारों को अप्रत्यक्ष किनारों से बदलकर जुड़ा हुआ (अप्रत्यक्ष) ग्राफ प्राप्त होता है। यह एकपक्षीय रूप से जुड़ा हुआ है| एकपक्षी जिसे सेमीकनेक्टेड भी कहा जाता है| यदि इसमें {{mvar|u}} से {{mvar|v}} तक निर्देशित पथ सम्मिलित है या {{mvar|v}} से {{mvar|u}} तक निर्देशित पथ {{mvar|u}}. , {{mvar|v}}. शीर्षों के प्रत्येक जोड़े के लिए है|<ref>[http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2011.pdf#page=6 Chapter 11: Digraphs: Principle of duality for digraphs: Definition]</ref> यह दृढ़ता से जुड़ा हुआ है या मजबूत है यदि इसमें {{mvar|u}} से {{mvar|v}} तक निर्देशित पथ और {{mvar|v}} से {{mvar|u}} तक निर्देशित पथ {{mvar|u, v}} की प्रत्येक जोड़े के लिए है|
[[निर्देशित ग्राफ]] को कमजोर रूप से जुड़ा हुआ कहा जाता है| यदि इसके सभी निर्देशित किनारों को अप्रत्यक्ष किनारों से बदलकर जुड़ा हुआ (अप्रत्यक्ष) ग्राफ प्राप्त होता है। यह एकपक्षीय रूप से जुड़ा हुआ है| एकपक्षी जिसे सेमीकनेक्टेड भी कहा जाता है| यदि इसमें {{mvar|u}} से {{mvar|v}} तक निर्देशित पथ सम्मिलित है या {{mvar|v}} से {{mvar|u}} तक निर्देशित पथ {{mvar|u}}. , {{mvar|v}}. शीर्षों के प्रत्येक जोड़े के लिए है|<ref>[http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%2011.pdf#page=6 Chapter 11: Digraphs: Principle of duality for digraphs: Definition]</ref> यह दृढ़ता से जुड़ा हुआ है या मजबूत है यदि इसमें {{mvar|u}} से {{mvar|v}} तक निर्देशित पथ और {{mvar|v}} से {{mvar|u}} तक निर्देशित पथ {{mvar|u, v}} की प्रत्येक जोड़े के लिए है|


== अवयव और कटौती ==
== अवयव और कटौती ==
Line 17: Line 17:
[[ कट (ग्राफ सिद्धांत) |(ग्राफ सिद्धांत)]] या कनेक्टेड ग्राफ {{mvar|G}} का वर्टिकल [[ कट (ग्राफ सिद्धांत) |कट]] या अलग करने वाला समुच्चय वर्टिकल का एक समुच्चय है| जिसका निष्कासन {{mvar|G}} रेंडर करता है| वर्टेक्स-कनेक्टिविटी ग्राफ {{math|''κ''(''G'')}} (जहां {{mvar|G}} पूर्ण ग्राफ़ नहीं है) न्यूनतम वर्टेक्स कट का आकार है। एक ग्राफ को ''{{mvar|k}}-वर्टेक्स-कनेक्टेड' या '{{mvar|k}}-कनेक्टेड' कहा जाता है यदि इसकी वर्टेक्स कनेक्टिविटी {{mvar|k}} या अधिक है।''
[[ कट (ग्राफ सिद्धांत) |(ग्राफ सिद्धांत)]] या कनेक्टेड ग्राफ {{mvar|G}} का वर्टिकल [[ कट (ग्राफ सिद्धांत) |कट]] या अलग करने वाला समुच्चय वर्टिकल का एक समुच्चय है| जिसका निष्कासन {{mvar|G}} रेंडर करता है| वर्टेक्स-कनेक्टिविटी ग्राफ {{math|''κ''(''G'')}} (जहां {{mvar|G}} पूर्ण ग्राफ़ नहीं है) न्यूनतम वर्टेक्स कट का आकार है। एक ग्राफ को ''{{mvar|k}}-वर्टेक्स-कनेक्टेड' या '{{mvar|k}}-कनेक्टेड' कहा जाता है यदि इसकी वर्टेक्स कनेक्टिविटी {{mvar|k}} या अधिक है।''


अधिक स्पष्ट रूप से किसी भी ग्राफ {{mvar|G}} (पूर्ण या नहीं) को {{mvar|k}}-वर्टेक्स-कनेक्टेड कहा जाता है| यदि इसमें कम से कम {{math|''k''+1}} शीर्ष हो लेकिन इसमें {{math|''k'' − 1}} शीर्ष का समुच्चय सम्मिलित नहीं है| जिनका निष्कासन ग्राफ़ को डिस्कनेक्ट कर देता है| और {{math|''κ''(''G'')}} को सबसे बड़े {{mvar|k}} के रूप में परिभाषित किया गया है| जैसा कि {{mvar|G}} {{mvar|k}}-जुड़ा हुआ है। विशेष रूप से {{mvar|n}} शीर्षों के साथ पूर्ण ग्राफ जिसे {{mvar|K<sub>n</sub>}} से निरूपित किया गया है| कोई शीर्ष कट नहीं है| लेकिन {{math|''κ''(''K<sub>n</sub>'') {{=}} ''n'' − 1}} है|
अधिक स्पष्ट रूप से किसी भी ग्राफ {{mvar|G}} (पूर्ण या नहीं) को {{mvar|k}}-वर्टेक्स-कनेक्टेड कहा जाता है| यदि इसमें कम से कम {{math|''k''+1}} शीर्ष हो लेकिन इसमें {{math|''k'' − 1}} शीर्ष का समुच्चय सम्मिलित नहीं है| जिनका निष्कासन ग्राफ़ को डिस्कनेक्ट कर देता है| और {{math|''κ''(''G'')}} को सबसे बड़े {{mvar|k}} के रूप में परिभाषित किया गया है| जैसा कि {{mvar|G}} {{mvar|k}}-जुड़ा हुआ है। विशेष रूप से {{mvar|n}} शीर्षों के साथ पूर्ण ग्राफ जिसे {{mvar|K<sub>n</sub>}} से निरूपित किया गया है| कोई शीर्ष कट नहीं है| लेकिन {{math|''κ''(''K<sub>n</sub>'') {{=}} ''n'' − 1}} है|


दो शीर्षों {{mvar|u}} और {{mvar|v}} के लिए कटा हुआ एक शीर्ष शीर्षों का समुच्चय है| जिसका ग्राफ़ के निष्कासन {{mvar|u}} और {{mvar|v}} डिस्कनेक्ट हो जाते है| स्थानीय कनेक्टिविटी {{math|''κ''(''u'', ''v'')}} अलग करने वाले सबसे छोटे वर्टेक्स कट का आकार है| अप्रत्यक्ष रेखांकन के लिए स्थानीय कनेक्टिविटी सममित है| वह {{math|''κ''(''u'', ''v'') {{=}} ''κ''(''v'', ''u'')}} है| इसके अतिरिक्त पूर्ण रेखांकन को छोड़कर {{math|''κ''(''G'')}} न्यूनतम {{math|''κ''(''u'', ''v'')}} के बराबर है| शीर्षों के सभी अनिकट युग्म {{mvar|u, v}} पर है|
दो शीर्षों {{mvar|u}} और {{mvar|v}} के लिए कटा हुआ एक शीर्ष शीर्षों का समुच्चय है| जिसका ग्राफ़ के निष्कासन {{mvar|u}} और {{mvar|v}} डिस्कनेक्ट हो जाते है| स्थानीय कनेक्टिविटी {{math|''κ''(''u'', ''v'')}} अलग करने वाले सबसे छोटे वर्टेक्स कट का आकार है| अप्रत्यक्ष रेखांकन के लिए स्थानीय कनेक्टिविटी सममित है| वह {{math|''κ''(''u'', ''v'') {{=}} ''κ''(''v'', ''u'')}} है| इसके अतिरिक्त पूर्ण रेखांकन को छोड़कर {{math|''κ''(''G'')}} न्यूनतम {{math|''κ''(''u'', ''v'')}} के बराबर है| शीर्षों के सभी अनिकट युग्म {{mvar|u, v}} पर है|


{{math|2}}-कनेक्टिविटी को[[ द्विसंबद्ध ग्राफ | बाइकनेक्टिविटी]] भी कहा जाता है और {{math|3}}-कनेक्टिविटी को ट्राइकनेक्टिविटी भी कहा जाता है। ग्राफ {{mvar|G}} जो जुड़ा हुआ है लेकिन {{math|2}}-कनेक्टेड नहीं है| उसे कभी-कभी वियोज्य कहा जाता है।
{{math|2}}-कनेक्टिविटी को[[ द्विसंबद्ध ग्राफ | बाइकनेक्टिविटी]] भी कहा जाता है और {{math|3}}-कनेक्टिविटी को ट्राइकनेक्टिविटी भी कहा जाता है। ग्राफ {{mvar|G}} जो जुड़ा हुआ है लेकिन {{math|2}}-कनेक्टेड नहीं है| उसे कभी-कभी वियोज्य कहा जाता है।


किनारों के लिए अनुरूप अवधारणाओं को परिभाषित किया जा सकता है। साधारण स्थितियों में जिसमें एकल विशिष्ट किनारे को काटने से ग्राफ अलग हो जाता है| उस किनारे को [[पुल (ग्राफ सिद्धांत)]] कहा जाता है। सामान्यतः {{mvar|G}} का किनारा कट किनारों का समुच्चय होता है| जिसका निष्कासन ग्राफ़ को डिस्कनेक्ट करता है। [[बढ़त-कनेक्टिविटी|एज-कनेक्टिविटी]] {{math|''λ''(''G'')}} सबसे छोटे एज कट का आकार है| और स्थानीय एज-कनेक्टिविटी {{math|''λ''(''u'', ''v'')}} दो शीर्षों का {{mvar|u, v}} सबसे छोटे किनारे के कट का आकार है| जो {{mvar|u}} से {{mvar|v}} डिस्कनेक्ट हो रहा है| फिर से स्थानीय एज-कनेक्टिविटी सममित है। ग्राफ को {{mvar|k}}-एज-कनेक्टेड कहा जाता है| यदि इसकी एज कनेक्टिविटी {{mvar|k}} या अधिक है।
किनारों के लिए अनुरूप अवधारणाओं को परिभाषित किया जा सकता है। साधारण स्थितियों में जिसमें एकल विशिष्ट किनारे को काटने से ग्राफ अलग हो जाता है| उस किनारे को [[पुल (ग्राफ सिद्धांत)]] कहा जाता है। सामान्यतः {{mvar|G}} का किनारा कट किनारों का समुच्चय होता है| जिसका निष्कासन ग्राफ़ को डिस्कनेक्ट करता है। [[बढ़त-कनेक्टिविटी|एज-कनेक्टिविटी]] {{math|''λ''(''G'')}} सबसे छोटे एज कट का आकार है| और स्थानीय एज-कनेक्टिविटी {{math|''λ''(''u'', ''v'')}} दो शीर्षों का {{mvar|u, v}} सबसे छोटे किनारे के कट का आकार है| जो {{mvar|u}} से {{mvar|v}} डिस्कनेक्ट हो रहा है| फिर से स्थानीय एज-कनेक्टिविटी सममित है। ग्राफ को {{mvar|k}}-एज-कनेक्टेड कहा जाता है| यदि इसकी एज कनेक्टिविटी {{mvar|k}} या अधिक है।


ग्राफ को अधिकतम रूप से जुड़ा हुआ कहा जाता है यदि इसकी कनेक्टिविटी न्यूनतम डिग्री के बराबर होती है। ग्राफ को अधिकतम किनारे से जुड़ा हुआ कहा जाता है| यदि इसकी बढ़त-कनेक्टिविटी इसकी न्यूनतम डिग्री के बराबर होती है।<ref>{{Cite book
ग्राफ को अधिकतम रूप से जुड़ा हुआ कहा जाता है यदि इसकी कनेक्टिविटी न्यूनतम डिग्री के बराबर होती है। ग्राफ को अधिकतम किनारे से जुड़ा हुआ कहा जाता है| यदि इसकी बढ़त-कनेक्टिविटी इसकी न्यूनतम डिग्री के बराबर होती है।<ref>{{Cite book
Line 57: Line 57:
  }}</ref>
  }}</ref>


G के कटसेट X को गैर-तुच्छ कटसेट कहा जाता है| यदि X में किसी शीर्ष u ∉ X का पड़ोस N(u) नहीं है। तो G की सुपरकनेक्टिविटी κ1 है:
G के कटसमुच्चय X को दूसरा-नगण्य कटसमुच्चय कहा जाता है| यदि X में किसी शीर्ष u ∉ X का पड़ोस N(u) नहीं है। तो G की सुपरकनेक्टिविटी κ1 है:
: κ1 (G) = न्यूनतम{|एक्स| : X एक गैर-तुच्छ कटसमुच्चय है}।
: κ1 (G) = न्यूनतम{|एक्स| : X एक दूसरा-नगण्य कटसमुच्चय है}।


एक गैर-तुच्छ एज-कट और एज-सुपरकनेक्टिविटी λ1(G) को समान रूप से परिभाषित किया गया है।<ref>{{Cite journal|last1=Balbuena|first1=Camino|last2=Carmona|first2=Angeles|date=2001-10-01|title=द्विपक्षीय डिग्राफ और ग्राफ की कनेक्टिविटी और सुपरकनेक्टिविटी पर|journal=Ars Combinatorica|volume=61|pages=3–22|citeseerx=10.1.1.101.1458}}</ref>
एक दूसरा-नगण्य एज-कट और एज-सुपरकनेक्टिविटी λ1(G) को समान रूप से परिभाषित किया गया है।<ref>{{Cite journal|last1=Balbuena|first1=Camino|last2=Carmona|first2=Angeles|date=2001-10-01|title=द्विपक्षीय डिग्राफ और ग्राफ की कनेक्टिविटी और सुपरकनेक्टिविटी पर|journal=Ars Combinatorica|volume=61|pages=3–22|citeseerx=10.1.1.101.1458}}</ref>




Line 73: Line 73:


== कम्प्यूटेशनल पहलू ==
== कम्प्यूटेशनल पहलू ==
यह निर्धारित करने की समस्या कि क्या किसी ग्राफ़ में दो कोने जुड़े हुए हैं, [[खोज एल्गोरिदम]], जैसे चौड़ाई-प्रथम खोज का उपयोग करके कुशलतापूर्वक हल किया जा सकता है। अधिक सामान्यतः, कम्प्यूटेशनल रूप से यह निर्धारित करना आसान होता है कि कोई ग्राफ़ कनेक्ट है या नहीं (उदाहरण के लिए, डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर#एप्लिकेशन|डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर का उपयोग करके), या कनेक्टेड घटकों की संख्या की गणना करने के लिए। [[छद्म कोड]] में एक साधारण एल्गोरिदम निम्नानुसार लिखा जा सकता है:
यह निर्धारित करने की समस्या कि क्या किसी ग्राफ़ में दो कोने जुड़े हुए हैं| [[खोज एल्गोरिदम]] जैसे चौड़ाई-प्रथम खोज का उपयोग करके कुशलतापूर्वक हल किया जा सकता है। सामान्यतः कम्प्यूटेशनल रूप से यह निर्धारित करना आसान होता है कि कोई ग्राफ़ कनेक्ट है या नहीं (उदाहरण के लिए डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर एप्लिकेशन|डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर का उपयोग करके) या कनेक्टेड घटकों की संख्या की गणना करने के लिए। [[छद्म कोड]] में साधारण एल्गोरिदम निम्नानुसार लिखा जा सकता है|


# ग्राफ के किसी भी मनमाना नोड पर शुरू करें, {{mvar|G}}
# ग्राफ के किसी भी इच्छानुकूल {{mvar|G}} नोड पर शुरू करें|
# उस नोड से या तो डेप्थ-फर्स्ट या विड्थ-फर्स्ट सर्च का उपयोग करके आगे बढ़ें, सभी नोड्स की गिनती करें।
# उस नोड से या तो डेप्थ-फर्स्ट या विड्थ-फर्स्ट सर्च का उपयोग करके आगे बढ़ें और सभी नोड्स की गणना करें।
# एक बार ग्राफ़ को पूरी तरह से पार कर लिया गया है, यदि गिने जाने वाले नोड्स की संख्या के नोड्स की संख्या के बराबर है {{mvar|G}}, ग्राफ जुड़ा हुआ है; अन्यथा यह डिस्कनेक्ट हो गया है।
# एक बार ग्राफ़ को पूरी तरह से पार हो जाने के बाद यदि गिने हुए नोड्स की संख्या {{mvar|G}} के नोड्स की संख्या के बराबर है तो ग्राफ जुड़ा हुआ है| अन्यथा यह डिस्कनेक्ट हो गया है।


मेन्जर के प्रमेय द्वारा किन्हीं दो शीर्षों के लिए {{mvar|u}} और {{mvar|v}} एक जुड़े ग्राफ में {{mvar|G}}, संख्या {{math|''κ''(''u'', ''v'')}} और {{math|''λ''(''u'', ''v'')}[[मैक्स फ्लो मिन कट]]|मैक्स-फ्लो मिन-कट एल्गोरिथम का उपयोग करके } को कुशलतापूर्वक निर्धारित किया जा सकता है। की कनेक्टिविटी और एज-कनेक्टिविटी {{mvar|G}} की गणना तब के न्यूनतम मानों के रूप में की जा सकती है {{math|''κ''(''u'', ''v'')}} और {{math|''λ''(''u'', ''v'')}}, क्रमश।
मेन्जर के प्रमेय के अनुसार कनेक्टेड ग्राफ़ 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'')}} स्थान में हल किया जा सकता है।


संभाव्यता की गणना करने की समस्या है कि एक बर्नौली वितरण यादृच्छिक ग्राफ जुड़ा हुआ है जिसे नेटवर्क विश्वसनीयता कहा जाता है और यह गणना करने की समस्या है कि दो दिए गए कोने एसटी-विश्वसनीयता समस्या से जुड़े हैं या नहीं। ये दोनों तेज-पी|#पी-हार्ड हैं।<ref>{{cite journal
संभाव्यता की गणना करने की समस्या है कि एक बर्नौली वितरण यादृच्छिक ग्राफ जुड़ा हुआ है जिसे नेटवर्क विश्वसनीयता कहा जाता है| और यह गणना करने की समस्या है कि दो दिए गए कोने एसटी-विश्वसनीयता समस्या से जुड़े हैं या नहीं। ये दोनों पी-हार्ड हैं।<ref>{{cite journal
  | last1 = Provan | first1 = J. Scott
  | last1 = Provan | first1 = J. Scott
  | last2 = Ball | first2 = Michael O.
  | last2 = Ball | first2 = Michael O.
Line 97: Line 97:


=== जुड़े हुए रेखांकन की संख्या ===
=== जुड़े हुए रेखांकन की संख्या ===
{{Main|Graph enumeration}}
{{Main|ग्राफ गणना}}
एन नोड्स के साथ अलग-अलग जुड़े लेबल वाले ग्राफ़ की संख्या अनुक्रम के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में सारणीबद्ध है {{OEIS link|A001187}}. पहले कुछ गैर-तुच्छ शब्द हैं
 
एन नोड्स के साथ अलग-अलग जुड़े लेबल वाले ग्राफ़ की संख्या अनुक्रम {{OEIS link|A001187}} के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में सारणीबद्ध है| पहले कुछ दूसरा-नगण्य शब्द हैं|
[[File:The number of connected graphs with 4 vertices.png|thumb|4 नोड्स के साथ जुड़े ग्राफ़ की संख्या और छवियां]]
[[File:The number of connected graphs with 4 vertices.png|thumb|4 नोड्स के साथ जुड़े ग्राफ़ की संख्या और छवियां]]
{| class="wikitable" style="margin:1em auto;"
{| class="wikitable" style="margin:1em auto;"
! ''n''
! ''n''
! graphs
!रेखांकन
|-
|-
! 1
! 1
Line 131: Line 132:


== उदाहरण ==
== उदाहरण ==
* एक डिस्कनेक्ट किए गए ग्राफ़ के वर्टेक्स- और एज-कनेक्टिविटी दोनों हैं {{math|0}}.
* एक डिस्कनेक्ट किए गए ग्राफ़ के वर्टेक्स- और एज-कनेक्टिविटी दोनों {{math|0}} हैं|
* {{math|1}}-कनेक्टनेस कम से कम 2 सिरों के ग्राफ़ के लिए कनेक्टिविटी के बराबर है।
* {{math|1}}-कनेक्टनेस कम से कम 2 सिरों के ग्राफ़ के लिए कनेक्टिविटी के बराबर है।
* पूरा ग्राफ चालू {{mvar|n}} वर्टिकल में एज-कनेक्टिविटी बराबर है {{math|''n'' − 1}}. हर दूसरे साधारण ग्राफ पर {{mvar|n}} वर्टिकल में सख्ती से छोटी एज-कनेक्टिविटी है।
* n शीर्षों पर पूर्ण ग्राफ़ में किनारा-कनेक्टिविटी n - 1 के बराबर है। n शीर्षों पर हर दूसरे सरल ग्राफ़ में सख्ती से छोटे किनारे-कनेक्टिविटी हैं।
* एक [[पेड़ (ग्राफ सिद्धांत)]] में, हर जोड़ी के बीच स्थानीय बढ़त-कनेक्टिविटी होती है {{math|1}}.
* एक [[पेड़ (ग्राफ सिद्धांत)]] में प्रत्येक जोड़ी के बीच स्थानीय बढ़त-कनेक्टिविटी {{math|1}} है|


== कनेक्टिविटी पर सीमा ==
== कनेक्टिविटी पर सीमा ==
* किसी ग्राफ की वर्टेक्स-कनेक्टिविटी उसके एज-कनेक्टिविटी से कम या उसके बराबर होती है। वह है, {{math|''κ''(''G'') ≤ ''λ''(''G'')}}. दोनों ग्राफ़ की डिग्री (ग्राफ़ सिद्धांत) से कम या उसके बराबर हैं, क्योंकि न्यूनतम डिग्री के शीर्ष के सभी पड़ोसियों को हटाने से उस शीर्ष को बाकी ग्राफ़ से अलग कर दिया जाएगा।<ref name="diestel">{{cite web|last=Diestel|first=R.|url=http://diestel-graph-theory.com/GrTh.html|title=ग्राफ थ्योरी, इलेक्ट्रॉनिक संस्करण|date=2005|pages=12}}</ref>
* किसी ग्राफ की वर्टेक्स-कनेक्टिविटी उसके एज-कनेक्टिविटी से कम या उसके बराबर होती है। वह {{math|''κ''(''G'') ≤ ''λ''(''G'')}} है| दोनों ग्राफ़ की न्यूनतम डिग्री (ग्राफ़ सिद्धांत) से कम या उसके बराबर हैं| क्योंकि न्यूनतम डिग्री के शीर्ष के सभी पड़ोसियों को हटाने से उस शीर्ष को शेष ग्राफ़ से अलग कर दिया जाएगा।<ref name="diestel">{{cite web|last=Diestel|first=R.|url=http://diestel-graph-theory.com/GrTh.html|title=ग्राफ थ्योरी, इलेक्ट्रॉनिक संस्करण|date=2005|pages=12}}</ref>
* डिग्री के [[शीर्ष-सकर्मक ग्राफ]] के लिए (ग्राफ सिद्धांत) {{mvar|d}}, अपने पास: {{math|2(''d'' + 1)/3 ≤ ''κ''(''G'') ≤ ''λ''(''G'') {{=}} ''d''}}.<ref name="GandR">{{cite book|title=बीजगणितीय ग्राफ सिद्धांत| last1=Godsil | first1=C. |author1-link=Chris Godsil| last2=Royle| first2=G.| author2-link=Gordon Royle|year=2001|publisher=Springer Verlag}}</ref>
* डिग्री {{mvar|d}} के [[शीर्ष-सकर्मक ग्राफ]] के लिए (ग्राफ सिद्धांत) हमारे पास: {{math|2(''d'' + 1)/3 ≤ ''κ''(''G'') ≤ ''λ''(''G'') {{=}} ''d''}} है|<ref name="GandR">{{cite book|title=बीजगणितीय ग्राफ सिद्धांत| last1=Godsil | first1=C. |author1-link=Chris Godsil| last2=Royle| first2=G.| author2-link=Gordon Royle|year=2001|publisher=Springer Verlag}}</ref>
* डिग्री के शीर्ष-सकर्मक ग्राफ के लिए (ग्राफ सिद्धांत) {{math|''d'' ≤ 4}}, या किसी भी (अप्रत्यक्ष) डिग्री के न्यूनतम [[केली ग्राफ]] (ग्राफ सिद्धांत) के लिए {{mvar|d}}, या डिग्री के किसी [[सममित ग्राफ]] के लिए (ग्राफ सिद्धांत) {{mvar|d}}, दोनों प्रकार की कनेक्टिविटी समान हैं: {{math|''κ''(''G'') {{=}} ''λ''(''G'') {{=}} ''d''}}.<ref>{{cite book|title=ऑटोमोर्फिज्म समूह, आइसोमोर्फिज्म, पुनर्निर्माण|series=Technical Report TR-94-10|author=Babai, L.|author-link=László Babai|year=1996|publisher=University of Chicago|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|url-status=dead|archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|archive-date=2010-06-11}} Chapter 27 of ''The Handbook of Combinatorics''.</ref>
* डिग्री {{math|''d'' ≤ 4}} के शीर्ष-संक्रमणीय ग्राफ के लिए (ग्राफ सिद्धांत) या डिग्री {{mvar|d}} के किसी भी (अप्रत्यक्ष) न्यूनतम [[केली ग्राफ]] (ग्राफ सिद्धांत) के लिए या डिग्री {{mvar|d}} के किसी भी [[सममित ग्राफ]] के लिए (ग्राफ सिद्धांत) दोनों प्रकार की कनेक्टिविटी {{math|''κ''(''G'') {{=}} ''λ''(''G'') {{=}} ''d''}} के समान हैं|<ref>{{cite book|title=ऑटोमोर्फिज्म समूह, आइसोमोर्फिज्म, पुनर्निर्माण|series=Technical Report TR-94-10|author=Babai, L.|author-link=László Babai|year=1996|publisher=University of Chicago|url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|url-status=dead|archive-url=https://web.archive.org/web/20100611212234/http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|archive-date=2010-06-11}} Chapter 27 of ''The Handbook of Combinatorics''.</ref>




== अन्य गुण ==
== अन्य गुण ==
* जुड़ाव को [[ग्राफ समरूपता]] द्वारा संरक्षित किया जाता है।
* जुड़ाव को [[ग्राफ समरूपता]] द्वारा संरक्षित किया जाता है।
* यदि {{mvar|G}} जुड़ा हुआ है तो इसका [[लाइन ग्राफ]] {{math|''L''(''G'')}} भी जुड़ा हुआ है।
* यदि {{mvar|G}} जुड़ा है तो इसका [[लाइन ग्राफ]] {{math|''L''(''G'')}} भी जुड़ा है।
* एक ग्राफ {{mvar|G}} है {{math|2}}-एज-कनेक्टेड [[अगर और केवल अगर|यदि और केवल यदि]] इसमें एक ओरिएंटेशन है जो दृढ़ता से जुड़ा हुआ है।
* ग्राफ {{mvar|G}} {{math|2}} किनारे से जुड़ा हुआ है| [[अगर और केवल अगर|और यदि केवल]] इसमें एक अभिविन्यास है| जो दृढ़ता से जुड़ा हुआ है।
* बालिंस्की के प्रमेय में कहा गया है कि [[पॉलीटॉपल ग्राफ]] ({{math|1}}-[[कंकाल (टोपोलॉजी)]]) का a {{mvar|k}}-विमीय उत्तल [[polytope]] एक है {{mvar|k}}-वर्टेक्स-कनेक्टेड ग्राफ।<ref>{{cite journal|author = Balinski, M. L.|title = On the graph structure of convex polyhedra in {{mvar|n}}-space|journal = [[Pacific Journal of Mathematics]]|volume = 11|issue = 2|year = 1961|pages = 431–434|doi = 10.2140/pjm.1961.11.431|doi-access = free}}</ref> [[अर्नेस्ट स्टीनिट्ज़]] का पिछला प्रमेय कि कोई भी 3-वर्टेक्स-कनेक्टेड [[ प्लेनर ग्राफ ]]़ एक पॉलीटोपल ग्राफ़ है (स्टीनिट्ज़ प्रमेय) एक आंशिक बातचीत देता है।
* बालिंस्की की प्रमेय में कहा गया है कि {{mvar|k}} आयामी उत्तल [[पॉलीटॉपल ग्राफ|पॉलीटॉप का पॉलीटोपल ग्राफ]] ({{math|1}}-[[कंकाल (टोपोलॉजी)]]) का एक {{mvar|k}}-वर्टेक्स-कनेक्टेड ग्राफ है।<ref>{{cite journal|author = Balinski, M. L.|title = On the graph structure of convex polyhedra in {{mvar|n}}-space|journal = [[Pacific Journal of Mathematics]]|volume = 11|issue = 2|year = 1961|pages = 431–434|doi = 10.2140/pjm.1961.11.431|doi-access = free}}</ref> [[अर्नेस्ट स्टीनिट्ज़]] का पिछला प्रमेय कि कोई भी 3-वर्टेक्स-कनेक्टेड [[ प्लेनर ग्राफ |प्लेनर ग्राफ]] पॉलीटोपल ग्राफ़ है| (स्टीनिट्ज़ प्रमेय) आंशिक वार्तालाप देता है।
* गेब्रियल एंड्रयू डिराक के एक प्रमेय के अनुसार | जी। ए Dirac, यदि एक ग्राफ है {{mvar|k}}-के लिए जुड़ा हुआ है {{math|''k'' ≥ 2}}, फिर प्रत्येक समुच्चय के लिए {{mvar|k}} ग्राफ़ में शीर्षों पर एक चक्र होता है जो समुच्चय के सभी शीर्षों से होकर गुजरता है।<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | author-link = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao
* जी ए डिराक के एक प्रमेय के अनुसार यदि एक ग्राफ {{math|''k'' ≥ 2}} के लिए {{mvar|k}} कनेक्टेड है तो ग्राफ में {{mvar|k}} के प्रत्येक समुच्चय के लिए एक चक्र होता है| जो समुच्चय के सभी शीर्षों से होकर गुजरता है।<ref>{{Cite journal | last = Dirac | first = Gabriel Andrew | author-link = Gabriel Andrew Dirac | journal = [[Mathematische Nachrichten]] | pages = 61–85 | title = In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen | volume = 22 | issue = 1–2 | year = 1960 | mr = 0121311 | doi = 10.1002/mana.19600220107}}.</ref><ref>{{Cite journal | last1 = Flandrin | first1 = Evelyne | last2 = Li | first2 = Hao
  | last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8
  | last3 = Marczyk | first3 = Antoni | last4 = Woźniak | first4 = Mariusz | doi = 10.1016/j.disc.2005.11.052 | issue = 7–8
  | journal = Discrete Mathematics | pages = 878–884 | title = A generalization of Dirac's theorem on cycles through {{mvar|k}} vertices in {{mvar|k}}-connected graphs | volume = 307 | year = 2007 | mr = 2297171| doi-access = free }}.</ref> विलोम सत्य है जब {{math|''k'' {{=}} 2}}.
  | journal = Discrete Mathematics | pages = 878–884 | title = A generalization of Dirac's theorem on cycles through {{mvar|k}} vertices in {{mvar|k}}-connected graphs | volume = 307 | year = 2007 | mr = 2297171| doi-access = free }}.</ref> जब {{math|''k'' {{=}} 2}} हो तो विलोम सही होता है|


== यह भी देखें ==
== यह भी देखें ==
* [[बीजगणितीय कनेक्टिविटी]]
* [[बीजगणितीय कनेक्टिविटी]]
* चीजर स्थिरांक (ग्राफ सिद्धांत)
* चीजर स्थिरांक (ग्राफ सिद्धांत)
* [[गतिशील कनेक्टिविटी]], [[विसंधित-सेट डेटा संरचना|विसंधित-समुच्चय डेटा संरचना]]
* [[गतिशील कनेक्टिविटी]] [[विसंधित-सेट डेटा संरचना|विसंधित-समुच्चय डेटा संरचना]]
* [[विस्तारक ग्राफ]]
* [[विस्तारक ग्राफ]]
* [[एक ग्राफ की ताकत]]
* [[एक ग्राफ की ताकत|ग्राफ की शक्ति]]


== संदर्भ ==
== संदर्भ ==
{{reflist}}
{{reflist}}
[[Category: ग्राफ कनेक्टिविटी | ग्राफ कनेक्टिविटी ]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 errors]]
[[Category:Created On 08/05/2023]]
[[Category:Created On 08/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ कनेक्टिविटी| ग्राफ कनेक्टिविटी ]]

Latest revision as of 17:54, 18 May 2023

यह ग्राफ़ तब डिस्कनेक्ट हो जाता है जब बाईं ओर ग्रे क्षेत्र में सबसे दाएँ-दाएँ नोड को हटा दिया जाता है
धराशायी किनारे को हटा दिए जाने पर यह ग्राफ़ डिस्कनेक्ट हो जाता है।

गणित और कंप्यूटर विज्ञान में कनेक्टिविटी ग्राफ़ सिद्धांत की मूल अवधारणाओं में से एक है| यह तत्वों की न्यूनतम संख्या (नोड्स या किनारों) के लिए पूछता है| जिन्हें शेष नोड्स को दो या अधिक कनेक्टेड घटक (ग्राफ़ सिद्धांत) में अलग करने के लिए निकालने की आवश्यकता होती है।[1] यह प्रवाह नेटवर्क समस्याओं के सिद्धांत से निकटता से संबंधित है। नेटवर्क के रूप में ग्राफ की कनेक्टिविटी इसकी कोमलता का महत्वपूर्ण उपाय है।

जुड़े हुए शिखर और रेखांकन

वर्टेक्स 0 के साथ यह ग्राफ डिस्कनेक्ट हो गया है। बाकी ग्राफ जुड़ा हुआ है।

अप्रत्यक्ष ग्राफ 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]


मेंजर की प्रमेय

Main article: मेंजर की प्रमेय

ग्राफ़ में कनेक्टिविटी के बारे में सबसे महत्वपूर्ण तथ्यों में से मेन्जर की प्रमेय है| जो कोने के बीच स्वतंत्र पथों की संख्या के संदर्भ में ग्राफ की कनेक्टिविटी और किनारे-कनेक्टिविटी की विशेषता है।

यदि 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] यह तथ्य वास्तव में मैक्स-फ्लो मिन-कट प्रमेय का विशेष स्थितियाँ है।

कम्प्यूटेशनल पहलू

यह निर्धारित करने की समस्या कि क्या किसी ग्राफ़ में दो कोने जुड़े हुए हैं| खोज एल्गोरिदम जैसे चौड़ाई-प्रथम खोज का उपयोग करके कुशलतापूर्वक हल किया जा सकता है। सामान्यतः कम्प्यूटेशनल रूप से यह निर्धारित करना आसान होता है कि कोई ग्राफ़ कनेक्ट है या नहीं (उदाहरण के लिए डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर एप्लिकेशन|डिसजॉइंट-समुच्चय डेटा स्ट्रक्चर का उपयोग करके) या कनेक्टेड घटकों की संख्या की गणना करने के लिए। छद्म कोड में साधारण एल्गोरिदम निम्नानुसार लिखा जा सकता है|

  1. ग्राफ के किसी भी इच्छानुकूल G नोड पर शुरू करें|
  2. उस नोड से या तो डेप्थ-फर्स्ट या विड्थ-फर्स्ट सर्च का उपयोग करके आगे बढ़ें और सभी नोड्स की गणना करें।
  3. एक बार ग्राफ़ को पूरी तरह से पार हो जाने के बाद यदि गिने हुए नोड्स की संख्या G के नोड्स की संख्या के बराबर है तो ग्राफ जुड़ा हुआ है| अन्यथा यह डिस्कनेक्ट हो गया है।

मेन्जर के प्रमेय के अनुसार कनेक्टेड ग्राफ़ G में किन्हीं दो शीर्षों u और v के लिए संख्या κ(u, v) और λ(u, v) को अधिकतम-प्रवाह न्यूनतम-कट एल्गोरिथम का उपयोग करके कुशलता से निर्धारित किया जा सकता है। G की कनेक्टिविटी और एज कनेक्टिविटी की गणना क्रमशः κ(u, v) और λ(u, v) के न्यूनतम मूल्यों के रूप में की जा सकती है।

कम्प्यूटेशनल जटिलता सिद्धांत में [[एसएल (जटिलता)]] लॉग-स्पेस समस्याओं का वर्ग है| जो यह निर्धारित करने की समस्या के लिए कम हो जाता है कि ग्राफ में दो कोने जुड़े हुए हैं| जो 2004 में ओमर रीनॉल्ड द्वारा एल (जटिलता) के बराबर सिद्ध हुआ था।[9] इसलिए अप्रत्यक्ष ग्राफ कनेक्टिविटी को O(log n) स्थान में हल किया जा सकता है।

संभाव्यता की गणना करने की समस्या है कि एक बर्नौली वितरण यादृच्छिक ग्राफ जुड़ा हुआ है जिसे नेटवर्क विश्वसनीयता कहा जाता है| और यह गणना करने की समस्या है कि दो दिए गए कोने एसटी-विश्वसनीयता समस्या से जुड़े हैं या नहीं। ये दोनों पी-हार्ड हैं।[10]


जुड़े हुए रेखांकन की संख्या

Main article: ग्राफ गणना

एन नोड्स के साथ अलग-अलग जुड़े लेबल वाले ग्राफ़ की संख्या अनुक्रम A001187 के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में सारणीबद्ध है| पहले कुछ दूसरा-नगण्य शब्द हैं|

4 नोड्स के साथ जुड़े ग्राफ़ की संख्या और छवियां
n रेखांकन
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 किनारे से जुड़ा हुआ है| और यदि केवल इसमें एक अभिविन्यास है| जो दृढ़ता से जुड़ा हुआ है।
  • बालिंस्की की प्रमेय में कहा गया है कि k आयामी उत्तल पॉलीटॉप का पॉलीटोपल ग्राफ (1-कंकाल (टोपोलॉजी)) का एक k-वर्टेक्स-कनेक्टेड ग्राफ है।[13] अर्नेस्ट स्टीनिट्ज़ का पिछला प्रमेय कि कोई भी 3-वर्टेक्स-कनेक्टेड प्लेनर ग्राफ पॉलीटोपल ग्राफ़ है| (स्टीनिट्ज़ प्रमेय) आंशिक वार्तालाप देता है।
  • जी ए डिराक के एक प्रमेय के अनुसार यदि एक ग्राफ k ≥ 2 के लिए k कनेक्टेड है तो ग्राफ में k के प्रत्येक समुच्चय के लिए एक चक्र होता है| जो समुच्चय के सभी शीर्षों से होकर गुजरता है।[14][15] जब k = 2 हो तो विलोम सही होता है|

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Diestel, R. (2005). "ग्राफ थ्योरी, इलेक्ट्रॉनिक संस्करण". p. 12.
  2. ↑ Chapter 11: Digraphs: Principle of duality for digraphs: Definition
  3. ↑ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.
  4. ↑ Liu, Qinghai; Zhang, Zhao (2010-03-01). "दो प्रकार की प्रतिबंधित कनेक्टिविटी के लिए अस्तित्व और ऊपरी सीमा". Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.
  5. ↑ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.
  6. ↑ Balbuena, Camino; Carmona, Angeles (2001-10-01). "द्विपक्षीय डिग्राफ और ग्राफ की कनेक्टिविटी और सुपरकनेक्टिविटी पर". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
  7. ↑ Gibbons, A. (1985). एल्गोरिथम ग्राफ थ्योरी. Cambridge University Press.
  8. ↑ Nagamochi, H.; Ibaraki, T. (2008). ग्राफ कनेक्टिविटी के एल्गोरिदमिक पहलू. Cambridge University Press.
  9. ↑ Reingold, Omer (2008). "लॉग-स्पेस में अप्रत्यक्ष कनेक्टिविटी". Journal of the ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478.
  10. ↑ 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..
  11. ↑ Godsil, C.; Royle, G. (2001). बीजगणितीय ग्राफ सिद्धांत. Springer Verlag.
  12. ↑ 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.
  13. ↑ 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)
  14. ↑ 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..
  15. ↑ 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).
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=कनेक्टिविटी_(ग्राफ_सिद्धांत)&oldid=163515’