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

ग्राफ़ सिद्धांत में, एक कनेक्टेड ग्राफ़ (असतत गणित) हैk-एज-कनेक्टेड यदि यह कनेक्टिविटी (ग्राफ सिद्धांत) से कम होने पर भी रहता है kकिनारे हटा दिए जाते हैं.

ग्राफ़ की एज-कनेक्टिविटी सबसे बड़ी होती है k जिसके लिए ग्राफ़ है k-किनारे से जुड़ा हुआ।

एज कनेक्टिविटी और ग्राफ गणना k-एज-कनेक्टेड ग्राफ़ का अध्ययन 1869 में केमिली जॉर्डन द्वारा किया गया था।

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

एक 2-किनारे से जुड़ा ग्राफ़

होने देना $G=(V,E)$ एक मनमाना ग्राफ बनें.

यदि ग्राफ़ सिद्धांत#सबग्राफ़ की शब्दावली $G'=(V,E\setminus X)$ सभी के लिए जुड़ा हुआ है $X\subseteq E$ कहाँ $|X|<k$, तो G को k-एज-कनेक्टेड कहा जाता है। की एज कनेक्टिविटी $G$ अधिकतम मान k इस प्रकार है कि G, k-किनारे से जुड़ा हुआ है। सबसे छोटा सेट X जिसका निष्कासन G को डिस्कनेक्ट करता है, G में न्यूनतम कटौती है।

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

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

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

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

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

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

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

एक बेहतर एल्गोरिदम प्रत्येक जोड़ी (यू, वी) के लिए अधिकतम प्रवाह समस्या का समाधान करेगा जहां यू को मनमाने ढंग से तय किया गया है जबकि वी भिन्न होता है सभी शिखरों पर. इससे जटिलता कम हो जाती है $O(n^{4})$ और तब से सही है, यदि k से कम क्षमता का Cut_(graph_theory) मौजूद है, यह आपको किसी अन्य शीर्ष से अलग करने के लिए बाध्य है। इसे हेरोल्ड एन. गैबो के एल्गोरिदम द्वारा और बेहतर बनाया जा सकता है जो सबसे खराब स्थिति में चलता है $O(n^{3})$ समय। कार्गर के एल्गोरिदम का कार्गर-स्टीन संस्करण अपेक्षित रनटाइम के साथ कनेक्टिविटी निर्धारित करने के लिए एक तेज़ यादृच्छिक एल्गोरिदम प्रदान करता है $O(n^{2}\log ^{3}n)$. एक संबंधित समस्या: जी का न्यूनतम के-एज-कनेक्टेड स्पैनिंग सबग्राफ ढूंढना (यानी: जी में जितना संभव हो उतना कम किनारों का चयन करें ताकि आपका चयन के-एज-कनेक्टेड हो) एनपी-कठिन है $k\geq 2$.

यह भी देखें

• के-वर्टेक्स-कनेक्टेड ग्राफ़
• कनेक्टिविटी (ग्राफ सिद्धांत)
• मिलान बहिष्करण