प्रतिच्छेदन ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Graph representing intersections between given sets}} Image:Intersection graph.gif|thumb|इंटरसेक्टिंग सेट कैसे ए...")
 
No edit summary
 
(10 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{short description|Graph representing intersections between given sets}}
{{short description|Graph representing intersections between given sets}}
[[Image:Intersection graph.gif|thumb|इंटरसेक्टिंग सेट कैसे एक ग्राफ को परिभाषित करता है इसका एक उदाहरण।]][[ग्राफ सिद्धांत]] में, एक चौराहे का ग्राफ एक [[ग्राफ (असतत गणित)]] है जो [[सेट (गणित)]] के एक परिवार के प्रतिच्छेदन (सेट सिद्धांत) के पैटर्न का प्रतिनिधित्व करता है। किसी भी ग्राफ़ को एक प्रतिच्छेदन ग्राफ़ के रूप में दर्शाया जा सकता है, लेकिन ग्राफ़ के कुछ महत्वपूर्ण विशेष वर्गों को उन सेटों के प्रकारों द्वारा परिभाषित किया जा सकता है, जिनका उपयोग उनका एक प्रतिच्छेदन प्रतिनिधित्व करने के लिए किया जाता है।
[[Image:Intersection graph.gif|thumb|इंटरसेक्टिंग समुच्चय कैसे ग्राफ को परिभाषित करता है इसका उदाहरण।]][[ग्राफ सिद्धांत]] में, प्रतिच्छेदन ग्राफ एक [[ग्राफ (असतत गणित)|ग्राफ]] है जो समुच्चय के समूह के प्रतिच्छेदन के पैटर्न का प्रतिनिधित्व करता है। किसी भी ग्राफ़ को प्रतिच्छेदन ग्राफ़ के रूप में दर्शाया जा सकता है, किन्तु ग्राफ़ के कुछ महत्वपूर्ण विशेष वर्गों को उन समुच्चयों के प्रकारों द्वारा परिभाषित किया जा सकता है, जिनका उपयोग उनका प्रतिच्छेदन प्रतिनिधित्व करने के लिए किया जाता है।


== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==
औपचारिक रूप से, एक चौराहा ग्राफ {{mvar|G}} सेट के परिवार से बना एक [[अप्रत्यक्ष ग्राफ]] है
औपचारिक रूप से, प्रतिच्छेदन ग्राफ {{mvar|G}} समुच्चय के समूह से बना [[अप्रत्यक्ष ग्राफ]] है,
: <math>S_i, \,\,\, i = 0, 1, 2, \dots</math>
: <math>S_i, \,\,\, i = 0, 1, 2, \dots</math>
एक शीर्ष बनाकर {{mvar|v{{sub|i}}}} प्रत्येक सेट के लिए {{mvar|S{{sub|i}}}}, और दो शीर्षों को जोड़ना {{mvar|v{{sub|i}}}} और {{mvar|v{{sub|j}}}} एक किनारे से जब भी संबंधित दो सेटों में एक [[खाली सेट]] चौराहा होता है, अर्थात
प्रत्येक समुच्चय {{mvar|S{{sub|i}}}} के लिए शीर्ष {{mvar|v{{sub|i}}}} बनाकर , और दो शीर्षों {{mvar|v{{sub|i}}}} और {{mvar|v{{sub|j}}}} को एक किनारे से जोड़कर जब भी संगत दो समुच्चयों में [[खाली सेट|गैर-रिक्त प्रतिच्छेदन]] होता है, अर्थात
: <math>E(G) = \{ \{ v_i, v_j \} \mid i \neq j, S_i \cap S_j \neq \empty \}.</math>
: <math>E(G) = \{ \{ v_i, v_j \} \mid i \neq j, S_i \cap S_j \neq \empty \}.</math>
== सभी रेखांकन प्रतिच्छेदन रेखांकन हैं ==
== सभी रेखांकन प्रतिच्छेदन रेखांकन हैं ==


