के-एज-कनेक्टेड ग्राफ़: Difference between revisions

From Vigyanwiki
(Created page with "{{DISPLAYTITLE:''k''-edge-connected graph}} {{short description|Graph which remains connected when k or fewer edges removed}} ग्राफ़ सिद्धांत म...")
 
No edit summary
Line 2: Line 2:
{{short description|Graph which remains connected when k or fewer edges removed}}
{{short description|Graph which remains connected when k or fewer edges removed}}


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


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


एज कनेक्टिविटी और [[ग्राफ गणना]] {{mvar|k}}-एज-कनेक्टेड ग्राफ़ का अध्ययन 1869 में [[केमिली जॉर्डन]] द्वारा किया गया था।<ref>{{cite journal
अश्रि अनुयोजकता और [[ग्राफ गणना|लेखाचित्र गणना]] '''{{mvar|k}}-अश्रि-आनुषंगिक लेखाचित्र''' का अध्ययन 1869 में [[केमिली जॉर्डन]] द्वारा किया गया था। <ref>{{cite journal
| last        = Jordan
| last        = Jordan
| first      = Camille
| first      = Camille
Line 22: Line 22:


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


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


एज कनेक्टिविटी [[परिधि (ग्राफ़ सिद्धांत)]] की दोहरी अवधारणा है, एक ग्राफ़ में सबसे छोटे चक्र की लंबाई, इस अर्थ में कि एक समतल ग्राफ़ की परिधि उसके दोहरे ग्राफ़ की किनारे कनेक्टिविटी है, और इसके विपरीत। इन अवधारणाओं को [[मैट्रोइड सिद्धांत]] में मैट्रोइड परिधि द्वारा एकीकृत किया गया है, जो मैट्रोइड में सबसे छोटे आश्रित सेट का आकार है। एक [[ग्राफ़िक मैट्रोइड]] के लिए, मैट्रोइड परिधि अंतर्निहित ग्राफ़ की परिधि के बराबर होती है, जबकि एक सह-ग्राफ़िक मैट्रोइड के लिए यह किनारे की कनेक्टिविटी के बराबर होती है।<ref>{{citation
अश्रि अनुयोजकता [[परिधि (ग्राफ़ सिद्धांत)|परिधि (लेखाचित्र सिद्धांत)]] की दोहरी अवधारणा है, एक लेखाचित्र में सबसे छोटे चक्र की लंबाई, इस अर्थ में कि एक समतल लेखाचित्र की परिधि उसके दोहरे लेखाचित्र की किनारे अनुयोजकता और इसके विपरीत है। इन अवधारणाओं को [[मैट्रोइड सिद्धांत]] में मैट्रोइड परिधि द्वारा एकीकृत किया गया है, जो मैट्रोइड में सबसे छोटे आश्रित सम्मुच्चय का आकार है। एक [[ग्राफ़िक मैट्रोइड|लेखाचित्रिक मैट्रोइड]] के लिए, मैट्रोइड परिधि अंतर्निहित लेखाचित्र की परिधि के बराबर होती है, जबकि एक सह-लेखाचित्रिक मैट्रोइड के लिए यह किनारे की अनुयोजकता के बराबर होती है।<ref>{{citation
  | last1 = Cho | first1 = Jung Jin
  | last1 = Cho | first1 = Jung Jin
  | last2 = Chen | first2 = Yong
  | last2 = Chen | first2 = Yong
Line 44: Line 42:
  | year = 2007| doi-access = free
  | year = 2007| doi-access = free
  }}.</ref>
  }}.</ref>
2-किनारे से जुड़े ग्राफ़ को [[ब्रिज (ग्राफ़ सिद्धांत)]] की अनुपस्थिति, कान के विघटन के अस्तित्व, या रॉबिन्स प्रमेय द्वारा भी चित्रित किया जा सकता है, जिसके अनुसार ये बिल्कुल ऐसे ग्राफ़ हैं जिनका एक [[मजबूत अभिविन्यास]] है।<ref>{{cite journal
 
2-किनारे से जुड़े लेखाचित्र को [[ब्रिज (ग्राफ़ सिद्धांत)|ब्रिज (लेखाचित्र सिद्धांत)]] की अनुपस्थिति, कान के विघटन के अस्तित्व, या रॉबिन्स प्रमेय द्वारा भी चित्रित किया जा सकता है, जिसके अनुसार ये बिल्कुल ऐसे लेखाचित्र हैं जिनका एक [[मजबूत अभिविन्यास|शक्तिशाली अभिविन्यास]] है। <ref>{{cite journal
  | last = Robbins | first = H. E. | author-link = Herbert Robbins
  | last = Robbins | first = H. E. | author-link = Herbert Robbins
  | journal = [[American Mathematical Monthly]]
  | journal = [[American Mathematical Monthly]]
Line 55: Line 54:




== कम्प्यूटेशनल पहलू ==
सबसे बड़े 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> कुल मिलाकर।
== अभिकलनात्मक दृष्टिकोण ==
सबसे बड़े 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>


एक बेहतर एल्गोरिदम प्रत्येक जोड़ी (यू, वी) के लिए अधिकतम प्रवाह समस्या का समाधान करेगा जहां यू को मनमाने ढंग से तय किया गया है जबकि वी भिन्न होता है
सभी शिखरों पर. इससे जटिलता कम हो जाती है <math>O(n^4)</math> और तब से सही है, यदि k से कम क्षमता का Cut_(graph_theory) मौजूद है,
यह आपको किसी अन्य शीर्ष से अलग करने के लिए बाध्य है। इसे हेरोल्ड एन. गैबो के एल्गोरिदम द्वारा और बेहतर बनाया जा सकता है जो सबसे खराब स्थिति में चलता है <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>
एक संबंधित समस्या: जी का न्यूनतम के-एज-कनेक्टेड स्पैनिंग सबग्राफ ढूंढना (यानी: जी में जितना संभव हो उतना कम किनारों का चयन करें ताकि आपका चयन के-एज-कनेक्टेड हो) एनपी-कठिन है <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>




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


Revision as of 13:40, 12 August 2023

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

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

अश्रि अनुयोजकता और लेखाचित्र गणना k-अश्रि-आनुषंगिक लेखाचित्र का अध्ययन 1869 में केमिली जॉर्डन द्वारा किया गया था। [1]


औपचारिक परिभाषा

एक 2-छोर से जुड़ा लेखाचित्र

मान लीजिये एक स्वेच्छाचारी लेखाचित्र है। यदि सबलेखाचित्र की शब्दावली सभी के लिए आनुषंगिक है, जहाँ , तो G को k-अश्रि-आनुषंगिक कहा जाता है। की अश्रि अनुयोजकता अधिकतम मान k इस प्रकार है कि G, k-किनारे से आनुषंगिक है। सबसे छोटा सम्मुच्चय X जिसका निष्कासन G को पृथक करता है, वह G में न्यूनतम कटौती है।

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

संबंधित अवधारणाएँ

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

अश्रि अनुयोजकता परिधि (लेखाचित्र सिद्धांत) की दोहरी अवधारणा है, एक लेखाचित्र में सबसे छोटे चक्र की लंबाई, इस अर्थ में कि एक समतल लेखाचित्र की परिधि उसके दोहरे लेखाचित्र की किनारे अनुयोजकता और इसके विपरीत है। इन अवधारणाओं को मैट्रोइड सिद्धांत में मैट्रोइड परिधि द्वारा एकीकृत किया गया है, जो मैट्रोइड में सबसे छोटे आश्रित सम्मुच्चय का आकार है। एक लेखाचित्रिक मैट्रोइड के लिए, मैट्रोइड परिधि अंतर्निहित लेखाचित्र की परिधि के बराबर होती है, जबकि एक सह-लेखाचित्रिक मैट्रोइड के लिए यह किनारे की अनुयोजकता के बराबर होती है।[2]

2-किनारे से जुड़े लेखाचित्र को ब्रिज (लेखाचित्र सिद्धांत) की अनुपस्थिति, कान के विघटन के अस्तित्व, या रॉबिन्स प्रमेय द्वारा भी चित्रित किया जा सकता है, जिसके अनुसार ये बिल्कुल ऐसे लेखाचित्र हैं जिनका एक शक्तिशाली अभिविन्यास है। [3]


अभिकलनात्मक दृष्टिकोण

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

यदि n लेखाचित्र में शीर्षों की संख्या है, तो यह सरल एल्गोरिदम कार्य करेगा अधिकतम प्रवाह समस्या की पुनरावृत्ति, जिसे समय में हल किया जा सकता है। इसलिए ऊपर वर्णित सरल एल्गोरिदम की जटिलता कुल मिलाकर है।

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

यह जटिलता को तक कम कर देता है और उचित है, यदि k से कम क्षमता का कट मौजूद है, तो यह u को किसी अन्य शीर्ष से अलग करने के लिए बाध्य है। इसे गैबो के एल्गोरिदम द्वारा और बेहतर बनाया जा सकता है जो सबसे खराब स्थिति समय में चलता है। [4]

कार्गर के एल्गोरिदम का कार्गर-स्टीन संस्करण अपेक्षित कार्यावधि के साथ अनुयोजकता निर्धारित करने के लिए एक तीव्र यादृच्छिक एल्गोरिदम प्रदान करता है। [5]

एक संबंधित समस्या: G का न्यूनतम के-अश्रि-आनुषंगिक विस्तरित सबलेखाचित्र ढूंढना (यानी: जी में जितना संभव हो उतना कम किनारों का चयन करें ताकि आपका चयन के-अश्रि-आनुषंगिक हो) के लिए एनपी-कठोर है। [6]


यह भी देखें

संदर्भ

  1. ↑ Jordan, Camille (1869). "Sur les assemblages de lignes". Journal für die reine und angewandte Mathematik (in français). 70 (2): 185–190.
  2. ↑ Cho, Jung Jin; Chen, Yong; Ding, Yu (2007), "On the (co)girth of a connected matroid", Discrete Applied Mathematics, 155 (18): 2456–2470, doi:10.1016/j.dam.2007.06.015, MR 2365057.
  3. ↑ Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem on traffic control". American Mathematical Monthly. 46: 281–283. doi:10.2307/2303897. JSTOR 2303897.
  4. ↑ Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
  5. ↑ Karger, David R.; Stein, Clifford (1996). "न्यूनतम कटौती की समस्या के लिए एक नया दृष्टिकोण" (PDF). Journal of the ACM. 43 (4): 601. doi:10.1145/234533.234534.
  6. ↑ M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=के-एज-कनेक्टेड_ग्राफ़&oldid=261701’