क्लिक-सम: Difference between revisions
(Created page with "{{Short description|Gluing graphs at complete subgraphs}} Image:Clique-sum.svg|thumb|upright=1.35|दो प्लानर ग्राफ़ और वैगनर ग्...") |
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|दो प्लानर | [[Image:Clique-sum.svg|thumb|upright=1.35|दो प्लानर आरेख और वैगनर आरेख का एक क्लिक-योग, एक K बनाता है<sub>5</sub>-मामूली मुक्त ग्राफ।]]आरेख सिद्धांत में, गणित की शाखा '''क्लिक-सम''', दो आरेख को एक आरेख सिद्धांत क्लिक पर एक साथ चिपकाकर जोड़ने की एक विधि है, जो [[टोपोलॉजी|सांस्थितिकी]] में [[जुड़ा योग|युग्म योग]] संक्रिया के अनुरूप है। यदि दो आरेख ''G'' और ''H'' प्रत्येक में समान आकार के समूह होते हैं, तो ''G'' और ''H'' का क्लिक-योग उनके क्लिक युग्म से बनता है, जो संयुक्त युग्म की पहचान करता है। इन दो समूहों में एक साझा समूह बनाने के लिए, समूहों के कुछ शीर्षों को हटा दिया जाता है। के-क्लिक-सम एक क्लिक-योग है जिसमें दोनों समूहों में अधिक से अधिक ''k'' शीर्ष होते हैं। दो-आरेख क्लिक-सम संक्रिया के बार-बार उपयोग से, दो से अधिक आरेख के क्लिक-सम और ''k ''- क्लिक-सम भी बनाए जा सकते हैं। | ||
विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम | विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम संक्रिया के भाग के रूप में किन शीर्षों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे [[कॉर्डल ग्राफ|कॉर्डल]] आरेख या [[गला घोंटने वाला ग्राफ|स्ट्रानगुलटेड ग्राफ]] का अपघटन करने पर, किसी भी शीर्ष को हटाया नहीं जाना चाहिए। अन्य संदर्भों में, जैसे [[ SPQR-पेड़ | एसपीक्यूआर -वृक्ष]] आरेख का उनके 3-युग्म-शीर्ष घटकों में अपघटन होने पर, सभी शीर्षों को हटा दिया जाना चाहिए। और अभी तक अन्य संदर्भों में, जैसे सरल रेखांकन के छोटे-बंद परिवारों के लिए [[ग्राफ संरचना प्रमेय]], संक्रिया के भाग के रूप में हटाए गए शीर्षों के समुच्चय को निर्दिष्ट करने की अनुमति देना स्वाभाविक है। | ||
== संबंधित अवधारणाएं == | == संबंधित अवधारणाएं == | ||
क्लिक-सम का [[ पेड़ की चौड़ाई ]] के साथ घनिष्ठ संबंध है: यदि दो | क्लिक-सम का [[ पेड़ की चौड़ाई ]] के साथ घनिष्ठ संबंध है: यदि दो आरेख में ट्रीविड्थ अधिकतम k है, तो उनका k-क्लिक-सम भी होता है। हर पेड़ (ग्राफ थ्योरी) उसके किनारों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में ट्रेविड्थ के साथ अधिकतम दो, त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k पर ट्रीविड्थ वाला प्रत्येक आरेख अधिकतम k + 1 कोने वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।<ref name="l">{{harvtxt|Lovász|2006}}.</ref> | ||
क्लिक-सम और [[ग्राफ कनेक्टिविटी]] के बीच एक करीबी संबंध भी है: यदि कोई | क्लिक-सम और [[ग्राफ कनेक्टिविटी]] के बीच एक करीबी संबंध भी है: यदि कोई आरेख k-वर्टेक्स-कनेक्टेड आरेख नहीं है|(k + 1)-वर्टेक्स-कनेक्टेड (ताकि वहाँ k वर्टिस का एक सेट मौजूद हो जिसे हटाने से डिस्कनेक्ट हो जाता है ग्राफ) तो इसे छोटे ग्राफों के के-क्लिक-योग के रूप में दर्शाया जा सकता है। उदाहरण के लिए, एक द्विसंबद्ध ग्राफ का SPQR ट्री अपने [[त्रिसंबद्ध घटक]]ों के 2-क्लिक-योग के रूप में ग्राफ का प्रतिनिधित्व करता है। | ||
== ग्राफ संरचना सिद्धांत में अनुप्रयोग == | == ग्राफ संरचना सिद्धांत में अनुप्रयोग == | ||
[[File:Strangulated graph.svg|thumb|upright=1.1|समतलीय ग्राफ (पीला) और दो कॉर्डल ग्राफ (लाल और नीला) के एक क्लिक योग के रूप में गठित एक अजनबी ग्राफ]] | [[File:Strangulated graph.svg|thumb|upright=1.1|समतलीय ग्राफ (पीला) और दो कॉर्डल ग्राफ (लाल और नीला) के एक क्लिक योग के रूप में गठित एक अजनबी ग्राफ]]आरेख संरचना सिद्धांत में क्लिक-रकम महत्वपूर्ण हैं, जहाँ उनका उपयोग आरेख के कुछ परिवारों को चिह्नित करने के लिए किया जाता है, क्योंकि सरल आरेख के क्लिक-रकम द्वारा बनाए गए आरेख। इस प्रकार का पहला परिणाम<ref>As credited by {{harvtxt|Kříž|Thomas|1990}}, who list several additional clique-sum-based characterizations of graph families.</ref> का एक प्रमेय था {{harvtxt|Wagner|1937}}, जिन्होंने यह साबित किया कि जिन आरेख में माइनर (आरेख थ्योरी) के रूप में पांच-शीर्ष पूर्ण आरेख नहीं है, वे आठ-वर्टेक्स [[वैगनर ग्राफ|वैगनर]] आरेख के साथ [[समतल रेखांकन]] के 3-क्लिक-राशि हैं; इस संरचना प्रमेय का उपयोग यह दिखाने के लिए किया जा सकता है कि [[चार रंग प्रमेय]] [[हैडविगर अनुमान (ग्राफ सिद्धांत)]] के केस k = 5 के बराबर है। कॉर्डल आरेख बिल्कुल ऐसे आरेख हैं जो किसी भी किनारों को हटाए बिना क्लिक्स के क्लिक-सम द्वारा बनाए जा सकते हैं, और स्ट्रैंग्युलेटेड आरेख वे आरेख हैं जो किनारों को हटाए बिना क्लिक्स के क्लिक-सम और [[अधिकतम प्लानर ग्राफ|अधिकतम प्लानर]] आरेख द्वारा बनाए जा सकते हैं।<ref>{{harvtxt|Seymour|Weaver|1984}}.</ref> वे आरेख जिनमें लंबाई चार या उससे अधिक का प्रत्येक [[प्रेरित सबग्राफ]] आरेख का एक न्यूनतम विभाजक बनाता है (इसका निष्कासन आरेख को दो या दो से अधिक डिस्कनेक्ट किए गए घटकों में विभाजित करता है, और चक्र के किसी भी उपसमुच्चय में समान गुण नहीं होते हैं) वास्तव में क्लिक-रकम हैं क्लिक्स और मैक्सिमम प्लानर ग्राफ, फिर से एज डिलीट किए बिना।<ref>{{harvtxt|Diestel|1987}}.</ref> {{harvtxt|Johnson|McKee|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-रकम (एक ग्राफ में फैले पेड़ों का प्रतिनिधित्व करने वाले मैट्रोइड्स), कॉग्राफिक मैट्रोड्स और एक निश्चित 10-एलिमेंट मैट्रोइड्स के रूप में दर्शाता है।<ref name="l" /><ref>{{harvtxt|Seymour|1980}}.</ref> | ||
Revision as of 09:37, 1 May 2023
आरेख सिद्धांत में, गणित की शाखा क्लिक-सम, दो आरेख को एक आरेख सिद्धांत क्लिक पर एक साथ चिपकाकर जोड़ने की एक विधि है, जो सांस्थितिकी में युग्म योग संक्रिया के अनुरूप है। यदि दो आरेख G और H प्रत्येक में समान आकार के समूह होते हैं, तो G और H का क्लिक-योग उनके क्लिक युग्म से बनता है, जो संयुक्त युग्म की पहचान करता है। इन दो समूहों में एक साझा समूह बनाने के लिए, समूहों के कुछ शीर्षों को हटा दिया जाता है। के-क्लिक-सम एक क्लिक-योग है जिसमें दोनों समूहों में अधिक से अधिक k शीर्ष होते हैं। दो-आरेख क्लिक-सम संक्रिया के बार-बार उपयोग से, दो से अधिक आरेख के क्लिक-सम और k - क्लिक-सम भी बनाए जा सकते हैं।
विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम संक्रिया के भाग के रूप में किन शीर्षों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे कॉर्डल आरेख या स्ट्रानगुलटेड ग्राफ का अपघटन करने पर, किसी भी शीर्ष को हटाया नहीं जाना चाहिए। अन्य संदर्भों में, जैसे एसपीक्यूआर -वृक्ष आरेख का उनके 3-युग्म-शीर्ष घटकों में अपघटन होने पर, सभी शीर्षों को हटा दिया जाना चाहिए। और अभी तक अन्य संदर्भों में, जैसे सरल रेखांकन के छोटे-बंद परिवारों के लिए ग्राफ संरचना प्रमेय, संक्रिया के भाग के रूप में हटाए गए शीर्षों के समुच्चय को निर्दिष्ट करने की अनुमति देना स्वाभाविक है।
संबंधित अवधारणाएं
क्लिक-सम का पेड़ की चौड़ाई के साथ घनिष्ठ संबंध है: यदि दो आरेख में ट्रीविड्थ अधिकतम k है, तो उनका k-क्लिक-सम भी होता है। हर पेड़ (ग्राफ थ्योरी) उसके किनारों का 1-क्लिक-योग है। प्रत्येक श्रृंखला-समानांतर आरेख, या अधिक सामान्यतः प्रत्येक आरेख में ट्रेविड्थ के साथ अधिकतम दो, त्रिकोण के 2-क्लिक-योग के रूप में बन सकते हैं। एक ही प्रकार का परिणाम k के बड़े मानों तक विस्तारित होता है: अधिकतम k पर ट्रीविड्थ वाला प्रत्येक आरेख अधिकतम k + 1 कोने वाले आरेख के क्लिक-योग के रूप में बनाया जा सकता है; यह आवश्यक रूप से एक k-क्लिक-योग है।[1] क्लिक-सम और ग्राफ कनेक्टिविटी के बीच एक करीबी संबंध भी है: यदि कोई आरेख k-वर्टेक्स-कनेक्टेड आरेख नहीं है|(k + 1)-वर्टेक्स-कनेक्टेड (ताकि वहाँ k वर्टिस का एक सेट मौजूद हो जिसे हटाने से डिस्कनेक्ट हो जाता है ग्राफ) तो इसे छोटे ग्राफों के के-क्लिक-योग के रूप में दर्शाया जा सकता है। उदाहरण के लिए, एक द्विसंबद्ध ग्राफ का SPQR ट्री अपने त्रिसंबद्ध घटकों के 2-क्लिक-योग के रूप में ग्राफ का प्रतिनिधित्व करता है।
ग्राफ संरचना सिद्धांत में अनुप्रयोग
आरेख संरचना सिद्धांत में क्लिक-रकम महत्वपूर्ण हैं, जहाँ उनका उपयोग आरेख के कुछ परिवारों को चिह्नित करने के लिए किया जाता है, क्योंकि सरल आरेख के क्लिक-रकम द्वारा बनाए गए आरेख। इस प्रकार का पहला परिणाम[2] का एक प्रमेय था Wagner (1937), जिन्होंने यह साबित किया कि जिन आरेख में माइनर (आरेख थ्योरी) के रूप में पांच-शीर्ष पूर्ण आरेख नहीं है, वे आठ-वर्टेक्स वैगनर आरेख के साथ समतल रेखांकन के 3-क्लिक-राशि हैं; इस संरचना प्रमेय का उपयोग यह दिखाने के लिए किया जा सकता है कि चार रंग प्रमेय हैडविगर अनुमान (ग्राफ सिद्धांत) के केस k = 5 के बराबर है। कॉर्डल आरेख बिल्कुल ऐसे आरेख हैं जो किसी भी किनारों को हटाए बिना क्लिक्स के क्लिक-सम द्वारा बनाए जा सकते हैं, और स्ट्रैंग्युलेटेड आरेख वे आरेख हैं जो किनारों को हटाए बिना क्लिक्स के क्लिक-सम और अधिकतम प्लानर आरेख द्वारा बनाए जा सकते हैं।[3] वे आरेख जिनमें लंबाई चार या उससे अधिक का प्रत्येक प्रेरित सबग्राफ आरेख का एक न्यूनतम विभाजक बनाता है (इसका निष्कासन आरेख को दो या दो से अधिक डिस्कनेक्ट किए गए घटकों में विभाजित करता है, और चक्र के किसी भी उपसमुच्चय में समान गुण नहीं होते हैं) वास्तव में क्लिक-रकम हैं क्लिक्स और मैक्सिमम प्लानर ग्राफ, फिर से एज डिलीट किए बिना।[4] Johnson & McKee (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.
