क्लिक-सम
ग्राफ़ थ्योरी में, गणित की एक शाखा, एक क्लिक-सम दो ग्राफ़ को एक क्लिक (ग्राफ़ थ्योरी) पर एक साथ चिपकाकर जोड़ने का एक तरीका है, जो टोपोलॉजी में जुड़ा योग ऑपरेशन के अनुरूप है। यदि दो ग्राफ़ G और H प्रत्येक में समान आकार के समूह होते हैं, तो G और H का क्लिक-योग उनके [[गुट (ग्राफ सिद्धांत)]] मिलन से बनता है, जो वर्टिकल जोड़े की पहचान करता है। इन दो गुटों में एक साझा समूह बनाने के लिए, और फिर संभवतः गुट के कुछ किनारों को हटाना। A k-क्लिक-सम एक क्लिक-योग है जिसमें दोनों क्लिक्स में अधिक से अधिक k कोने होते हैं। दो-ग्राफ़ क्लिक-सम ऑपरेशन के बार-बार उपयोग से, दो से अधिक ग्राफ़ के क्लिक-सम और k - क्लिक-सम भी बना सकते हैं।
विभिन्न स्रोत इस बात से असहमत हैं कि क्लिक-सम ऑपरेशन के भाग के रूप में किन किनारों को हटाया जाना चाहिए। कुछ संदर्भों में, जैसे कॉर्डल ग्राफ़ या गला घोंटने वाला ग्राफ का अपघटन, किसी भी किनारे को हटाया नहीं जाना चाहिए। अन्य संदर्भों में, जैसे SPQR-पेड़ ग्राफ़ का उनके 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.
