ब्लॉक ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Graph whose biconnected components are all cliques}} {{distinguish|text=block diagram or bar chart}} File:Block graph.svg|thumb|240px|एक ब...")
 
(modification)
Line 1: Line 1:
{{Short description|Graph whose biconnected components are all cliques}}
{{Short description|Graph whose biconnected components are all cliques}}
{{distinguish|text=[[block diagram]] or [[bar chart]]}}
{{distinguish|text=[[block diagram]] or [[bar chart]]}}
[[File:Block graph.svg|thumb|240px|एक ब्लॉक ग्राफ]][[ ग्राफ सिद्धांत ]] में, कॉम्बिनेटरियल गणित की एक शाखा, एक ब्लॉक ग्राफ या क्लिक ट्री<ref name="v10">{{citation
[[File:Block graph.svg|thumb|240px|एक ब्लॉक ग्राफ]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, कॉम्बिनेटरियल गणित की एक शाखा, एक ब्लॉक ग्राफ या क्लिक ट्री<ref name="v10">{{citation
  | last = Vušković | first = Kristina | author-link = Kristina Vušković
  | last = Vušković | first = Kristina | author-link = Kristina Vušković
  | doi = 10.2298/AADM100812027V
  | doi = 10.2298/AADM100812027V
Line 13: Line 13:


ब्लॉक ग्राफ़ को कभी-कभी ग़लती से हुसिमी पेड़ कहा जाता है (कोडी हुसिमी के बाद),<ref name="h79"/>लेकिन यह नाम [[कैक्टस ग्राफ]]़ को अधिक ठीक से संदर्भित करता है, ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है।<ref>See, e.g., {{MR|0659742}}, 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]].</ref>
ब्लॉक ग्राफ़ को कभी-कभी ग़लती से हुसिमी पेड़ कहा जाता है (कोडी हुसिमी के बाद),<ref name="h79"/>लेकिन यह नाम [[कैक्टस ग्राफ]]़ को अधिक ठीक से संदर्भित करता है, ग्राफ़ जिसमें प्रत्येक गैर-तुच्छ द्विसंबद्ध घटक एक चक्र है।<ref>See, e.g., {{MR|0659742}}, 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]].</ref>
ब्लॉक ग्राफ़ को मनमाने ढंग से अप्रत्यक्ष ग्राफ़ के ब्लॉक के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है।<ref name="h63">{{citation
ब्लॉक ग्राफ़ को मनमाने ढंग से अप्रत्यक्ष ग्राफ़ के ब्लॉक के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है।<ref name="h63">{{citation
  | last = Harary | first = Frank | author-link = Frank Harary
  | last = Harary | first = Frank | author-link = Frank Harary
Line 24: Line 25:
  | hdl-access = free
  | hdl-access = free
  }}.</ref>
  }}.</ref>




Line 49: Line 51:
  | year = 1986| doi-access = free
  | year = 1986| doi-access = free
  }}.</ref>
  }}.</ref>
उनके पास ग्राफ़ के रूप में एक वर्जित ग्राफ़ लक्षण वर्णन भी है जिसमें हीरे का ग्राफ़ या एक [[प्रेरित सबग्राफ]] के रूप में चार या अधिक वर्टिकल का चक्र नहीं है; अर्थात्, वे हीरा-मुक्त कॉर्डल ग्राफ़ हैं।<ref name="bm86"/>वे [[टॉलेमिक ग्राफ]]़ भी हैं ([[कॉर्डल ग्राफ]]़ [[दूरी-वंशानुगत ग्राफ]]़) जिसमें प्रत्येक दो नोड्स एक दूसरे से दो दूरी पर एक अद्वितीय सबसे छोटे पथ से जुड़े होते हैं,<ref name="h79"/>और कॉर्डल ग्राफ़ जिसमें प्रत्येक दो अधिकतम समूहों में अधिक से अधिक एक शीर्ष उभयनिष्ठ होता है।<ref name="h79"/>


