ब्लॉक ग्राफ
ग्राफ सिद्धांत में, कॉम्बिनेटरियल गणित की एक शाखा, एक ब्लॉक ग्राफ या क्लिक ट्री[1] एक प्रकार का अप्रत्यक्ष ग्राफ है जिसमें प्रत्येक द्विसंबद्ध घटक (ब्लॉक) एक क्लिक (ग्राफ सिद्धांत) है।
ब्लॉक ग्राफ़ को कभी-कभी ग़लती से हुसिमी ट्री कहा जाता है (कोडी हुसिमी के बाद),[2]लेकिन यह नाम कैक्टस ग्राफ को अधिक ठीक से संदर्भित करता है, ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है।[3]
ब्लॉक ग्राफ़ को मनमाने ढंग से अप्रत्यक्ष ग्राफ़ के ब्लॉक के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है।[4]
लक्षण वर्णन
ब्लॉक ग्राफ़ वास्तव में वे ग्राफ़ हैं जिनके लिए, प्रत्येक चार शीर्षों के लिए u, v, x, और y, तीन दूरियों में से सबसे बड़ी दो d(u,v) + d(x,y), d(u,x) + d(v,y), और d(u,y) + d(v,x) हमेशा बराबर होते हैं।[2][5]
उनके पास ग्राफ़ के रूप में एक वर्जित ग्राफ़ लक्षण वर्णन भी है जिसमें डायमंड ग्राफ़ या एक प्रेरित सबग्राफ के रूप में चार या अधिक वर्टिकल का चक्र नहीं है; अर्थात्, वे डायमंड-मुक्त कॉर्डल ग्राफ़ हैं।[5]वे टॉलेमिक ग्राफ भी हैं (कॉर्डल डिस्टेंस-हेरेडिटरी ग्राफ, दूरी-वंशानुगत ग्राफ) जिसमें प्रत्येक दो नोड्स एक दूसरे से दो दूरी पर एक अद्वितीय सबसे छोटे पथ से जुड़े होते हैं,[2]और कॉर्डल ग्राफ़ जिसमें प्रत्येक दो अधिकतम समूहों में अधिक से अधिक एक शीर्ष उभयनिष्ठ होता है।[2]
ग्राफ G एक ब्लॉक ग्राफ है अगर और केवल अगर हर दो कनेक्टिविटी (ग्राफ सिद्धांत) का प्रतिच्छेदन उपसमुच्चय का सबसेट है G खाली है या जुड़ा हुआ है। इसलिए, कनेक्टेड ब्लॉक ग्राफ़ में वर्टिकल के जुड़े उपसमुच्चय एक एंटिमेट्र बनाते हैं, एक ऐसी संपत्ति जो किसी भी ग्राफ़ के लिए सही नहीं है जो ब्लॉक ग्राफ़ नहीं हैं।[6] इस संपत्ति के कारण, कनेक्टेड ब्लॉक ग्राफ़ में, कोने के प्रत्येक सेट में एक अद्वितीय न्यूनतम कनेक्टेड अधिसमुच्चय होता है, जो उत्तल ज्यामिति में बंद होता है। कनेक्टेड ब्लॉक ग्राफ़ बिल्कुल ऐसे ग्राफ़ हैं जिनमें प्रत्येक जोड़े को जोड़ने वाला एक अनूठा प्रेरित पथ है।[1]
संबंधित ग्राफ वर्ग
ब्लॉक ग्राफ़ कॉर्डल ग्राफ़, दूरी-वंशानुगत ग्राफ़|दूरी-वंशानुगत ग्राफ़ और जियोडेटिक ग्राफ हैं। दूरी-वंशानुगत ग्राफ़ वे ग्राफ़ होते हैं जिनमें समान दो शीर्षों के बीच प्रत्येक दो प्रेरित पथों की लंबाई समान होती है, प्रत्येक दो शीर्षों के बीच अधिकतम एक प्रेरित पथ होने के रूप में ब्लॉक ग्राफ़ के लक्षण वर्णन का कमजोर होना। चूँकि कॉर्डल ग्राफ़ और दूरी-वंशानुगत ग्राफ़ दोनों ही पूर्ण ग्राफ़ के उपवर्ग हैं, ब्लॉक ग्राफ़ परिपूर्ण हैं।
हर ट्री (ग्राफ थ्योरी), क्लस्टर ग्राफ या पवनचक्की ग्राफ एक ब्लॉक ग्राफ है।
प्रत्येक ब्लॉक ग्राफ में अधिक से अधिक दो बॉक्सिंग होती है।[7]
ब्लॉक ग्राफ़ छद्म-माध्यिका ग्राफ के उदाहरण हैं: प्रत्येक तीन शीर्षों के लिए, या तो एक अद्वितीय शीर्ष सम्मिलित होता है जो तीनों शीर्षों के बीच सबसे छोटे पथ से संबंधित होता है, या एक अद्वितीय त्रिभुज सम्मिलित होता है जिसके किनारे इन तीन सबसे छोटे पथों पर स्थित होते हैं।[7]
ट्री के लाइन ग्राफ वास्तव में ब्लॉक ग्राफ़ हैं जिनमें प्रत्येक कट वर्टेक्स अधिकतम दो ब्लॉक, या समकक्ष पंजा मुक्त ग्राफ क्लॉ-फ़्री ब्लॉक ग्राफ़ों की घटना होती है। ट्री के लाइन ग्राफ़ का उपयोग किनारों और शीर्षों की दी गई संख्या वाले ग्राफ़ को खोजने के लिए किया गया है जिसमें सबसे बड़ा प्रेरित सबग्राफ जो कि एक ट्री है, जितना संभव हो उतना छोटा है।[8]
ब्लॉक ग्राफ़ जिसमें प्रत्येक ब्लॉक का आकार अधिकतम तीन होता है, एक विशेष प्रकार का कैक्टस ग्राफ़, एक त्रिकोणीय कैक्टस होता है। किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ होता हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का सन्निकटन अनुपात 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।[9]
अप्रत्यक्ष रेखांकन के ब्लॉक रेखांकन
यदि G कोई अप्रत्यक्ष ग्राफ है, तो G का ब्लॉक ग्राफ,B(G) को दर्शाता है, G के ब्लॉकों का प्रतिच्छेदन ग्राफ है: B (G) में G के प्रत्येक द्विसंबद्ध घटक के लिए एक शीर्ष है, और B (G) के दो कोने) आसन्न हैं यदि संबंधित दो ब्लॉक एक आर्टिक्यूलेशन वर्टेक्स पर मिलते हैं। अगर K1 एक शीर्ष के साथ ग्राफ को दर्शाता है, तो B(K1) को रिक्त ग्राफ ग्राफ के रूप में परिभाषित किया गया है। B (G) आवश्यक रूप से एक ब्लॉक ग्राफ है: इसमें G के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक बायकनेक्टेड घटक है, और इस तरह से गठित प्रत्येक बाइकनेक्टेड घटक एक क्लिक होना चाहिए। इसके विपरीत, प्रत्येक ब्लॉक ग्राफ किसी ग्राफ G के लिए ग्राफ B(G) होता है ।[4] अगर G एक ट्री है, तो B(G) G के लाइन ग्राफ के साथ मेल खाता है।
ग्राफ B (B (G)) में G के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने B(B(G)) में आसन्न हैं यदि वे G में एक ही ब्लॉक से संबंधित हैं।[4]
संदर्भ
- ↑ 1.0 1.1 Vušković, Kristina (2010), "Even-hole-free graphs: A survey" (PDF), Applicable Analysis and Discrete Mathematics, 4 (2): 219–240, doi:10.2298/AADM100812027V.
- ↑ 2.0 2.1 2.2 2.3 Howorka, Edward (1979), "On metric properties of certain clique graphs", Journal of Combinatorial Theory, Series B, 27 (1): 67–74, doi:10.1016/0095-8956(79)90069-8.
- ↑ See, e.g., MR0659742, a 1983 review by Robert E. Jamison of another paper referring to block graphs as Husimi trees; Jamison attributes the mistake to an error in a book by Mehdi Behzad and Gary Chartrand.
- ↑ 4.0 4.1 4.2 Harary, Frank (1963), "A characterization of block-graphs", Canadian Mathematical Bulletin, 6 (1): 1–6, doi:10.4153/cmb-1963-001-x, hdl:10338.dmlcz/101399.
- ↑ 5.0 5.1 Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2.
- ↑ Edelman, Paul H.; Jamison, Robert E. (1985), "The theory of convex geometries", Geometriae Dedicata, 19 (3): 247–270, doi:10.1007/BF00149365, S2CID 123491343.
- ↑ 7.0 7.1 Block graphs, Information System on Graph Class Inclusions.
- ↑ Erdős, Paul; Saks, Michael; Sós, Vera T. (1986), "Maximum induced trees in graphs" (PDF), Journal of Combinatorial Theory, Series B, 41 (1): 61–79, doi:10.1016/0095-8956(86)90028-6.
- ↑ Călinescu, Gruia; Fernandes, Cristina G.; Finkler, Ulrich; Karloff, Howard (2002), "A Better Approximation Algorithm for Finding Planar Subgraphs", Journal of Algorithms, 2, 27 (2): 269–302, doi:10.1006/jagm.1997.0920, S2CID 8329680
