प्रेरित मिलान: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 9: Line 9:


== अभिकलनात्मक जटिलता ==
== अभिकलनात्मक जटिलता ==
कम से कम <math>k</math> आकार के प्रेरित मिलान की खोज NP-पूर्ण है (और इस प्रकार अधिकतम आकार का प्रेरित मिलान खोजना [[ एनपी कठिन |NP-कठिन]] है)। [[कॉर्डल ग्राफ]] में इसे बहुपद समय में हल किया जा सकता है क्योंकि कॉर्डल ग्राफ़ के लाइन ग्राफ़ के वर्ग [[सही ग्राफ|आदर्श ग्राफ]] हैं।{{r|cam89}} इसके अतिरिक्त इसे कॉर्डल ग्राफ़ में रैखिक समय में हल किया जा सकता है।{{r|brahoa08}} जब तक [[बहुपद पदानुक्रम]] में अप्रत्याशित पतन नहीं होता तब तक सबसे बड़ा प्रेरित मिलान बहुपद समय में [[सन्निकटन अनुपात]] <math>n^{1-\varepsilon}</math> किसी के भीतर अनुमानित नहीं किया जा सकता है।{{r|cln}}
कम से कम <math>k</math> आकार के प्रेरित मिलान की खोज NP-पूर्ण है (और इस प्रकार अधिकतम आकार का प्रेरित मिलान खोजना [[ एनपी कठिन |NP-कठिन]] है)। [[कॉर्डल ग्राफ]] में इसे बहुपद समय में हल किया जा सकता है क्योंकि कॉर्डल ग्राफ़ के लाइन ग्राफ़ के वर्ग [[सही ग्राफ|आदर्श ग्राफ]] हैं।{{r|cam89}} इसके अतिरिक्त इसे कॉर्डल ग्राफ़ में रैखिक समय में हल किया जा सकता है।{{r|brahoa08}} जब तक [[बहुपद पदानुक्रम]] में अप्रत्याशित पतन नहीं होता तब तक सबसे बड़ा प्रेरित मिलान बहुपद समय में [[सन्निकटन अनुपात]] <math>n^{1-\varepsilon}</math> किसी में अनुमानित नहीं किया जा सकता है।{{r|cln}}


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

Revision as of 22:32, 11 May 2023

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

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

प्रबल रंग और पडोसी

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

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

अभिकलनात्मक जटिलता

कम से कम आकार के प्रेरित मिलान की खोज NP-पूर्ण है (और इस प्रकार अधिकतम आकार का प्रेरित मिलान खोजना NP-कठिन है)। कॉर्डल ग्राफ में इसे बहुपद समय में हल किया जा सकता है क्योंकि कॉर्डल ग्राफ़ के लाइन ग्राफ़ के वर्ग आदर्श ग्राफ हैं।[6] इसके अतिरिक्त इसे कॉर्डल ग्राफ़ में रैखिक समय में हल किया जा सकता है।[7] जब तक बहुपद पदानुक्रम में अप्रत्याशित पतन नहीं होता तब तक सबसे बड़ा प्रेरित मिलान बहुपद समय में सन्निकटन अनुपात किसी में अनुमानित नहीं किया जा सकता है।[8]

W[1]-कठिन (मापदण्ड जटिलता) भी समस्या है जिसका अर्थ है कि किसी दिए गए आकार के छोटे से प्रेरित मिलान को खोजने की संभावना नहीं है जबकि किनारों के सभी - टपल्स का प्रयास करने की विस्तृत बल खोज दृष्टिकोण की तुलना में एल्गोरिथ्म अधिक तीव्र है।[9] जबकि कोने खोजने की समस्या जिसका निष्कासन प्रेरित मिलान को छोड़ देता है, फिक्स्ड-पैरामीटर ट्रैक्टेबल है।[10] वर्टेक्स रेखांकन समय में घातीय स्थान के साथ या समय में बहुपद स्थान के साथ पर भी समस्या का समाधान किया जा सकता है।[11]

यह भी देखें

संदर्भ

  1. ↑ Cameron, Kathie (2004), "Induced matchings in intersection graphs", Discrete Mathematics, 278 (1–3): 1–9, doi:10.1016/j.disc.2003.05.001, MR 2035386
  2. ↑ Fouquet, J.-L.; Jolivet, J.-L. (1983), "Strong edge-colorings of graphs and applications to multi-k-gons", Ars Combinatoria, 16 (A): 141–150, MR 0737086
  3. ↑ Molloy, Michael; Reed, Bruce (1997), "A bound on the strong chromatic index of a graph", Journal of Combinatorial Theory, Series B, 69 (2): 103–109, doi:10.1006/jctb.1997.1724, hdl:1807/9474, MR 1438613
  4. ↑ Fronček, Dalibor (1989), "Locally linear graphs", Mathematica Slovaca, 39 (1): 3–6, hdl:10338.dmlcz/136481, MR 1016323
  5. ↑ Ruzsa, I. Z.; Szemerédi, E. (1978), "Triple systems with no six points carrying three triangles", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18, Amsterdam and New York: North-Holland, pp. 939–945, MR 0519318
  6. ↑ Cameron, Kathie (2008), "Maximum Induced Matchings for Chordal Graphs in Linear Time", Special issue for First Montreal Conference on Combinatorics and Computer Science, 1987, Algorithmica, 52: 440–447, doi:10.1016/0166-218X(92)90275-F, MR 1011265
  7. ↑ Brandstaedt, Andreas; Hoang, Chinh (1989), "Induced matchings", Discrete Applied Mathematics, 24 (1–3): 97–102, doi:10.1007/s00453-007-9045-2
  8. ↑ Chalermsook, Parinya; Laekhanukit, Bundit; Nanongkai, Danupon (2012), "Graph products revisited: tight approximation hardness of induced matching, poset dimension and more", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, Pennsylvania: SIAM, pp. 1557–1576, MR 3202998
  9. ↑ Moser, Hannes; Sikdar, Somnath (2009), "The parameterized complexity of the induced matching problem", Discrete Applied Mathematics, 157 (4): 715–727, doi:10.1016/j.dam.2008.07.011, MR 2499485
  10. ↑ Xiao, Mingyu; Kou, Shaowei (2016), "Almost induced matching: linear kernels and parameterized algorithms", in Heggernes, Pinar (ed.), Graph-Theoretic Concepts in Computer Science: 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22–24, 2016, Revised Selected Papers, Lecture Notes in Computer Science, vol. 9941, Berlin: Springer, pp. 220–232, doi:10.1007/978-3-662-53536-3_19, MR 3593958
  11. ↑ Xiao, Mingyu; Tan, Huan (2017), "Exact algorithms for maximum induced matching", Information and Computation, 256: 196–211, doi:10.1016/j.ic.2017.07.006, MR 3705425
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=प्रेरित_मिलान&oldid=156864’