कोई भी अप्रत्यक्ष ग्राफ {{mvar|G}} को प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है। प्रत्येक शीर्ष के लिए {{mvar|v<sub>i</sub>}} का {{mvar|G}}, एक सेट बनाएं {{mvar|S<sub>i</sub>}} किनारों की घटना से मिलकर {{mvar|v<sub>i</sub>}}; तो दो ऐसे सेटों में एक गैर-रिक्त चौराहा होता है यदि और केवल यदि संबंधित कोने किनारे साझा करते हैं। इसलिए, {{mvar|G}} समुच्चयों का प्रतिच्छेदन ग्राफ है {{mvar|S<sub>i</sub>}}.
कोई भी अप्रत्यक्ष ग्राफ {{mvar|G}} को प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है। {{mvar|G}} के प्रत्येक शीर्ष {{mvar|v<sub>i</sub>}} के लिए , समुच्चय {{mvar|S<sub>i</sub>}} बनाएं जिसमें किनारे {{mvar|v<sub>i</sub>}} से जुड़े हों; तो दो ऐसे समुच्चयों में गैर-रिक्त प्रतिच्छेदन होता है यदि और केवल यदि संबंधित कोने किनारे साझा करते हैं। इसलिए, {{mvar|G}} समुच्चय {{mvar|S<sub>i</sub>}} का प्रतिच्छेदन ग्राफ है।


{{harvtxt|Erdős|Goodman|Pósa|1966}} एक ऐसा निर्माण प्रदान करें जो अधिक कुशल हो, इस अर्थ में कि इसके लिए सभी सेटों में कम संख्या में तत्वों की आवश्यकता होती है {{mvar|S<sub>i</sub>}} संयुक्त। इसके लिए, सेट तत्वों की कुल संख्या अधिक से अधिक होती है {{math|{{sfrac|''n''<sup>2</sup>|4}}}}, कहाँ {{mvar|n}} ग्राफ में शीर्षों की संख्या है। वे इस अवलोकन का श्रेय देते हैं कि सभी ग्राफ़ प्रतिच्छेदन ग्राफ़ हैं {{harvtxt|Szpilrajn-Marczewski|1945}}, लेकिन देखने के लिए भी कहते हैं {{harvtxt|Čulík|1964}}. एक ग्राफ का प्रतिच्छेदन संख्या (ग्राफ सिद्धांत) ग्राफ के किसी भी प्रतिच्छेदन प्रतिनिधित्व में तत्वों की न्यूनतम कुल संख्या है।
{{harvtxt|एर्डोस|गुडमैन|पोसा|1966}} एक ऐसा निर्माण प्रदान करते हैं जो अधिक कुशल है, इस अर्थ में कि इसके लिए सभी समुच्चय {{mvar|S<sub>i</sub>}} संयुक्त में तत्वों की छोटी संख्या की आवश्यकता होती है। इसके लिए, समुच्चय तत्वों की कुल संख्या अधिक से अधिक {{math|{{sfrac|''n''<sup>2</sup>|4}}}}, जहां {{mvar|n}} ग्राफ में शीर्षों की संख्या है। वे इस अवलोकन का श्रेय {{harvtxt|स्ज़पिलराजन-मार्क्ज़वेस्की|1945}} को देते हैं कि सभी ग्राफ़ प्रतिच्छेदन ग्राफ़ हैं , किन्तु {{harvtxt|कुलिक|1964}} इसे देखने के लिए भी कहते है। किसी ग्राफ़ का प्रतिच्छेदन संख्या ग्राफ़ के किसी भी प्रतिच्छेदन प्रतिनिधित्व में तत्वों की न्यूनतम कुल संख्या है।


