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

लेखाचित्र सिद्धांत में, एक आनुषंगिक लेखाचित्र (असतत गणित) 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 कम से कम एक पथ से अलग हो जाता है, और शीर्षों का जोड़ा 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})$ है।

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

यह जटिलता को $O(n^{4})$ तक कम कर देता है और उचित है, यदि k से कम क्षमता का कट मौजूद है, तो यह u को किसी अन्य शीर्ष से अलग करने के लिए बाध्य है। इसे गैबो के एल्गोरिदम द्वारा और बेहतर बनाया जा सकता है जो सबसे खराब स्थिति $O(n^{3})$ समय में चलता है।

कार्गर के एल्गोरिदम का कार्गर-स्टीन संस्करण अपेक्षित कार्यावधि के साथ अनुयोजकता निर्धारित करने के लिए एक तीव्र यादृच्छिक एल्गोरिदम $O(n^{2}\log ^{3}n)$ प्रदान करता है।

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

यह भी देखें

• के-कोणबिंदु-आनुषंगिक लेखाचित्र
• अनुयोजकता (लेखाचित्र सिद्धांत)
• मिलान बहिष्करण