क्लिक-सम: Difference between revisions
No edit summary |
|||
| Line 5: | Line 5: | ||
== संबंधित अवधारणाएं == | == संबंधित अवधारणाएं == | ||
[[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] क्लिक-सम के साथ का निकट संबंध होता है: यदि दो आरेखों का वृक्षदैर्ध्य अधिकतम k है, तो उनका k-क्लिक-योग भी k या उससे कम वृक्षदैर्ध्य वाला होगा। आरेख सिद्धांत में प्रत्येक वृक्ष उसके शीर्षों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में [[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] के साथ अधिकतम त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k वृक्षदैर्ध्य वाला प्रत्येक आरेख अधिकतम k + 1 शीर्ष वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।<ref name="l">{{harvtxt|Lovász|2006}}.</ref> | |||
क्लिक-सम और [[ग्राफ कनेक्टिविटी|आरेख]] संयोजन के मध्य एक निकट संबंध भी है: यदि एक आरेख (k+1)-शीर्ष-संयोजित नहीं है (जिससे ऐसे k शीर्ष का समुच्चय उपलब्ध हो जो आरेख को विसंयोजित कर देते हैं) तो उसे | क्लिक-सम और [[ग्राफ कनेक्टिविटी|आरेख]] संयोजन के मध्य एक निकट संबंध भी है: यदि एक आरेख (k+1)-शीर्ष-संयोजित नहीं है (जिससे ऐसे k शीर्ष का समुच्चय उपलब्ध हो जो आरेख को विसंयोजित कर देते हैं) तो उसे छोटे आरेखों के कुछ समूह का क्लिक-योग रूप में व्यक्त किया जा सकता है। उदाहरण के लिए, एक द्विसंबद्ध आरेख का एसपीक्यूआर-वृक्ष अपने [[त्रिसंबद्ध घटक|त्रिसंबद्ध घट]]कों के 2-क्लिक-योग के रूप में आरेख का प्रतिनिधित्व करता है। | ||
== आरेख संरचना सिद्धांत में अनुप्रयोग == | == आरेख संरचना सिद्धांत में अनुप्रयोग == | ||
[[File:Strangulated graph.svg|thumb|upright=1.1|समतलीय आरेख (पीला) और दो कॉर्डल आरेख (लाल और नीला) के एक क्लिक योग के रूप में गठित एक आरेख]]क्लिक-योग आरेख संरचना सिद्धांत में महत्वपूर्ण होते हैं, जहाँ वे कुछ निश्चित | [[File:Strangulated graph.svg|thumb|upright=1.1|समतलीय आरेख (पीला) और दो कॉर्डल आरेख (लाल और नीला) के एक क्लिक योग के रूप में गठित एक आरेख]]क्लिक-योग आरेख संरचना सिद्धांत में महत्वपूर्ण होते हैं, जहाँ वे कुछ निश्चित समूहों के आरेख को चरित्रित करने के लिए प्रयोग किए जाते हैं, जो सरल आरेखों के क्लिक-योग के रूप में संदर्भित होते हैं। इस प्रकार के प्रथम परिणामों में से एक, वागनर (1937) का सिद्धांत था, जिसने प्रमाणित किया था कि पांच-शीर्ष पूर्ण आरेख को सूक्ष्म नहीं करने वाले आरेख केवल वो हैं जो आठ-शीर्ष वागनर आरेख के साथ योजनात्मक आरेख के 3-क्लिक-योग से बने होते हैं; इस संरचना का सिद्धांत का अर्थ है कि केवल पांच-शीर्ष पूर्णता के स्थिति में हडविगर के परिकल्पना का एक विशेष संस्करण होता है।<ref>As credited by {{harvtxt|Kříž|Thomas|1990}}, who list several additional clique-sum-based characterizations of graph families.</ref> चोर्डल आरेख उन आरेखों को कहते हैं जो क्लिकों के क्लिक-समूहों के युग्म से बनाए जा सकते हैं, जहां कोई एक भी समूह नहीं हटाया जाता है। वहीं, स्ट्रैंग्युलेटेड आरेख वे आरेख होते हैं जो क्लिकों और [[अधिकतम प्लानर ग्राफ|अधिकतम ज्यामितीय]] आरेखों के क्लिक-समूहों के युग्म से बनाए जा सकते हैं, जहां कोई एक भी समूह नहीं हटाया जाता है।<ref>{{harvtxt|Seymour|Weaver|1984}}.</ref>उन आरेखों को जिनमें हर आविष्कृत चक्र चार या उससे अधिक का गुणक आरेख का एक न्यूनतम विभाजक बनाता है (इसके हटाने से आरेख को दो या दो से अधिक भिन्न-भिन्न भागों में विभाजित किया जाता है और चक्र का कोई भी उपसमूह इसी गुणवत्ता के साथ नहीं होता है) केवल क्लिकों और अधिकतम त्रिकोणीय आरेखों के क्लिक-योग से बनाए जाते हैं, फिर भी किसी भी शीर्ष को हटाने की आवश्यकता नहीं होती है। <ref>{{harvtxt|Diestel|1987}}.</ref> {{harvtxt|जॉनसन|मैकी|1996}} ने समानांतर आरेख और कोर्डल आरेख के क्लिक-योजनों का उपयोग करके पूर्णगुण पूर्ति वाले आंशिक आव्यूहों को वर्णन करने के लिए क्लिक-योजनों का उपयोग किया। | ||
आरेख वर्ग के लिए क्लीक-योग विभाजन का निर्धारण किसी भी आरेख | आरेख वर्ग के लिए क्लीक-योग विभाजन का निर्धारण किसी भी आरेख समूह के लिए संभव होता है जो आरेख सूक्ष्म-संक्रिया के अंतर्गत बंद होता है: प्रत्येक सूक्ष्म-बंद समूह के आरेख को सीमित जीनस वाले सतहों पर "लगभग स्थापित" आरेख के क्लीक-योग से बनाया जा सकता है, जिसका अर्थ होता है कि एक छोटी सी संख्या के एपेक्स (वे वर्टेक्स होते हैं जो सुरेखों के किसी भी उपसमूह से जुड़े हो सकते हैं) और शीर्ष (पथचौड़ाई कम होने वाले आरेख होते हैं जो सतह की स्थितियों को परिवर्तित करते हैं) की छूट की अनुमति होती है।<ref>{{harvtxt|Robertson|Seymour|2003}}</ref> इन विशेषताओं का उपयोग सन्निकटन विधिकलन के निर्माण में एक महत्वपूर्ण उपकरण के रूप में किया गया है और लघु-बंद आरेख समूहों पर एनपी-पूर्ण अनुकूलन समस्याओं के लिए उप-घातीय-समय सटीक विधिकलन हैं।<ref>{{harvtxt|Demaine|Hajiaghayi|Nishimura|Ragde|2004}}; {{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2005}}; {{harvtxt|Demaine|Hajiaghayi|Kawarabayashi|2005}}.</ref> | ||
Revision as of 12:38, 2 May 2023
आरेख सिद्धांत में, गणित की एक शाखा क्लिक-सम, दो आरेखो को किसी शीर्ष पर एक साथ युग्मित करने की एक विधि है, जो सांस्थितिकी मे प्रयोग होने वाले युग्म योग संक्रिया के अनुरूप है। यदि दो आरेख G और H, प्रत्येक में समान आकार के समूह होते हैं, तो G और H का योग उनके क्लिक युग्म से बनता है, जो संयुक्त युग्म की पहचान करता है। इन दो समूहों में एक सहभाजित समूह बनाने के लिए, समूहों के कुछ शीर्षों को हटा दिया जाता है। के-क्लिक-सम, एक क्लिक-योग है जिसमें दोनों समूहों में अधिक से अधिक k शीर्ष होते हैं। दो-आरेख क्लिक-सम संक्रिया के बार-बार उपयोग से, दो से अधिक आरेख के क्लिक-सम और k - क्लिक-सम भी बनाए जा सकते हैं।
विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम संक्रिया के भाग के रूप में किन शीर्षों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे कॉर्डल आरेख या स्ट्रानगुलटेड आरेख का अपघटन करने पर, किसी भी शीर्ष को हटाया नहीं जाता है। अन्य संदर्भों में, जैसे एसपीक्यूआर -वृक्ष आरेख का उनके 3-युग्म-शीर्ष घटकों में अपघटन होने पर, सभी शीर्षों को हटा दिया जाता है। और अभी तक अन्य संदर्भों में, जैसे सरल रेखांकन के छोटे-बंद समूहों के लिए आरेख संरचना प्रमेय, संक्रिया के भाग के रूप में हटाए गए शीर्षों के समुच्चय को निर्दिष्ट करने की अनुमति प्रदान करता है।
संबंधित अवधारणाएं
वृक्षदैर्ध्य क्लिक-सम के साथ का निकट संबंध होता है: यदि दो आरेखों का वृक्षदैर्ध्य अधिकतम k है, तो उनका k-क्लिक-योग भी k या उससे कम वृक्षदैर्ध्य वाला होगा। आरेख सिद्धांत में प्रत्येक वृक्ष उसके शीर्षों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में वृक्षदैर्ध्य के साथ अधिकतम त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k वृक्षदैर्ध्य वाला प्रत्येक आरेख अधिकतम k + 1 शीर्ष वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।[1]
क्लिक-सम और आरेख संयोजन के मध्य एक निकट संबंध भी है: यदि एक आरेख (k+1)-शीर्ष-संयोजित नहीं है (जिससे ऐसे k शीर्ष का समुच्चय उपलब्ध हो जो आरेख को विसंयोजित कर देते हैं) तो उसे छोटे आरेखों के कुछ समूह का क्लिक-योग रूप में व्यक्त किया जा सकता है। उदाहरण के लिए, एक द्विसंबद्ध आरेख का एसपीक्यूआर-वृक्ष अपने त्रिसंबद्ध घटकों के 2-क्लिक-योग के रूप में आरेख का प्रतिनिधित्व करता है।
आरेख संरचना सिद्धांत में अनुप्रयोग
क्लिक-योग आरेख संरचना सिद्धांत में महत्वपूर्ण होते हैं, जहाँ वे कुछ निश्चित समूहों के आरेख को चरित्रित करने के लिए प्रयोग किए जाते हैं, जो सरल आरेखों के क्लिक-योग के रूप में संदर्भित होते हैं। इस प्रकार के प्रथम परिणामों में से एक, वागनर (1937) का सिद्धांत था, जिसने प्रमाणित किया था कि पांच-शीर्ष पूर्ण आरेख को सूक्ष्म नहीं करने वाले आरेख केवल वो हैं जो आठ-शीर्ष वागनर आरेख के साथ योजनात्मक आरेख के 3-क्लिक-योग से बने होते हैं; इस संरचना का सिद्धांत का अर्थ है कि केवल पांच-शीर्ष पूर्णता के स्थिति में हडविगर के परिकल्पना का एक विशेष संस्करण होता है।[2] चोर्डल आरेख उन आरेखों को कहते हैं जो क्लिकों के क्लिक-समूहों के युग्म से बनाए जा सकते हैं, जहां कोई एक भी समूह नहीं हटाया जाता है। वहीं, स्ट्रैंग्युलेटेड आरेख वे आरेख होते हैं जो क्लिकों और अधिकतम ज्यामितीय आरेखों के क्लिक-समूहों के युग्म से बनाए जा सकते हैं, जहां कोई एक भी समूह नहीं हटाया जाता है।[3]उन आरेखों को जिनमें हर आविष्कृत चक्र चार या उससे अधिक का गुणक आरेख का एक न्यूनतम विभाजक बनाता है (इसके हटाने से आरेख को दो या दो से अधिक भिन्न-भिन्न भागों में विभाजित किया जाता है और चक्र का कोई भी उपसमूह इसी गुणवत्ता के साथ नहीं होता है) केवल क्लिकों और अधिकतम त्रिकोणीय आरेखों के क्लिक-योग से बनाए जाते हैं, फिर भी किसी भी शीर्ष को हटाने की आवश्यकता नहीं होती है। [4] जॉनसन & मैकी (1996) ने समानांतर आरेख और कोर्डल आरेख के क्लिक-योजनों का उपयोग करके पूर्णगुण पूर्ति वाले आंशिक आव्यूहों को वर्णन करने के लिए क्लिक-योजनों का उपयोग किया।
आरेख वर्ग के लिए क्लीक-योग विभाजन का निर्धारण किसी भी आरेख समूह के लिए संभव होता है जो आरेख सूक्ष्म-संक्रिया के अंतर्गत बंद होता है: प्रत्येक सूक्ष्म-बंद समूह के आरेख को सीमित जीनस वाले सतहों पर "लगभग स्थापित" आरेख के क्लीक-योग से बनाया जा सकता है, जिसका अर्थ होता है कि एक छोटी सी संख्या के एपेक्स (वे वर्टेक्स होते हैं जो सुरेखों के किसी भी उपसमूह से जुड़े हो सकते हैं) और शीर्ष (पथचौड़ाई कम होने वाले आरेख होते हैं जो सतह की स्थितियों को परिवर्तित करते हैं) की छूट की अनुमति होती है।[5] इन विशेषताओं का उपयोग सन्निकटन विधिकलन के निर्माण में एक महत्वपूर्ण उपकरण के रूप में किया गया है और लघु-बंद आरेख समूहों पर एनपी-पूर्ण अनुकूलन समस्याओं के लिए उप-घातीय-समय सटीक विधिकलन हैं।[6]
सामान्यीकरण
क्लिक्स-योग के सिद्धांत को आरेख से आव्यूह तक सामान्यीकृत किया जा सकता है।[1]ध्यान दें कि "मैट्रॉइड" एक गणितीय वस्तु होती है जो ग्राफ की संरचना को अधिक अनुकूल ढंग से वर्णित करती है। इसे विशेष रूप से आधार समझौतों के रूप में देखा जाता है।[1][7]
टिप्पणियाँ
- ↑ 1.0 1.1 1.2 Lovász (2006).
- ↑ As credited by Kříž & Thomas (1990), who list several additional clique-sum-based characterizations of graph families.
- ↑ Seymour & Weaver (1984).
- ↑ Diestel (1987).
- ↑ Robertson & Seymour (2003)
- ↑ Demaine et al. (2004); Demaine et al. (2005); Demaine, Hajiaghayi & Kawarabayashi (2005).
- ↑ Seymour (1980).
संदर्भ
- Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammedTaghi; Thilikos, Dimitrios (2005), "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs", Journal of the ACM, 52 (6): 866–893, arXiv:1104.2230, doi:10.1145/1101821.1101823, MR 2179550.
- Demaine, Erik D.; Hajiaghayi, MohammedTaghi; Nishimura, Naomi; Ragde, Prabhakar; Thilikos, Dimitrios (2004), "Approximation algorithms for classes of graphs excluding single-crossing graphs as minors", Journal of Computer and System Sciences, 69 (2): 166–195, doi:10.1016/j.jcss.2003.12.001, MR 2077379.
- Demaine, Erik D.; Hajiaghayi, MohammedTaghi; Kawarabayashi, Ken-ichi (2005), "Algorithmic graph minor theory: decomposition, approximation, and coloring" (PDF), Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (PDF), pp. 637–646, doi:10.1109/SFCS.2005.14.
- Diestel, Reinhard (1987), "A separation property of planar triangulations", Journal of Graph Theory, 11 (1): 43–52, doi:10.1002/jgt.3190110108, MR 0876203.
- Kříž, Igor; Thomas, Robin (1990), "Clique-sums, tree-decompositions and compactness", Discrete Mathematics, 81 (2): 177–185, doi:10.1016/0012-365X(90)90150-G, MR 1054976.
- Johnson, Charles R.; McKee, Terry A. (1996), "Structural conditions for cycle completable graphs", Discrete Mathematics, 159 (1–3): 155–160, doi:10.1016/0012-365X(95)00107-8, MR 1415290.
- Lovász, László (2006), "Graph minor theory", Bulletin of the American Mathematical Society, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8, MR 2188176.
- Robertson, N.; Seymour, P. D. (2003), "Graph minors XVI. Excluding a non-planar graph", Journal of Combinatorial Theory, Series B, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X, MR 1999736.
- Seymour, P. D. (1980), "Decomposition of regular matroids", Journal of Combinatorial Theory, Series B, 28 (3): 305–359, doi:10.1016/0095-8956(80)90075-1, MR 0579077.
- Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
- Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen, 114: 570–590, doi:10.1007/BF01594196.