== प्रतिच्छेदन रेखांकन की कक्षाएं ==
== प्रतिच्छेदन रेखांकन की कक्षाएं ==
कई महत्वपूर्ण ग्राफ़ परिवारों को अधिक प्रतिबंधित प्रकार के सेट परिवारों के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है, उदाहरण के लिए किसी प्रकार के ज्यामितीय विन्यास से प्राप्त सेट:
कई महत्वपूर्ण ग्राफ़ समूहों को अधिक प्रतिबंधित प्रकार के समुच्चय समूहों के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है, उदाहरण के लिए किसी प्रकार के ज्यामितीय विन्यास से प्राप्त समुच्चय :
* एक [[अंतराल ग्राफ]] को वास्तविक रेखा पर अंतरालों के प्रतिच्छेदन ग्राफ, या एक [[पथ ग्राफ]] के जुड़े हुए सबग्राफ के रूप में परिभाषित किया जाता है।
* [[अंतराल ग्राफ]] को वास्तविक रेखा पर अंतरालों के प्रतिच्छेदन ग्राफ या [[पथ ग्राफ]] के जुड़े हुए सबग्राफ के रूप में परिभाषित किया जाता है।
* एक [[उदासीनता ग्राफ]] को वास्तविक रेखा पर इकाई अंतरालों के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जा सकता है
* [[उदासीनता ग्राफ]] को वास्तविक रेखा पर इकाई अंतरालों के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जा सकता है।
* एक वृत्ताकार चाप ग्राफ को वृत्ताकार चाप के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है।
* वृत्ताकार चाप ग्राफ को वृत्ताकार चाप के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है।
* एक [[बहुभुज-वृत्त ग्राफ]]को एक वृत्त पर कोनों वाले बहुभुजों के प्रतिच्छेदन के रूप में परिभाषित किया जाता है।
* [[बहुभुज-वृत्त ग्राफ]] को वृत्त पर कोनों वाले बहुभुजों के प्रतिच्छेदन के रूप में परिभाषित किया जाता है।
* [[कॉर्डल ग्राफ]] का एक लक्षण एक पेड़ (ग्राफ थ्योरी) के जुड़े सबग्राफ के इंटरसेक्शन ग्राफ के रूप में है।
* [[कॉर्डल ग्राफ]] का लक्षण ट्री के जुड़े सबग्राफ के प्रतिच्छेदन ग्राफ़ के रूप में है।
* समलम्बाकार ग्राफ को दो समांतर रेखाओं से बने समलम्बाकार के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है। वे क्रमचय ग्राफ की धारणा का एक सामान्यीकरण हैं, बदले में वे तुलनात्मकता ग्राफ के पूरक के परिवार का एक विशेष मामला हैं, जिसे सह-तुलनीयता ग्राफ के रूप में जाना जाता है।
* समलम्बाकार ग्राफ को दो समांतर रेखाओं से बने समलम्बाकार के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है। वे क्रमचय ग्राफ की धारणा का सामान्यीकरण हैं, बदले में वे तुलनात्मकता ग्राफ के पूरक के समूह का विशेष स्थिति हैं, जिसे सह-तुलनीयता ग्राफ के रूप में जाना जाता है।
* [[[[यूनिट डिस्क]] ग्राफ]] को प्लेन में यूनिट डिस्क के इंटरसेक्शन ग्राफ के रूप में परिभाषित किया गया है।
* [[यूनिट डिस्क|यूनिट डिस्क ग्राफ]] को प्लेन में यूनिट डिस्क के इंटरसेक्शन ग्राफ के रूप में परिभाषित किया गया है।
* एक वृत्त ग्राफ एक वृत्त की जीवाओं के समूह का प्रतिच्छेदन ग्राफ है।
* वृत्त ग्राफ वृत्त की जीवाओं के समूह का प्रतिच्छेदन ग्राफ है।
* [[सर्कल पैकिंग प्रमेय]] में कहा गया है कि [[प्लेनर ग्राफ]] गैर-क्रॉसिंग सर्किलों से घिरे विमान में बंद डिस्क के परिवारों के बिल्कुल प्रतिच्छेदन ग्राफ हैं।
* [[सर्कल पैकिंग प्रमेय]] में कहा गया है कि [[प्लेनर ग्राफ]] गैर-क्रॉसिंग सर्किलों से घिरे विमान में बंद डिस्क के समूहों के बिल्कुल प्रतिच्छेदन ग्राफ हैं।
* स्कीनरमैन के अनुमान (अब एक प्रमेय) में कहा गया है कि प्रत्येक प्लानर ग्राफ को विमान में [[रेखा खंड]]ों के एक प्रतिच्छेदन ग्राफ के रूप में भी दर्शाया जा सकता है। हालाँकि, रेखा खंडों के प्रतिच्छेदन रेखांकन गैर-योजनाबद्ध भी हो सकते हैं, और रेखा खंडों के प्रतिच्छेदन रेखांकन को पहचानना वास्तविक के अस्तित्वगत सिद्धांत के लिए [[पूर्ण (जटिलता)]] है {{harv|Schaefer|2010}}.
* स्कीनरमैन के अनुमान (अब प्रमेय) में कहा गया है कि प्रत्येक प्लानर ग्राफ को विमान में [[रेखा खंड|रेखा खंडों]] के प्रतिच्छेदन ग्राफ के रूप में भी दर्शाया जा सकता है। चूँकि, रेखा खंडों के प्रतिच्छेदन रेखांकन गैर-योजनाबद्ध भी हो सकते हैं, और रेखा खंडों के प्रतिच्छेदन रेखांकन को पहचानना वास्तविक के अस्तित्व सिद्धांत के लिए पूरा हो गया है {{harv|शेफ़र|2010}}
* ग्राफ़ G के [[लाइन ग्राफ]]को G के किनारों के प्रतिच्छेदन ग्राफ़ के रूप में परिभाषित किया गया है, जहाँ हम प्रत्येक किनारे को उसके दो समापन बिंदुओं के सेट के रूप में दर्शाते हैं।
* ग्राफ़ G के [[लाइन ग्राफ]] को G के किनारों के प्रतिच्छेदन ग्राफ़ के रूप में परिभाषित किया गया है, जहाँ हम प्रत्येक किनारे को उसके दो समापन बिंदुओं के समुच्चय के रूप में दर्शाते हैं।
* एक [[स्ट्रिंग ग्राफ]] [[समतल वक्र]] का प्रतिच्छेदन ग्राफ है।
* [[स्ट्रिंग ग्राफ]] [[समतल वक्र]] का प्रतिच्छेदन ग्राफ है।
* एक ग्राफ़ में [[बॉक्सिसिटी]] k है यदि यह आयाम k के बहुआयामी [[ अतिआयत ]] का प्रतिच्छेदन ग्राफ़ है, लेकिन किसी छोटे आयाम का नहीं है।
* ग्राफ़ में [[बॉक्सिसिटी]] k है यदि यह आयाम k के बहुआयामी [[ अतिआयत |बक्से]] का प्रतिच्छेदन ग्राफ़ है, किन्तु किसी छोटे आयाम का नहीं प्रतिच्छेदन ग्राफ़ है।
* एक [[ ग्राफ क्लिक करें ]] दूसरे ग्राफ के [[अधिकतम क्लिक]]्स का प्रतिच्छेदन ग्राफ है
* [[ ग्राफ क्लिक करें |क्लिक ग्राफ]] दूसरे ग्राफ के [[अधिकतम क्लिक|अधिकतम क्लिक्स]] का प्रतिच्छेदन ग्राफ है।
* क्लिक ट्री का एक [[ब्लॉक ग्राफ]] दूसरे ग्राफ के [[द्विसंबद्ध घटक]]ों का प्रतिच्छेदन ग्राफ है
* क्लिक ट्री का एक [[ब्लॉक ग्राफ]] दूसरे ग्राफ के [[द्विसंबद्ध घटक|द्विसंबद्ध घटकों]] का प्रतिच्छेदन ग्राफ है।


