क्लिक-सम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Gluing graphs at complete subgraphs}} | {{Short description|Gluing graphs at complete subgraphs}} | ||
[[Image:Clique-sum.svg|thumb|upright=1.35|दो समतलक आरेख और वैगनर आरेख का एक क्लिक-योग, एक K बनाता है<sub>5</sub>-मामूली मुक्त | [[Image:Clique-sum.svg|thumb|upright=1.35|दो समतलक आरेख और वैगनर आरेख का एक क्लिक-योग, एक K बनाता है<sub>5</sub>-मामूली मुक्त आरेख।]]आरेख सिद्धांत में, गणित की शाखा '''क्लिक-सम''', दो आरेख को एक आरेख सिद्धांत क्लिक पर एक साथ चिपकाकर जोड़ने की एक विधि है, जो [[टोपोलॉजी|सांस्थितिकी]] में [[जुड़ा योग|युग्म योग]] संक्रिया के अनुरूप है। यदि दो आरेख ''G'' और ''H'' प्रत्येक में समान आकार के समूह होते हैं, तो ''G'' और ''H'' का क्लिक-योग उनके क्लिक युग्म से बनता है, जो संयुक्त युग्म की पहचान करता है। इन दो समूहों में एक साझा समूह बनाने के लिए, समूहों के कुछ शीर्षों को हटा दिया जाता है। के-क्लिक-सम एक क्लिक-योग है जिसमें दोनों समूहों में अधिक से अधिक ''k'' शीर्ष होते हैं। दो-आरेख क्लिक-सम संक्रिया के बार-बार उपयोग से, दो से अधिक आरेख के क्लिक-सम और ''k ''- क्लिक-सम भी बनाए जा सकते हैं। | ||
विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम संक्रिया के भाग के रूप में किन शीर्षों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे [[कॉर्डल ग्राफ|कॉर्डल]] आरेख या [[गला घोंटने वाला ग्राफ|स्ट्रानगुलटेड | विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम संक्रिया के भाग के रूप में किन शीर्षों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे [[कॉर्डल ग्राफ|कॉर्डल]] आरेख या [[गला घोंटने वाला ग्राफ|स्ट्रानगुलटेड आरेख]] का अपघटन करने पर, किसी भी शीर्ष को हटाया नहीं जाना चाहिए। अन्य संदर्भों में, जैसे [[ SPQR-पेड़ |एसपीक्यूआर -वृक्ष]] आरेख का उनके 3-युग्म-शीर्ष घटकों में अपघटन होने पर, सभी शीर्षों को हटा दिया जाना चाहिए। और अभी तक अन्य संदर्भों में, जैसे सरल रेखांकन के छोटे-बंद समूहों के लिए [[ग्राफ संरचना प्रमेय|आरेख संरचना प्रमेय]], संक्रिया के भाग के रूप में हटाए गए शीर्षों के समुच्चय को निर्दिष्ट करने की अनुमति देना स्वाभाविक है। | ||
== संबंधित अवधारणाएं == | == संबंधित अवधारणाएं == | ||
क्लीक-सम के साथ [[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] का निकट संबंध होता है: यदि दो आरेखों का वृक्षदैर्ध्य अधिकतम k है, तो उनका k-क्लीक-सम भी k या उससे कम वृक्षदैर्ध्य वाला होगा। आरेख सिद्धांत में प्रत्येक वृक्ष उसके शीर्षों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में [[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] के साथ अधिकतम त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k वृक्षदैर्ध्य वाला प्रत्येक आरेख अधिकतम k + 1 शीर्ष वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।<ref name="l">{{harvtxt|Lovász|2006}}.</ref> | क्लीक-सम के साथ [[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] का निकट संबंध होता है: यदि दो आरेखों का वृक्षदैर्ध्य अधिकतम k है, तो उनका k-क्लीक-सम भी k या उससे कम वृक्षदैर्ध्य वाला होगा। आरेख सिद्धांत में प्रत्येक वृक्ष उसके शीर्षों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में [[ पेड़ की चौड़ाई |वृक्षदैर्ध्य]] के साथ अधिकतम त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k वृक्षदैर्ध्य वाला प्रत्येक आरेख अधिकतम k + 1 शीर्ष वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।<ref name="l">{{harvtxt|Lovász|2006}}.</ref> | ||
क्लिक-सम और [[ग्राफ कनेक्टिविटी| | क्लिक-सम और [[ग्राफ कनेक्टिविटी|आरेख]] संयोजन के मध्य एक निकट संबंध भी है: यदि एक आरेख (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> | ||
== सामान्यीकरण == | == सामान्यीकरण == | ||
क्लिक्स-सम्स के सिद्धांत को आरेख से [[matroid]] तक सामान्यीकृत किया जा सकता है।<ref name="l" />विशेष रूप से, सीमोर का अपघटन प्रमेय नियमित मैट्रोइड्स ([[पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स]] द्वारा प्रतिनिधित्व करने योग्य मैट्रोइड्स) को [[ग्राफिक मैट्रोइड]]्स के 3-रकम (एक | क्लिक्स-सम्स के सिद्धांत को आरेख से [[matroid]] तक सामान्यीकृत किया जा सकता है।<ref name="l" />विशेष रूप से, सीमोर का अपघटन प्रमेय नियमित मैट्रोइड्स ([[पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स]] द्वारा प्रतिनिधित्व करने योग्य मैट्रोइड्स) को [[ग्राफिक मैट्रोइड|आरेखिक मैट्रोइड]]्स के 3-रकम (एक आरेख में फैले पेड़ों का प्रतिनिधित्व करने वाले मैट्रोइड्स), कॉआरेखिक मैट्रोड्स और एक निश्चित 10-एलिमेंट मैट्रोइड्स के रूप में दर्शाता है।<ref name="l" /><ref>{{harvtxt|Seymour|1980}}.</ref> | ||
Revision as of 11:19, 1 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]
सामान्यीकरण
क्लिक्स-सम्स के सिद्धांत को आरेख से matroid तक सामान्यीकृत किया जा सकता है।[1]विशेष रूप से, सीमोर का अपघटन प्रमेय नियमित मैट्रोइड्स (पूरी तरह से यूनिमॉड्यूलर मैट्रिक्स द्वारा प्रतिनिधित्व करने योग्य मैट्रोइड्स) को आरेखिक मैट्रोइड्स के 3-रकम (एक आरेख में फैले पेड़ों का प्रतिनिधित्व करने वाले मैट्रोइड्स), कॉआरेखिक मैट्रोड्स और एक निश्चित 10-एलिमेंट मैट्रोइड्स के रूप में दर्शाता है।[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.
