View source for के-एज-कनेक्टेड ग्राफ़

{{DISPLAYTITLE:''k''-edge-connected graph}}
{{short description|Graph which remains connected when k or fewer edges removed}}

लेखाचित्र सिद्धांत में, एक आनुषंगिक लेखाचित्र (असतत गणित) {{mvar|k}}-अश्रि-आनुषंगिक है यदि यह k से कम किनारों को हटाए जाने पर भी आनुषंगिक रहता है।

लेखाचित्र की अश्रि-अनुयोजकता सबसे बड़ी {{mvar|k}} होती है  जिसके लिए लेखाचित्र {{mvar|k}}-किनारे से आनुषंगिक होता है।

अश्रि अनुयोजकता और [[ग्राफ गणना|लेखाचित्र गणना]] '''{{mvar|k}}-अश्रि-आनुषंगिक लेखाचित्र''' का अध्ययन 1869 में [[केमिली जॉर्डन]] द्वारा किया गया था। <ref>{{cite journal
| last        = Jordan
| first       = Camille
| author-link  = Camille Jordan
| year        = 1869
| title       = Sur les assemblages de lignes
| journal     = [[Journal für die reine und angewandte Mathematik]]
| volume      = 70
| issue       = 2
| pages       = 185–190
| url         = http://resolver.sub.uni-goettingen.de/purl?GDZPPN002153998
| language    = fr
}}</ref>


==औपचारिक परिभाषा==
[[File:2-edge connected graph.svg|thumb|एक 2-छोर से जुड़ा लेखाचित्र]]मान लीजिये <math>G = (V, E)</math> एक स्वेच्छाचारी लेखाचित्र है। यदि सबलेखाचित्र की शब्दावली <math>G' = (V, E \setminus X)</math> सभी <math>X \subseteq E</math> के लिए आनुषंगिक है, जहाँ <math>|X| < k</math>, तो G को k-अश्रि-आनुषंगिक कहा जाता है। <math>G</math> की अश्रि अनुयोजकता अधिकतम मान k इस प्रकार है कि G, k-किनारे से आनुषंगिक है। सबसे छोटा सम्मुच्चय X जिसका निष्कासन G को पृथक करता है, वह G में [[न्यूनतम कटौती]] है।

मेन्जर के प्रमेय का अश्रि अनुयोजकता संस्करण लेखाचित्र में किनारे-असंगठित पथों के संदर्भ में एक वैकल्पिक और समकक्ष लक्षण वर्णन प्रदान करता है। यदि और केवल यदि G के प्रत्येक दो [[शीर्ष (ग्राफ़ सिद्धांत)|शीर्ष (लेखाचित्र सिद्धांत)]] k पथों के अंतिम बिंदु बनाते हैं, जिनमें से कोई भी दो एक दूसरे के साथ किनारा साझा नहीं करते हैं, तो G k-किनारे से आनुषंगिक है। एक दिशा में यह आसान है: यदि इस तरह के पथों की एक प्रणाली उपस्थित है, तो k किनारों से कम का प्रत्येक सम्मुच्चय X कम से कम एक पथ से अलग हो जाता है, और शीर्षों का जोड़ा X हटा दिए जाने के बाद भी एक दूसरे से जुड़ा रहता है। दूसरी दिशा में, लेखाचित्र में शीर्षों की प्रत्येक जोड़ी के लिए पथों की एक प्रणाली का अस्तित्व जिसे कुछ किनारों को हटाकर पृथक नहीं किया जा सकता है,[[ प्रवाह नेटवर्क | प्रवाह संजाल]] के सिद्धांत से [[अधिकतम-प्रवाह न्यूनतम-कट प्रमेय]] का उपयोग करके सिद्ध किया जा सकता है।

==संबंधित अवधारणाएँ==
न्यूनतम [[डिग्री (ग्राफ सिद्धांत)|कोटि (लेखाचित्र सिद्धांत)]] किनारे-अनुयोजकता पर एक तुच्छ ऊपरी सीमा देता है। यानी, यदि एक लेखाचित्र <math>G = (V, E)</math> k-अश्रि-आनुषंगिक है तो यह आवश्यक है कि k ≤ δ(G), जहां δ(G) किसी भी शीर्ष v∈V की न्यूनतम कोटि है। स्पष्ट रुप से, एक शीर्ष, v पर पड़ने वाले सभी किनारों को हटाने से, फिर v लेखाचित्र से पृथक हो जाएगा।

अश्रि अनुयोजकता [[परिधि (ग्राफ़ सिद्धांत)|परिधि (लेखाचित्र सिद्धांत)]] की दोहरी अवधारणा है, एक लेखाचित्र में सबसे छोटे चक्र की लंबाई, इस अर्थ में कि एक समतल लेखाचित्र की परिधि उसके दोहरे लेखाचित्र की किनारे अनुयोजकता और इसके विपरीत है। इन अवधारणाओं को [[मैट्रोइड सिद्धांत]] में मैट्रोइड परिधि द्वारा एकीकृत किया गया है, जो मैट्रोइड में सबसे छोटे आश्रित सम्मुच्चय का आकार है। एक [[ग्राफ़िक मैट्रोइड|लेखाचित्रिक मैट्रोइड]] के लिए, मैट्रोइड परिधि अंतर्निहित लेखाचित्र की परिधि के बराबर होती है, जबकि एक सह-लेखाचित्रिक मैट्रोइड के लिए यह किनारे की अनुयोजकता के बराबर होती है।<ref>{{citation
 | last1 = Cho | first1 = Jung Jin
 | last2 = Chen | first2 = Yong
 | last3 = Ding | first3 = Yu
 | doi = 10.1016/j.dam.2007.06.015
 | issue = 18
 | journal = Discrete Applied Mathematics
 | mr = 2365057
 | pages = 2456–2470
 | title = On the (co)girth of a connected matroid
 | volume = 155
 | year = 2007| doi-access = free
 }}.</ref>