एक ग्राफ {{mvar|G}} एक ब्लॉक ग्राफ है [[अगर और केवल अगर]] हर दो [[ कनेक्टिविटी (ग्राफ सिद्धांत) ]] का प्रतिच्छेदन सबसेट का सबसेट है {{mvar|G}} खाली है या जुड़ा हुआ है। इसलिए, कनेक्टेड ब्लॉक ग्राफ़ में वर्टिकल के जुड़े सबसेट एक [[antimatroid]] बनाते हैं, एक ऐसी संपत्ति जो किसी भी ग्राफ़ के लिए सही नहीं है जो ब्लॉक ग्राफ़ नहीं हैं।<ref>{{citation
उनके पास ग्राफ़ के रूप में एक वर्जित ग्राफ़ लक्षण वर्णन भी है जिसमें हीरे का ग्राफ़ या एक [[प्रेरित सबग्राफ]] के रूप में चार या अधिक वर्टिकल का चक्र नहीं है; अर्थात्, वे हीरा-मुक्त कॉर्डल ग्राफ़ हैं।<ref name="bm86" />वे [[टॉलेमिक ग्राफ]] भी हैं ([[कॉर्डल ग्राफ|कॉर्डल डिस्टेंस-हेरेडिटरी ग्राफ]], [[दूरी-वंशानुगत ग्राफ]]) जिसमें प्रत्येक दो नोड्स एक दूसरे से दो दूरी पर एक अद्वितीय सबसे छोटे पथ से जुड़े होते हैं,<ref name="h79" />और कॉर्डल ग्राफ़ जिसमें प्रत्येक दो अधिकतम समूहों में अधिक से अधिक एक शीर्ष उभयनिष्ठ होता है।<ref name="h79" />
 
एक ग्राफ {{mvar|जी}} एक ब्लॉक ग्राफ है [[अगर और केवल अगर]] हर दो [[ कनेक्टिविटी (ग्राफ सिद्धांत) | कनेक्टिविटी (ग्राफ सिद्धांत)]] का प्रतिच्छेदन सबसेट का सबसेट है {{mvar|जी}} खाली है या जुड़ा हुआ है। इसलिए, कनेक्टेड ब्लॉक ग्राफ़ में वर्टिकल के जुड़े सबसेट एक [[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 61: Line 64:
  | volume = 19
  | volume = 19
  | year = 1985| s2cid = 123491343
  | year = 1985| s2cid = 123491343
  }}.</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 name="isgci"/>


पेड़ों के [[लाइन ग्राफ]]़ वास्तव में ब्लॉक ग्राफ़ हैं जिनमें प्रत्येक कट वर्टेक्स अधिकतम दो ब्लॉक, या समकक्ष [[पंजा मुक्त ग्राफ]] | क्लॉ-फ़्री ब्लॉक ग्राफ़ पर घटना है। पेड़ों के लाइन ग्राफ़ का उपयोग दिए गए किनारों और शिखरों के साथ ग्राफ़ खोजने के लिए किया गया है जिसमें सबसे बड़ा प्रेरित सबग्राफ जो कि एक पेड़ है, जितना संभव हो उतना छोटा है।<ref>{{citation
पेड़ों के [[लाइन ग्राफ]] वास्तव में ब्लॉक ग्राफ़ हैं जिनमें प्रत्येक कट वर्टेक्स अधिकतम दो ब्लॉक, या समकक्ष [[पंजा मुक्त ग्राफ]] | क्लॉ-फ़्री ब्लॉक ग्राफ़ों की घटना होती है। पेड़ों के लाइन ग्राफ़ का उपयोग किनारों और शीर्षों की दी गई संख्या वाले ग्राफ़ को खोजने के लिए किया गया है जिसमें सबसे बड़ा प्रेरित सबग्राफ जो कि एक पेड़ है, जितना संभव हो उतना छोटा है।<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 83: Line 87:
  | volume = 41
  | volume = 41
  | year = 1986| url = http://real.mtak.hu/110576/1/1-s2.0-0095895686900286-main.pdf }}.</ref>
  | year = 1986| url = http://real.mtak.hu/110576/1/1-s2.0-0095895686900286-main.pdf }}.</ref>
ब्लॉक ग्राफ़ जिसमें प्रत्येक ब्लॉक का आकार अधिकतम तीन होता है, एक विशेष प्रकार का कैक्टस ग्राफ़, एक त्रिकोणीय कैक्टस होता है। किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ [[प्लेनर ग्राफ]]़ हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का [[सन्निकटन अनुपात]] 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।<ref>{{citation
 
ब्लॉक ग्राफ़ जिसमें प्रत्येक ब्लॉक का आकार अधिकतम तीन होता है, एक विशेष प्रकार का कैक्टस ग्राफ़, एक त्रिकोणीय कैक्टस होता है। किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय [[प्लेनर ग्राफ|कैक्टस ग्राफ़ होता]] हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का [[सन्निकटन अनुपात]] 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।<ref>{{citation
  | last1 = Călinescu | first1 = Gruia
  | last1 = Călinescu | first1 = Gruia
  | last2 = Fernandes | first2 = Cristina G. | author2-link = Cristina G. Fernandes
  | last2 = Fernandes | first2 = Cristina G. | author2-link = Cristina G. Fernandes
Line 98: Line 103:
  }}</ref>
  }}</ref>


यदि जी कोई अप्रत्यक्ष ग्राफ है, तो जी का ब्लॉक ग्राफ, बी (जी) को दर्शाता है, जी के ब्लॉकों का प्रतिच्छेदन ग्राफ है: बी (जी) में जी के प्रत्येक द्विसंबद्ध घटक के लिए एक शीर्ष है, और बी (जी) के दो कोने ) आसन्न हैं यदि संबंधित दो ब्लॉक एक आर्टिक्यूलेशन वर्टेक्स पर मिलते हैं। अगर के1 एक शीर्ष के साथ ग्राफ को दर्शाता है, तो बी(के1) को [[खाली ग्राफ]] ग्राफ के रूप में परिभाषित किया गया है। बी (जी) आवश्यक रूप से एक ब्लॉक ग्राफ है: इसमें जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक बायकनेक्टेड घटक है, और इस तरह से गठित प्रत्येक बाइकनेक्टेड घटक एक क्लिक होना चाहिए। इसके विपरीत, प्रत्येक ब्लॉक ग्राफ किसी ग्राफ जी के लिए ग्राफ B(जी) होता है ।<ref name="h63" /> अगर जी एक पेड़ है, तो बी (जी) जी के लाइन ग्राफ के साथ मेल खाता है।


== अप्रत्यक्ष रेखांकन == के ब्लॉक रेखांकन
ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने बी(बी(जी)) में आसन्न हैं यदि वे जी में एक ही ब्लॉक से संबंधित हैं।<ref name="h63" />
यदि G कोई अप्रत्यक्ष ग्राफ़ है, तो G का ब्लॉक ग्राफ़, जिसे B(G) के रूप में दर्शाया गया है, G के ब्लॉक का प्रतिच्छेदन ग्राफ़ है: B(G) में G के प्रत्येक द्विसंबद्ध घटक के लिए एक शीर्ष है, और B(G) के दो शीर्ष हैं ) आसन्न हैं यदि संबंधित दो ब्लॉक एक आर्टिक्यूलेशन वर्टेक्स पर मिलते हैं। यदि के<sub>1</sub> ग्राफ को एक शीर्ष के साथ दर्शाता है, फिर B(K<sub>1</sub>) को [[खाली ग्राफ]] के रूप में परिभाषित किया गया है। बी (जी) आवश्यक रूप से एक ब्लॉक ग्राफ है: इसमें जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक बायकनेक्टेड घटक है, और इस तरह से गठित प्रत्येक बाइकनेक्टेड घटक एक क्लिक होना चाहिए। इसके विपरीत, प्रत्येक ब्लॉक ग्राफ कुछ ग्राफ जी के लिए ग्राफ बी (जी) है।<ref name="h63"/>अगर जी एक पेड़ है, तो बी (जी) जी के लाइन ग्राफ के साथ मेल खाता है।
 
ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो शीर्ष B(B(G)) में आसन्न हैं यदि वे G में एक ही ब्लॉक से संबंधित हैं।<ref name="h63"/>




==संदर्भ==
संदर्भ{{reflist}}
{{reflist}}
[[Category: ग्राफ परिवार]] [[Category: रेखांकन के चौराहे वर्ग]] [[Category: बिल्कुल सही रेखांकन]] [[Category: पेड़ (ग्राफ सिद्धांत)]]  
[[Category: ग्राफ परिवार]] [[Category: रेखांकन के चौराहे वर्ग]] [[Category: बिल्कुल सही रेखांकन]] [[Category: पेड़ (ग्राफ सिद्धांत)]]  


Revision as of 16:52, 14 March 2023

Not to be confused with block diagram or bar chart.
एक ब्लॉक ग्राफ

ग्राफ सिद्धांत में, कॉम्बिनेटरियल गणित की एक शाखा, एक ब्लॉक ग्राफ या क्लिक ट्री[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]

एक ग्राफ जी एक ब्लॉक ग्राफ है अगर और केवल अगर हर दो कनेक्टिविटी (ग्राफ सिद्धांत) का प्रतिच्छेदन सबसेट का सबसेट है जी खाली है या जुड़ा हुआ है। इसलिए, कनेक्टेड ब्लॉक ग्राफ़ में वर्टिकल के जुड़े सबसेट एक एंटिमेट्र बनाते हैं, एक ऐसी संपत्ति जो किसी भी ग्राफ़ के लिए सही नहीं है जो ब्लॉक ग्राफ़ नहीं हैं।[6] इस संपत्ति के कारण, कनेक्टेड ब्लॉक ग्राफ़ में, कोने के प्रत्येक सेट में एक अद्वितीय न्यूनतम कनेक्टेड सुपरसेट होता है, जो उत्तल ज्यामिति में बंद होता है। कनेक्टेड ब्लॉक ग्राफ़ बिल्कुल ऐसे ग्राफ़ हैं जिनमें प्रत्येक जोड़े को जोड़ने वाला एक अनूठा प्रेरित पथ है।[1]


संबंधित ग्राफ वर्ग

ब्लॉक ग्राफ़ कॉर्डल ग्राफ़, दूरी-वंशानुगत ग्राफ़|दूरी-वंशानुगत ग्राफ़ और जियोडेटिक ग्राफ हैं। दूरी-वंशानुगत ग्राफ़ वे ग्राफ़ होते हैं जिनमें समान दो शीर्षों के बीच प्रत्येक दो प्रेरित पथों की लंबाई समान होती है, प्रत्येक दो शीर्षों के बीच अधिकतम एक प्रेरित पथ होने के रूप में ब्लॉक ग्राफ़ के लक्षण वर्णन का कमजोर होना। चूँकि कॉर्डल ग्राफ़ और दूरी-वंशानुगत ग्राफ़ दोनों ही पूर्ण ग्राफ़ के उपवर्ग हैं, ब्लॉक ग्राफ़ परिपूर्ण हैं।

हर पेड़ (ग्राफ थ्योरी), क्लस्टर ग्राफ या पवनचक्की ग्राफ एक ब्लॉक ग्राफ है।

प्रत्येक ब्लॉक ग्राफ में अधिक से अधिक दो बॉक्सिंग होती है।[7] ब्लॉक ग्राफ़ छद्म-माध्यिका ग्राफ के उदाहरण हैं: प्रत्येक तीन शीर्षों के लिए, या तो एक अद्वितीय शीर्ष मौजूद होता है जो तीनों शीर्षों के बीच सबसे छोटे पथ से संबंधित होता है, या एक अद्वितीय त्रिभुज मौजूद होता है जिसके किनारे इन तीन सबसे छोटे पथों पर स्थित होते हैं।[7]

पेड़ों के लाइन ग्राफ वास्तव में ब्लॉक ग्राफ़ हैं जिनमें प्रत्येक कट वर्टेक्स अधिकतम दो ब्लॉक, या समकक्ष पंजा मुक्त ग्राफ | क्लॉ-फ़्री ब्लॉक ग्राफ़ों की घटना होती है। पेड़ों के लाइन ग्राफ़ का उपयोग किनारों और शीर्षों की दी गई संख्या वाले ग्राफ़ को खोजने के लिए किया गया है जिसमें सबसे बड़ा प्रेरित सबग्राफ जो कि एक पेड़ है, जितना संभव हो उतना छोटा है।[8]

ब्लॉक ग्राफ़ जिसमें प्रत्येक ब्लॉक का आकार अधिकतम तीन होता है, एक विशेष प्रकार का कैक्टस ग्राफ़, एक त्रिकोणीय कैक्टस होता है। किसी भी ग्राफ़ में सबसे बड़ा त्रिकोणीय कैक्टस बहुपद समता समस्या के लिए एक एल्गोरिथ्म का उपयोग करते हुए बहुपद समय में पाया जा सकता है। चूंकि त्रिकोणीय कैक्टस ग्राफ़ होता हैं, इसलिए सबसे बड़ा त्रिकोणीय कैक्टस का उपयोग सबसे बड़े प्लानर सबग्राफ के सन्निकटन के रूप में किया जा सकता है, जो कि प्लानरीकरण में एक महत्वपूर्ण उप-समस्या है। सन्निकटन एल्गोरिथम के रूप में, इस पद्धति का सन्निकटन अनुपात 4/9 है, जो अधिकतम प्लानर सबग्राफ समस्या के लिए सबसे अच्छी तरह से जाना जाता है।[9]

यदि जी कोई अप्रत्यक्ष ग्राफ है, तो जी का ब्लॉक ग्राफ, बी (जी) को दर्शाता है, जी के ब्लॉकों का प्रतिच्छेदन ग्राफ है: बी (जी) में जी के प्रत्येक द्विसंबद्ध घटक के लिए एक शीर्ष है, और बी (जी) के दो कोने ) आसन्न हैं यदि संबंधित दो ब्लॉक एक आर्टिक्यूलेशन वर्टेक्स पर मिलते हैं। अगर के1 एक शीर्ष के साथ ग्राफ को दर्शाता है, तो बी(के1) को खाली ग्राफ ग्राफ के रूप में परिभाषित किया गया है। बी (जी) आवश्यक रूप से एक ब्लॉक ग्राफ है: इसमें जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक बायकनेक्टेड घटक है, और इस तरह से गठित प्रत्येक बाइकनेक्टेड घटक एक क्लिक होना चाहिए। इसके विपरीत, प्रत्येक ब्लॉक ग्राफ किसी ग्राफ जी के लिए ग्राफ B(जी) होता है ।[4] अगर जी एक पेड़ है, तो बी (जी) जी के लाइन ग्राफ के साथ मेल खाता है।

ग्राफ बी (बी (जी)) में जी के प्रत्येक आर्टिक्यूलेशन वर्टेक्स के लिए एक वर्टेक्स है; दो कोने बी(बी(जी)) में आसन्न हैं यदि वे जी में एक ही ब्लॉक से संबंधित हैं।[4]


संदर्भ

  1. ↑ 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. ↑ 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.
  3. ↑ 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. ↑ 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. ↑ 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.
  6. ↑ 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. ↑ 7.0 7.1 Block graphs, Information System on Graph Class Inclusions.
  8. ↑ 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.
  9. ↑ 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ब्लॉक_ग्राफ&oldid=114504’