{{harvtxt|Scheinerman|1985}} रेखांकन के प्रतिच्छेदन वर्गों की विशेषता है, परिमित रेखांकन के परिवार जिन्हें सेट के दिए गए परिवार से तैयार किए गए सेट के प्रतिच्छेदन ग्राफ के रूप में वर्णित किया जा सकता है। यह आवश्यक और पर्याप्त है कि परिवार में निम्नलिखित गुण हों:
{{harvtxt|शीनरमैन|1985}} रेखांकन के प्रतिच्छेदन वर्गों की विशेषता है, परिमित रेखांकन के समूह जिन्हें समुच्चय के दिए गए समूह से तैयार किए गए समुच्चय के प्रतिच्छेदन ग्राफ के रूप में वर्णित किया जा सकता है। यह आवश्यक और पर्याप्त है कि समूह में निम्नलिखित गुण हों:
* परिवार में एक ग्राफ का प्रत्येक [[प्रेरित सबग्राफ]] भी परिवार में होना चाहिए।
* समूह में ग्राफ का प्रत्येक [[प्रेरित सबग्राफ]] भी समूह में होना चाहिए।
* परिवार में एक शीर्ष को क्लिक (ग्राफ सिद्धांत) द्वारा प्रतिस्थापित करके परिवार में एक ग्राफ से गठित प्रत्येक ग्राफ भी परिवार से संबंधित होना चाहिए।
* समूह में शीर्ष को क्लिक द्वारा प्रतिस्थापित करके समूह में ग्राफ से गठित प्रत्येक ग्राफ भी समूह से संबंधित होना चाहिए।
*परिवार में रेखांकन का एक अनंत अनुक्रम मौजूद है, जिनमें से प्रत्येक अनुक्रम में अगले ग्राफ का एक प्रेरित सबग्राफ है, संपत्ति के साथ कि परिवार में प्रत्येक ग्राफ अनुक्रम में एक ग्राफ का एक प्रेरित सबग्राफ है।
*समूह में रेखांकन का अनंत अनुक्रम उपस्थित है, जिनमें से प्रत्येक अनुक्रम में अगले ग्राफ का प्रेरित सबग्राफ है, संपत्ति के साथ कि समूह में प्रत्येक ग्राफ अनुक्रम में ग्राफ का प्रेरित सबग्राफ है।
यदि प्रतिच्छेदन ग्राफ अभ्यावेदन की अतिरिक्त आवश्यकता है कि अलग-अलग सिरों को अलग-अलग सेटों द्वारा दर्शाया जाना चाहिए, तो क्लिक विस्तार संपत्ति को छोड़ा जा सकता है।
यदि प्रतिच्छेदन ग्राफ अभ्यावेदन की अतिरिक्त आवश्यकता है कि अलग-अलग सिरों को अलग-अलग समुच्चयों द्वारा दर्शाया जाना चाहिए, तो क्लिक विस्तार गुण को छोड़ा जा सकता है।