2-किनारे से जुड़े लेखाचित्र को [[ब्रिज (ग्राफ़ सिद्धांत)|ब्रिज (लेखाचित्र सिद्धांत)]] की अनुपस्थिति, कान के विघटन के अस्तित्व, या रॉबिन्स प्रमेय द्वारा भी चित्रित किया जा सकता है, जिसके अनुसार ये बिल्कुल ऐसे लेखाचित्र हैं जिनका एक [[मजबूत अभिविन्यास|शक्तिशाली अभिविन्यास]] है। <ref>{{cite journal
 | last = Robbins | first = H. E. | author-link = Herbert Robbins
 | journal = [[American Mathematical Monthly]]
 | jstor = 2303897
 | pages = 281–283
 | title = A theorem on graphs, with an application to a problem on traffic control
 | volume = 46
 | year = 1939
 | doi=10.2307/2303897}}</ref>



== अभिकलनात्मक दृष्टिकोण ==
सबसे बड़े k को निर्धारित करने के लिए एक बहुपद-समय कलन विधि है जिसके लिए लेखाचित्र G, k-किनारे से आनुषंगिक है। एक सरल कलन विधि, प्रत्येक जोड़ी (u,v) के लिए, दोनों दिशाओं के लिए G में सभी किनारों की क्षमता को 1 पर सम्मुच्चय करके u से v तक [[अधिकतम प्रवाह समस्या]] निर्धारित करेगा। एक लेखाचित्र k-अश्रि-आनुषंगिक होता है यदि और केवल यदि u से v तक अधिकतम प्रवाह किसी भी जोड़ी (u,v) के लिए कम से कम k है, तो k सभी (u,v) के बीच सबसे कम u-v-प्रवाह है।

यदि n लेखाचित्र में शीर्षों की संख्या है, तो यह सरल एल्गोरिदम <math>O(n^2)</math> कार्य करेगा  अधिकतम प्रवाह समस्या की पुनरावृत्ति, जिसे <math>O(n^3)</math> समय में हल किया जा सकता है। इसलिए ऊपर वर्णित सरल एल्गोरिदम की जटिलता कुल मिलाकर  <math>O(n^5)</math> है।

एक बेहतर एल्गोरिदम प्रत्येक जोड़ी (u, v) के लिए अधिकतम प्रवाह समस्या का समाधान करेगा जहां u को स्वेच्छाचारी ढंग से तय किया गया है जबकि v सभी शिखरों पर भिन्न होता है।

यह जटिलता को <math>O(n^4)</math> तक कम कर देता है और उचित है, यदि k से कम क्षमता का कट मौजूद है, तो यह u को किसी अन्य शीर्ष से अलग करने के लिए बाध्य है। इसे गैबो के एल्गोरिदम द्वारा और बेहतर बनाया जा सकता है जो सबसे खराब स्थिति <math>O(n^3)</math> समय में चलता है। <ref>[[Harold N. Gabow]]. A matroid approach to finding edge connectivity and packing arborescences. ''J. Comput. Syst. Sci.'', 50(2):259–273, 1995.</ref>

कार्गर के एल्गोरिदम का कार्गर-स्टीन संस्करण अपेक्षित कार्यावधि के साथ अनुयोजकता निर्धारित करने के लिए एक तीव्र [[यादृच्छिक एल्गोरिदम]] <math>O(n^2\log^3 n)</math> प्रदान करता है। <ref>{{Cite journal | last1 = Karger | first1 = David R. | author-link1 = David Karger| last2 = Stein | first2 = Clifford| author-link2 = Clifford Stein | doi = 10.1145/234533.234534 | title = न्यूनतम कटौती की समस्या के लिए एक नया दृष्टिकोण| journal = Journal of the ACM | volume = 43 | issue = 4 | pages = 601 | year = 1996 | url = http://www.columbia.edu/~cs2035/courses/ieor6614.S09/Contraction.pdf}}</ref>

एक संबंधित समस्या: G का न्यूनतम के-अश्रि-आनुषंगिक विस्तरित सबलेखाचित्र ढूंढना (यानी: जी में जितना संभव हो उतना कम किनारों का चयन करें ताकि आपका चयन के-अश्रि-आनुषंगिक हो) <math>k\geq 2</math> के लिए एनपी-कठोर है। <ref>M.R. Garey and D.S. Johnson. ''Computers and Intractability: a Guide to the Theory of NP-Completeness''. Freeman, San Francisco, CA, 1979.</ref>



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

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



[[Category: Machine Translated Page]]
[[Category:Created On 09/08/2023]]
[[Category:Vigyan Ready]]