प्रेरित मिलान

ग्राफ़ सिद्धांत में, एक प्रेरित मिलान या मजबूत मिलान एक अप्रत्यक्ष ग्राफ़ के किनारों का एक उपसमुच्चय है जो किसी भी शिखर को साझा नहीं करता है (यह एक मिलान (ग्राफ़ सिद्धांत) है) और इसमें उपसमुच्चय में किसी भी दो कोने को जोड़ने वाला हर किनारा शामिल है (यह है एक प्रेरित सबग्राफ)।

दिए गए ग्राफ़ के लाइन ग्राफ़ की ग्राफ़ शक्ति में एक प्रेरित मिलान को एक स्वतंत्र सेट (ग्राफ़ सिद्धांत) के रूप में भी वर्णित किया जा सकता है।

मजबूत रंग और पड़ोस

प्रेरित मिलानों की न्यूनतम संख्या जिसमें एक ग्राफ के किनारों को विभाजित किया जा सकता है, को इसका मजबूत रंगीन सूचकांक कहा जाता है, ग्राफ के क्रोमैटिक इंडेक्स के अनुरूप, मिलान की न्यूनतम संख्या जिसमें इसके किनारों को विभाजित किया जा सकता है। यह रेखा ग्राफ के वर्ग की रंगीन संख्या के बराबर है। ब्रूक्स प्रमेय, रेखा ग्राफ के वर्ग पर लागू, दिखाता है कि दिए गए ग्राफ की अधिकतम डिग्री में मजबूत रंगीन सूचकांक सबसे अधिक द्विघात है, लेकिन द्विघात सीमा में बेहतर स्थिर कारक अन्य तरीकों से प्राप्त किए जा सकते हैं।

रूजसा-ज़ेमेरीडी समस्या रैखिक मजबूत रंगीन सूचकांक के साथ संतुलित द्विदलीय रेखांकन के किनारे घनत्व से संबंधित है। समान रूप से, यह ग्राफ़ के एक अलग वर्ग के घनत्व से संबंधित है, स्थानीय रूप से रेखीय ग्राफ़ जिसमें प्रत्येक शीर्ष का पड़ोस (ग्राफ़ सिद्धांत) एक प्रेरित मिलान है। इनमें से किसी भी प्रकार के ग्राफ़ में किनारों की द्विघात संख्या नहीं हो सकती है, लेकिन निर्माण इस प्रकार के ग्राफ़ के लिए जाने जाते हैं जिनमें किनारों की लगभग-द्विघात संख्या होती है।

कम्प्यूटेशनल जटिलता

कम से कम आकार का एक प्रेरित मिलान ढूँढना $k$ एनपी-पूर्ण है (और इस प्रकार, अधिकतम आकार का एक प्रेरित मिलान खोजना एनपी कठिन है)। कॉर्डल ग्राफ़ में इसे बहुपद समय में हल किया जा सकता है, क्योंकि कॉर्डल ग्राफ़ के लाइन ग्राफ़ के वर्ग सही ग्राफ़ हैं। इसके अलावा, इसे कॉर्डल ग्राफ़ में रैखिक समय में हल किया जा सकता है . जब तक बहुपद पदानुक्रम में एक अप्रत्याशित पतन नहीं होता, सबसे बड़ा प्रेरित मिलान किसी के भीतर अनुमानित नहीं किया जा सकता है $n^{1-\varepsilon }$ बहुपद समय में सन्निकटन अनुपात।

समस्या भी Parameterized Complex|W[1]-हार्ड है, जिसका अर्थ है कि किसी दिए गए आकार का एक छोटा प्रेरित मिलान भी खोजना $k$ सभी को आज़माने के क्रूर बल खोज दृष्टिकोण की तुलना में एल्गोरिथम के बहुत तेज़ होने की संभावना नहीं है $k$- किनारों का टूटना। हालांकि, खोजने की समस्या $k$ कोने जिसका निष्कासन एक प्रेरित मिलान को छोड़ देता है, फिक्स्ड-पैरामीटर ट्रैक्टेबल है। पर भी समस्या का समाधान किया जा सकता है $n$समय में वर्टेक्स रेखांकन $O(1.3752^{n})$ घातीय स्थान के साथ, या समय में $O(1.4231^{n})$ बहुपद स्थान के साथ।

यह भी देखें

• प्रेरित पथ