== संबंधित अवधारणाएं ==
== संबंधित अवधारणाएं ==
एक [[ आदेश सिद्धांत ]] | इंटरसेक्शन ग्राफ़ के लिए ऑर्डर-सैद्धांतिक एनालॉग शामिल किए जाने के ऑर्डर हैं। उसी तरह जिस तरह एक ग्राफ का एक प्रतिच्छेदन प्रतिनिधित्व प्रत्येक शीर्ष को एक सेट के साथ लेबल करता है ताकि कोने आसन्न हों यदि और केवल अगर उनके सेट में गैर-रिक्त चौराहा है, तो एक [[ poset ]] का समावेशन प्रतिनिधित्व प्रत्येक तत्व को एक सेट के साथ लेबल करता है ताकि किसी के लिए पॉसेट में x और y, x ≤ y अगर और केवल अगर f(x) ⊆ f(y)
इंटरसेक्शन ग्राफ़ के लिए ऑर्डर-सैद्धांतिक एनालॉग सम्मिलित किए जाने के ऑर्डर हैं। उसी प्रकार जिस प्रकार ग्राफ का प्रतिच्छेदन प्रतिनिधित्व प्रत्येक शीर्ष को एक समुच्चय के साथ लेबल करता है जिससे कोने आसन्न हों यदि और केवल यदि उनके समुच्चय में गैर-रिक्त प्रतिच्छेदन है, जिससे पोसेट में किसी भी x और y के लिए, x y यदि और केवल यदि f(x) ⊆ f(y) हो।


