ब्लॉक ग्राफ: Difference between revisions
(modification) |
|||
| Line 25: | Line 25: | ||
| hdl-access = free | | hdl-access = free | ||
}}.</ref> | }}.</ref> | ||
== लक्षण वर्णन == | == लक्षण वर्णन == | ||
ब्लॉक ग्राफ़ वास्तव में वे ग्राफ़ हैं जिनके लिए, प्रत्येक चार शीर्षों के लिए {{mvar|u}}, {{mvar|v}}, {{mvar|x}}, और {{mvar|y}}, तीन दूरियों में से सबसे बड़ी दो {{math|''d''(''u'',''v'') + ''d''(''x'',''y'')}}, | ब्लॉक ग्राफ़ वास्तव में वे ग्राफ़ हैं जिनके लिए, प्रत्येक चार शीर्षों के लिए {{mvar|u}}, {{mvar|v}}, {{mvar|x}}, और {{mvar|y}}, तीन दूरियों में से सबसे बड़ी दो {{math|''d''(''u'',''v'') + ''d''(''x'',''y'')}}, | ||
| Line 54: | Line 51: | ||
उनके पास ग्राफ़ के रूप में एक वर्जित ग्राफ़ लक्षण वर्णन भी है जिसमें हीरे का ग्राफ़ या एक [[प्रेरित सबग्राफ]] के रूप में चार या अधिक वर्टिकल का चक्र नहीं है; अर्थात्, वे हीरा-मुक्त कॉर्डल ग्राफ़ हैं।<ref name="bm86" />वे [[टॉलेमिक ग्राफ]] भी हैं ([[कॉर्डल ग्राफ|कॉर्डल डिस्टेंस-हेरेडिटरी ग्राफ]], [[दूरी-वंशानुगत ग्राफ]]) जिसमें प्रत्येक दो नोड्स एक दूसरे से दो दूरी पर एक अद्वितीय सबसे छोटे पथ से जुड़े होते हैं,<ref name="h79" />और कॉर्डल ग्राफ़ जिसमें प्रत्येक दो अधिकतम समूहों में अधिक से अधिक एक शीर्ष उभयनिष्ठ होता है।<ref name="h79" /> | उनके पास ग्राफ़ के रूप में एक वर्जित ग्राफ़ लक्षण वर्णन भी है जिसमें हीरे का ग्राफ़ या एक [[प्रेरित सबग्राफ]] के रूप में चार या अधिक वर्टिकल का चक्र नहीं है; अर्थात्, वे हीरा-मुक्त कॉर्डल ग्राफ़ हैं।<ref name="bm86" />वे [[टॉलेमिक ग्राफ]] भी हैं ([[कॉर्डल ग्राफ|कॉर्डल डिस्टेंस-हेरेडिटरी ग्राफ]], [[दूरी-वंशानुगत ग्राफ]]) जिसमें प्रत्येक दो नोड्स एक दूसरे से दो दूरी पर एक अद्वितीय सबसे छोटे पथ से जुड़े होते हैं,<ref name="h79" />और कॉर्डल ग्राफ़ जिसमें प्रत्येक दो अधिकतम समूहों में अधिक से अधिक एक शीर्ष उभयनिष्ठ होता है।<ref name="h79" /> | ||
एक ग्राफ {{mvar| | एक ग्राफ {{mvar|G}} एक ब्लॉक ग्राफ है [[अगर और केवल अगर]] हर दो [[ कनेक्टिविटी (ग्राफ सिद्धांत) | कनेक्टिविटी (ग्राफ सिद्धांत)]] का प्रतिच्छेदन सबसेट का सबसेट है ''G'' खाली है या जुड़ा हुआ है। इसलिए, कनेक्टेड ब्लॉक ग्राफ़ में वर्टिकल के जुड़े सबसेट एक [[Index.php?title=एंटिमेट्र|एंटिमेट्र]] बनाते हैं, एक ऐसी संपत्ति जो किसी भी ग्राफ़ के लिए सही नहीं है जो ब्लॉक ग्राफ़ नहीं हैं।<ref>{{citation | ||
| last1 = Edelman | first1 = Paul H. | | last1 = Edelman | first1 = Paul H. | ||
| last2 = Jamison | first2 = Robert E. | | last2 = Jamison | first2 = Robert E. | ||
| Line 66: | Line 63: | ||
}}.</ref> इस संपत्ति के कारण, कनेक्टेड ब्लॉक ग्राफ़ में, कोने के प्रत्येक सेट में एक अद्वितीय न्यूनतम कनेक्टेड सुपरसेट होता है, जो उत्तल ज्यामिति में बंद होता है। कनेक्टेड ब्लॉक ग्राफ़ बिल्कुल ऐसे ग्राफ़ हैं जिनमें प्रत्येक जोड़े को जोड़ने वाला एक अनूठा [[प्रेरित पथ]] है।<ref name="v10" /> | }}.</ref> इस संपत्ति के कारण, कनेक्टेड ब्लॉक ग्राफ़ में, कोने के प्रत्येक सेट में एक अद्वितीय न्यूनतम कनेक्टेड सुपरसेट होता है, जो उत्तल ज्यामिति में बंद होता है। कनेक्टेड ब्लॉक ग्राफ़ बिल्कुल ऐसे ग्राफ़ हैं जिनमें प्रत्येक जोड़े को जोड़ने वाला एक अनूठा [[प्रेरित पथ]] है।<ref name="v10" /> | ||
== संबंधित ग्राफ वर्ग == | |||
ब्लॉक ग्राफ़ कॉर्डल ग्राफ़, दूरी-वंशानुगत ग्राफ़|दूरी-वंशानुगत ग्राफ़ और [[जियोडेटिक ग्राफ]] हैं। दूरी-वंशानुगत ग्राफ़ वे ग्राफ़ होते हैं जिनमें समान दो शीर्षों के बीच प्रत्येक दो प्रेरित पथों की लंबाई समान होती है, प्रत्येक दो शीर्षों के बीच अधिकतम एक प्रेरित पथ होने के रूप में ब्लॉक ग्राफ़ के लक्षण वर्णन का कमजोर होना। चूँकि कॉर्डल ग्राफ़ और दूरी-वंशानुगत ग्राफ़ दोनों ही पूर्ण ग्राफ़ के उपवर्ग हैं, ब्लॉक ग्राफ़ परिपूर्ण हैं। | ब्लॉक ग्राफ़ कॉर्डल ग्राफ़, दूरी-वंशानुगत ग्राफ़|दूरी-वंशानुगत ग्राफ़ और [[जियोडेटिक ग्राफ]] हैं। दूरी-वंशानुगत ग्राफ़ वे ग्राफ़ होते हैं जिनमें समान दो शीर्षों के बीच प्रत्येक दो प्रेरित पथों की लंबाई समान होती है, प्रत्येक दो शीर्षों के बीच अधिकतम एक प्रेरित पथ होने के रूप में ब्लॉक ग्राफ़ के लक्षण वर्णन का कमजोर होना। चूँकि कॉर्डल ग्राफ़ और दूरी-वंशानुगत ग्राफ़ दोनों ही पूर्ण ग्राफ़ के उपवर्ग हैं, ब्लॉक ग्राफ़ परिपूर्ण हैं। | ||
हर | हर ट्री (ग्राफ थ्योरी), [[क्लस्टर ग्राफ]] या [[ पवनचक्की ग्राफ ]] एक ब्लॉक ग्राफ है। | ||
प्रत्येक ब्लॉक ग्राफ में अधिक से अधिक दो बॉक्सिंग होती है।<ref name="isgci">[http://www.graphclasses.org/classes/gc_93.html Block graphs], Information System on Graph Class Inclusions.</ref> | प्रत्येक ब्लॉक ग्राफ में अधिक से अधिक दो बॉक्सिंग होती है।<ref name="isgci">[http://www.graphclasses.org/classes/gc_93.html Block graphs], Information System on Graph Class Inclusions.</ref> | ||
ब्लॉक ग्राफ़ छद्म-[[माध्यिका ग्राफ]] के उदाहरण हैं: प्रत्येक तीन शीर्षों के लिए, या तो एक अद्वितीय शीर्ष मौजूद होता है जो तीनों शीर्षों के बीच सबसे छोटे पथ से संबंधित होता है, या एक अद्वितीय त्रिभुज मौजूद होता है जिसके किनारे इन तीन सबसे छोटे पथों पर स्थित होते हैं।<ref name="isgci" /> | |||
ट्री के [[लाइन ग्राफ]] वास्तव में ब्लॉक ग्राफ़ हैं जिनमें प्रत्येक कट वर्टेक्स अधिकतम दो ब्लॉक, या समकक्ष [[पंजा मुक्त ग्राफ]] क्लॉ-फ़्री ब्लॉक ग्राफ़ों की घटना होती है। पेड़ों के लाइन ग्राफ़ का उपयोग किनारों और शीर्षों की दी गई संख्या वाले ग्राफ़ को खोजने के लिए किया गया है जिसमें सबसे बड़ा प्रेरित सबग्राफ जो कि एक पेड़ है, जितना संभव हो उतना छोटा है।<ref>{{citation | |||
| last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős | ||
| last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician) | | last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician) | ||
| Line 106: | Line 102: | ||
ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने बी(बी(जी)) में आसन्न हैं यदि वे जी में एक ही ब्लॉक से संबंधित हैं।<ref name="h63" /> | ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने बी(बी(जी)) में आसन्न हैं यदि वे जी में एक ही ब्लॉक से संबंधित हैं।<ref name="h63" /> | ||
संदर्भ{{reflist}} | संदर्भ{{reflist}} | ||
Revision as of 15:46, 17 March 2023
ग्राफ सिद्धांत में, कॉम्बिनेटरियल गणित की एक शाखा, एक ब्लॉक ग्राफ या क्लिक ट्री[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]
यदि जी कोई अप्रत्यक्ष ग्राफ है, तो जी का ब्लॉक ग्राफ, बी (जी) को दर्शाता है, जी के ब्लॉकों का प्रतिच्छेदन ग्राफ है: बी (जी) में जी के प्रत्येक द्विसंबद्ध घटक के लिए एक शीर्ष है, और बी (जी) के दो कोने ) आसन्न हैं यदि संबंधित दो ब्लॉक एक आर्टिक्यूलेशन वर्टेक्स पर मिलते हैं। अगर के1 एक शीर्ष के साथ ग्राफ को दर्शाता है, तो बी(के1) को खाली ग्राफ ग्राफ के रूप में परिभाषित किया गया है। बी (जी) आवश्यक रूप से एक ब्लॉक ग्राफ है: इसमें जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक बायकनेक्टेड घटक है, और इस तरह से गठित प्रत्येक बाइकनेक्टेड घटक एक क्लिक होना चाहिए। इसके विपरीत, प्रत्येक ब्लॉक ग्राफ किसी ग्राफ जी के लिए ग्राफ B(जी) होता है ।[4] अगर जी एक पेड़ है, तो बी (जी) जी के लाइन ग्राफ के साथ मेल खाता है।
ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने बी(बी(जी)) में आसन्न हैं यदि वे जी में एक ही ब्लॉक से संबंधित हैं।[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