== यह भी देखें ==
== यह भी देखें ==
Line 92: Line 90:
  | year = 1985| doi-access = free
  | year = 1985| doi-access = free
  }}.
  }}.
== अग्रिम पठन ==
== अग्रिम पठन ==
* For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see {{harvtxt|McKee|McMorris|1999}}.
* For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see {{harvtxt|McKee|McMorris|1999}}.
== बाहरी संबंध ==
== बाहरी संबंध ==


Line 103: Line 97:
* E. Prisner, [http://www.eprisner.de/Journey/Rahmen.html A Journey through Intersection Graph County]
* E. Prisner, [http://www.eprisner.de/Journey/Rahmen.html A Journey through Intersection Graph County]


{{DEFAULTSORT:Intersection Graph}}[[Category: रेखांकन के चौराहे वर्ग | रेखांकन के चौराहे वर्ग ]]
{{DEFAULTSORT:Intersection Graph}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 28/02/2023|Intersection Graph]]
[[Category:Created On 28/02/2023]]
[[Category:Lua-based templates|Intersection Graph]]
[[Category:Machine Translated Page|Intersection Graph]]
[[Category:Pages with script errors|Intersection Graph]]
[[Category:Short description with empty Wikidata description|Intersection Graph]]
[[Category:Templates Vigyan Ready|Intersection Graph]]
[[Category:Templates that add a tracking category|Intersection Graph]]
[[Category:Templates that generate short descriptions|Intersection Graph]]
[[Category:Templates using TemplateData|Intersection Graph]]
[[Category:रेखांकन के चौराहे वर्ग| रेखांकन के चौराहे वर्ग ]]

Latest revision as of 10:53, 15 March 2023

इंटरसेक्टिंग समुच्चय कैसे ग्राफ को परिभाषित करता है इसका उदाहरण।

ग्राफ सिद्धांत में, प्रतिच्छेदन ग्राफ एक ग्राफ है जो समुच्चय के समूह के प्रतिच्छेदन के पैटर्न का प्रतिनिधित्व करता है। किसी भी ग्राफ़ को प्रतिच्छेदन ग्राफ़ के रूप में दर्शाया जा सकता है, किन्तु ग्राफ़ के कुछ महत्वपूर्ण विशेष वर्गों को उन समुच्चयों के प्रकारों द्वारा परिभाषित किया जा सकता है, जिनका उपयोग उनका प्रतिच्छेदन प्रतिनिधित्व करने के लिए किया जाता है।

औपचारिक परिभाषा

औपचारिक रूप से, प्रतिच्छेदन ग्राफ G समुच्चय के समूह से बना अप्रत्यक्ष ग्राफ है,

प्रत्येक समुच्चय Si के लिए शीर्ष vi बनाकर , और दो शीर्षों vi और vj को एक किनारे से जोड़कर जब भी संगत दो समुच्चयों में गैर-रिक्त प्रतिच्छेदन होता है, अर्थात

सभी रेखांकन प्रतिच्छेदन रेखांकन हैं

कोई भी अप्रत्यक्ष ग्राफ G को प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है। G के प्रत्येक शीर्ष vi के लिए , समुच्चय Si बनाएं जिसमें किनारे vi से जुड़े हों; तो दो ऐसे समुच्चयों में गैर-रिक्त प्रतिच्छेदन होता है यदि और केवल यदि संबंधित कोने किनारे साझा करते हैं। इसलिए, G समुच्चय Si का प्रतिच्छेदन ग्राफ है।

एर्डोस, गुडमैन & पोसा (1966) एक ऐसा निर्माण प्रदान करते हैं जो अधिक कुशल है, इस अर्थ में कि इसके लिए सभी समुच्चय Si संयुक्त में तत्वों की छोटी संख्या की आवश्यकता होती है। इसके लिए, समुच्चय तत्वों की कुल संख्या अधिक से अधिक n2/4, जहां n ग्राफ में शीर्षों की संख्या है। वे इस अवलोकन का श्रेय स्ज़पिलराजन-मार्क्ज़वेस्की (1945) को देते हैं कि सभी ग्राफ़ प्रतिच्छेदन ग्राफ़ हैं , किन्तु कुलिक (1964) इसे देखने के लिए भी कहते है। किसी ग्राफ़ का प्रतिच्छेदन संख्या ग्राफ़ के किसी भी प्रतिच्छेदन प्रतिनिधित्व में तत्वों की न्यूनतम कुल संख्या है।

प्रतिच्छेदन रेखांकन की कक्षाएं

कई महत्वपूर्ण ग्राफ़ समूहों को अधिक प्रतिबंधित प्रकार के समुच्चय समूहों के प्रतिच्छेदन ग्राफ़ के रूप में वर्णित किया जा सकता है, उदाहरण के लिए किसी प्रकार के ज्यामितीय विन्यास से प्राप्त समुच्चय :

  • अंतराल ग्राफ को वास्तविक रेखा पर अंतरालों के प्रतिच्छेदन ग्राफ या पथ ग्राफ के जुड़े हुए सबग्राफ के रूप में परिभाषित किया जाता है।
  • उदासीनता ग्राफ को वास्तविक रेखा पर इकाई अंतरालों के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जा सकता है।
  • वृत्ताकार चाप ग्राफ को वृत्ताकार चाप के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है।
  • बहुभुज-वृत्त ग्राफ को वृत्त पर कोनों वाले बहुभुजों के प्रतिच्छेदन के रूप में परिभाषित किया जाता है।
  • कॉर्डल ग्राफ का लक्षण ट्री के जुड़े सबग्राफ के प्रतिच्छेदन ग्राफ़ के रूप में है।
  • समलम्बाकार ग्राफ को दो समांतर रेखाओं से बने समलम्बाकार के प्रतिच्छेदन ग्राफ के रूप में परिभाषित किया जाता है। वे क्रमचय ग्राफ की धारणा का सामान्यीकरण हैं, बदले में वे तुलनात्मकता ग्राफ के पूरक के समूह का विशेष स्थिति हैं, जिसे सह-तुलनीयता ग्राफ के रूप में जाना जाता है।
  • यूनिट डिस्क ग्राफ को प्लेन में यूनिट डिस्क के इंटरसेक्शन ग्राफ के रूप में परिभाषित किया गया है।
  • वृत्त ग्राफ वृत्त की जीवाओं के समूह का प्रतिच्छेदन ग्राफ है।
  • सर्कल पैकिंग प्रमेय में कहा गया है कि प्लेनर ग्राफ गैर-क्रॉसिंग सर्किलों से घिरे विमान में बंद डिस्क के समूहों के बिल्कुल प्रतिच्छेदन ग्राफ हैं।
  • स्कीनरमैन के अनुमान (अब प्रमेय) में कहा गया है कि प्रत्येक प्लानर ग्राफ को विमान में रेखा खंडों के प्रतिच्छेदन ग्राफ के रूप में भी दर्शाया जा सकता है। चूँकि, रेखा खंडों के प्रतिच्छेदन रेखांकन गैर-योजनाबद्ध भी हो सकते हैं, और रेखा खंडों के प्रतिच्छेदन रेखांकन को पहचानना वास्तविक के अस्तित्व सिद्धांत के लिए पूरा हो गया है (शेफ़र 2010)
  • ग्राफ़ G के लाइन ग्राफ को G के किनारों के प्रतिच्छेदन ग्राफ़ के रूप में परिभाषित किया गया है, जहाँ हम प्रत्येक किनारे को उसके दो समापन बिंदुओं के समुच्चय के रूप में दर्शाते हैं।
  • स्ट्रिंग ग्राफ समतल वक्र का प्रतिच्छेदन ग्राफ है।
  • ग्राफ़ में बॉक्सिसिटी k है यदि यह आयाम k के बहुआयामी बक्से का प्रतिच्छेदन ग्राफ़ है, किन्तु किसी छोटे आयाम का नहीं प्रतिच्छेदन ग्राफ़ है।
  • क्लिक ग्राफ दूसरे ग्राफ के अधिकतम क्लिक्स का प्रतिच्छेदन ग्राफ है।
  • क्लिक ट्री का एक ब्लॉक ग्राफ दूसरे ग्राफ के द्विसंबद्ध घटकों का प्रतिच्छेदन ग्राफ है।

शीनरमैन (1985) रेखांकन के प्रतिच्छेदन वर्गों की विशेषता है, परिमित रेखांकन के समूह जिन्हें समुच्चय के दिए गए समूह से तैयार किए गए समुच्चय के प्रतिच्छेदन ग्राफ के रूप में वर्णित किया जा सकता है। यह आवश्यक और पर्याप्त है कि समूह में निम्नलिखित गुण हों:

  • समूह में ग्राफ का प्रत्येक प्रेरित सबग्राफ भी समूह में होना चाहिए।
  • समूह में शीर्ष को क्लिक द्वारा प्रतिस्थापित करके समूह में ग्राफ से गठित प्रत्येक ग्राफ भी समूह से संबंधित होना चाहिए।
  • समूह में रेखांकन का अनंत अनुक्रम उपस्थित है, जिनमें से प्रत्येक अनुक्रम में अगले ग्राफ का प्रेरित सबग्राफ है, संपत्ति के साथ कि समूह में प्रत्येक ग्राफ अनुक्रम में ग्राफ का प्रेरित सबग्राफ है।

यदि प्रतिच्छेदन ग्राफ अभ्यावेदन की अतिरिक्त आवश्यकता है कि अलग-अलग सिरों को अलग-अलग समुच्चयों द्वारा दर्शाया जाना चाहिए, तो क्लिक विस्तार गुण को छोड़ा जा सकता है।

संबंधित अवधारणाएं

इंटरसेक्शन ग्राफ़ के लिए ऑर्डर-सैद्धांतिक एनालॉग सम्मिलित किए जाने के ऑर्डर हैं। उसी प्रकार जिस प्रकार ग्राफ का प्रतिच्छेदन प्रतिनिधित्व प्रत्येक शीर्ष को एक समुच्चय के साथ लेबल करता है जिससे कोने आसन्न हों यदि और केवल यदि उनके समुच्चय में गैर-रिक्त प्रतिच्छेदन है, जिससे पोसेट में किसी भी x और y के लिए, x ≤ y यदि और केवल यदि f(x) ⊆ f(y) हो।

यह भी देखें

संदर्भ

  • Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), Prague: Publ. House Czechoslovak Acad. Sci., pp. 13–20, MR 0176940.
  • Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575, S2CID 646660.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
  • Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Math., 33: 303–307, doi:10.4064/fm-33-1-303-307, MR 0015448.
  • Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF), Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 334–344, doi:10.1007/978-3-642-11805-0_32, ISBN 978-3-642-11804-3.
  • Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", Discrete Mathematics, 55 (2): 185–193, doi:10.1016/0012-365X(85)90047-0, MR 0798535.

अग्रिम पठन

  • For an overview of both the theory of intersection graphs and important special classes of intersection graphs, see McKee & McMorris (1999).

बाहरी संबंध