अंतराल ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Intersection graph for intervals on the real number line}} {{Distinguish|D-interval hypergraph}} Image:Interval graph.svg|thumb|upright=1.35|वास्...")
 
No edit summary
Line 1: Line 1:
{{Short description|Intersection graph for intervals on the real number line}}
{{Short description|Intersection graph for intervals on the real number line}}
{{Distinguish|D-interval hypergraph}}
{{Distinguish|डी-अंतराल हाइपरग्राफ}}
[[Image:Interval graph.svg|thumb|upright=1.35|वास्तविक रेखा पर सात अंतराल और संबंधित सात-शीर्ष अंतराल ग्राफ।]][[ग्राफ सिद्धांत]] में, एक अंतराल ग्राफ [[वास्तविक रेखा]] पर [[अंतराल (गणित)]] के एक सेट से बना एक [[अप्रत्यक्ष ग्राफ]] है,
[[Image:Interval graph.svg|thumb|upright=1.35|वास्तविक रेखा पर सात अंतराल और संबंधित सात-शीर्ष अंतराल ग्राफ।]][[ग्राफ सिद्धांत]] में, एक अंतराल ग्राफ एक [[अप्रत्यक्ष ग्राफ]]  होता है जो  [[वास्तविक रेखा]] पर [[अंतराल (गणित)]] के एक समुच्चय से बनता है, जिसमें प्रत्येक अंतराल के लिए एक शीर्ष होता है और अंतराल के बीच एक किनारा होता है जिसका अंतराल प्रतिच्छेद करता है। यह अंतरालों का प्रतिच्छेदन ग्राफ है।
प्रत्येक अंतराल के लिए एक शीर्ष और उन शीर्षों के बीच एक किनारे के साथ जिनके अंतराल प्रतिच्छेद करते हैं। यह अंतरालों का प्रतिच्छेदन ग्राफ है।


अंतराल रेखांकन तारकीय रेखांकन और पूर्ण रेखांकन हैं। उन्हें [[रैखिक समय]] में पहचाना जा सकता है, और इन ग्राफों में एक इष्टतम [[ग्राफ रंग]] या अधिकतम क्लिक रैखिक समय में पाया जा सकता है। अंतराल ग्राफ़ में सभी [[उचित अंतराल ग्राफ]]़ शामिल होते हैं, ग्राफ़ को [[इकाई अंतराल]] के सेट से उसी तरह परिभाषित किया जाता है।
अंतराल ग्राफ तारकीय ग्राफ और पूर्ण ग्राफ हैं। उन्हें [[रैखिक समय]] में पहचाना जा सकता है, और इन ग्राफों में एक इष्टतम [[ग्राफ रंग]] या अधिकतम गुट रैखिक समय में पाया जा सकता है। अंतराल ग्राफ़ में सभी [[उचित अंतराल ग्राफ|उचित अंतराल ग्राफ़]] सम्मिलित  होते हैं, ग्राफ़ को [[इकाई अंतराल]] के समुच्चय से उसी प्रकार  परिभाषित किया जाता है।


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


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


== लक्षण ==
== विवरण ==


एक ग्राफ़ में तीन शिखर एक क्षुद्रग्रह ट्रिपल (एटी) बनाते हैं, यदि प्रत्येक दो के लिए, उन दोनों में से एक पथ मौजूद है लेकिन तीसरे का कोई पड़ोसी नहीं है। एक ग्राफ एटी-मुक्त है यदि इसमें कोई क्षुद्रग्रह ट्रिपल नहीं है। अंतराल ग्राफ़ का सबसे पहला लक्षण वर्णन निम्न प्रतीत होता है:
एक ग्राफ़ में तीन शीर्ष एक क्षुद्रग्रह त्रिपक्षीय (एटी) बनाते हैं, यदि प्रत्येक दो के लिए, उन दोनों में से एक पथ स्थित है परन्तु  तीसरे का कोई निकटवर्ती  नहीं है। एक ग्राफ एटी-मुक्त है यदि इसमें कोई क्षुद्रग्रह त्रिपक्षीय नहीं है। अंतराल ग्राफ़ का सबसे प्रथम विवरण वर्णन निम्न प्रतीत होता है:


* एक ग्राफ़ एक अंतराल ग्राफ़ है अगर और केवल अगर यह कॉर्डल और एटी-फ्री है।{{sfnp|Lekkerkerker|Boland|1962}}
* एक ग्राफ़ एक अंतराल ग्राफ़ है यदि  और मात्र  यदि  यह तारकीय और एटी-मुक्त है।{{sfnp|Lekkerkerker|Boland|1962}}


अन्य लक्षण वर्णन:
अन्य विवरण वर्णन:


* एक ग्राफ एक अंतराल ग्राफ है अगर और केवल अगर इसकी अधिकतम [[क्लिक (ग्राफ सिद्धांत)]] का आदेश दिया जा सकता है <math>M_1,M_2,\dots,M_k</math> ऐसा है कि इनमें से दो समूहों से संबंधित प्रत्येक शीर्ष भी क्रम में उनके बीच सभी समूहों से संबंधित है। यानी हर के लिए <math>v\in M_i\cap M_k</math> साथ <math>i<k</math>, ऐसा भी होता है <math>v\in M_j</math> जब कभी भी <math>i<j<k</math>.<ref>{{harvtxt|Fulkerson|Gross|1965}}; {{harvtxt|Fishburn|1985}}</ref>
* एक ग्राफ एक अंतराल ग्राफ है यदि  और मात्र  यदि  इसके अधिकतम [[क्लिक (ग्राफ सिद्धांत)|गुट (ग्राफ सिद्धांत)]] को <math>M_1,M_2,\dots,M_k</math> का  तर्कसंगत किया जा सकता है ऐसा है कि इनमें से दो समुच्चयों से संबंधित प्रत्येक शीर्ष भी क्रम में उनके बीच सभी समुच्चयों से संबंधित है। अर्थात्, प्रत्येक  <math>v\in M_i\cap M_k</math> के लिए <math>i<k</math>   के साथ, ऐसा भी होता है कि <math>v\in M_j</math> जब भी <math>i<j<k</math> होता है।<ref>{{harvtxt|Fulkerson|Gross|1965}}; {{harvtxt|Fishburn|1985}}</ref>
* एक ग्राफ एक अंतराल ग्राफ है अगर और केवल अगर इसमें [[चक्र ग्राफ]] नहीं है <math>C_4</math> एक [[प्रेरित सबग्राफ]] के रूप में और एक [[तुलनात्मक ग्राफ]] का पूरक है।{{sfnp|Gilmore|Hoffman|1964}}
* एक ग्राफ एक अंतराल ग्राफ है यदि  और मात्र  यदि  इसमें एक [[प्रेरित सबग्राफ|प्रेरित उपग्राफ]]  के रूप में  [[चक्र ग्राफ]] <math>C_4</math> सम्मिलित नहीं है और एक [[तुलनात्मक ग्राफ]] का पूरक है।{{sfnp|Gilmore|Hoffman|1964}}


अंतराल रेखांकन और वेरिएंट के विभिन्न अन्य लक्षण वर्णन किए गए हैं।<ref>{{harvtxt|McKee|McMorris|1999}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}</ref>
अंतराल ग्राफ और प्रकार के विभिन्न अन्य विवरण वर्णन किए गए हैं।<ref>{{harvtxt|McKee|McMorris|1999}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}</ref>




== कुशल पहचान एल्गोरिथ्म ==
== कुशल पहचान एल्गोरिथ्म ==


यह निर्धारित करना कि क्या दिया गया ग्राफ <math>G=(V,E)</math> एक अंतराल ग्राफ में किया जा सकता है <math>O(|V|+|E|)</math> के अधिकतम गुटों के आदेश की मांग करके समय <math>G</math> जो वर्टेक्स समावेशन के संबंध में लगातार है। इस समस्या के लिए कई ज्ञात एल्गोरिदम इस तरह से काम करते हैं, हालांकि उनके क्लिक्स का उपयोग किए बिना रैखिक समय में अंतराल ग्राफ को पहचानना भी संभव है।{{sfnp|Hsu|1992}}
यह निर्धारित करना कि क्या एक  दिया गया ग्राफ <math>G=(V,E)</math> एक अंतराल ग्राफ है, <math>O(|V|+|E|)</math> समय में किया जा सकता है, <math>G</math> के अधिकतम गुटों के  तर्कसंगत की मांग करके जो शीर्ष समावेशन के संबंध में निरंतर है। इस समस्या के लिए कई ज्ञात एल्गोरिदम इस प्रकार  से काम करते हैं, यद्यपि  उनके गुट् का उपयोग किए बिना रैखिक समय में अंतराल ग्राफ को पहचानना भी संभव है।{{sfnp|Hsu|1992}}


का मूल रेखीय समय पहचान एल्गोरिथम {{harvtxt|Booth|Lueker|1976}} उनकी जटिल PQ ट्री डेटा संरचना पर आधारित है, लेकिन {{harvtxt|Habib|McConnell|Paul|Viennot|2000}} ने दिखाया कि [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज]] का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि एक ग्राफ एक अंतराल ग्राफ है अगर और केवल अगर यह कॉर्डल ग्राफ है और इसका [[पूरक (ग्राफ सिद्धांत)]] एक तुलनात्मक ग्राफ है।<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref>
{{harvtxt|बूथ|ल्यूकर |1976}} का मूल रेखीय समय पहचान एल्गोरिथम उनकी जटिल पीक्यू ट्री डेटा संरचना पर आधारित है, परन्तु  {{harvtxt|हबीब |मैककोनेल|पॉल|वियनॉट|2000}} ने दिखाया कि [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज|कोषगत चौड़ाई-प्रथम खोज]] का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि एक ग्राफ एक अंतराल ग्राफ है यदि  और मात्र  यदि  यह तारकीय ग्राफ है और इसका [[पूरक (ग्राफ सिद्धांत)]] एक तुलनात्मक ग्राफ है।<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref> 6-प्रभावक्षेत्र लेक्सबीएफएस  एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण {{harvtxt|कॉर्नियल|ओलारियू|स्टीवर्ट|2009}} में वर्णित किया गया है।
6-स्वीप LexBFS एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण में वर्णित है {{harvtxt|Corneil|Olariu|Stewart|2009}}.


== रेखांकन के संबंधित परिवार ==
== ग्राफ के संबंधित वर्ग ==


एटी-फ्री कॉर्डल ग्राफ़ के रूप में अंतराल ग्राफ़ के लक्षण वर्णन द्वारा,{{sfnp|Lekkerkerker|Boland|1962}} अंतराल ग्राफ़ [[जोरदार कॉर्डल ग्राफ]]़ हैं और इसलिए सही ग्राफ़ हैं। उनका [[पूरक ग्राफ]] तुलनीयता ग्राफ के वर्ग से संबंधित है,{{sfnp|Gilmore|Hoffman|1964}} और तुलनीयता संबंध निश्चित रूप से [[अंतराल क्रम]] हैं।{{sfnp|Fishburn|1985}}
एटी-मुक्त तारकीय ग्राफ़ के रूप में अंतराल ग्राफ़ के विवरण वर्णन से,{{sfnp|Lekkerkerker|Boland|1962}} अंतराल ग्राफ़ [[जोरदार कॉर्डल ग्राफ|दृढ़ता से तारकीय ग्राफ]] होते हैं और इसलिए उत्तम ग्राफ़ होते हैं। उनका [[पूरक ग्राफ]] तुलनीयता ग्राफ के वर्ग से संबंधित है,{{sfnp|Gilmore|Hoffman|1964}} और तुलनीयता संबंध निश्चित रूप से [[अंतराल क्रम]] हैं।{{sfnp|Fishburn|1985}}


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


अंतराल ग्राफ़ जिसमें एक अंतराल प्रतिनिधित्व होता है जिसमें प्रत्येक दो अंतराल या तो अलग या नेस्टेड होते हैं, [[तुच्छ रूप से सही ग्राफ]]़ होते हैं।
अंतराल ग्राफ़ जिसमें एक अंतराल प्रतिनिधित्व होता है जिसमें प्रत्येक दो अंतराल या तो अलग या नीडन होते हैं, [[तुच्छ रूप से सही ग्राफ|तुच्छ रूप से उत्तम ग्राफ]] होते हैं।


एक ग्राफ़ में [[बॉक्सिसिटी]] अधिक से अधिक एक होती है यदि और केवल यदि यह एक अंतराल ग्राफ़ है; एक मनमाना ग्राफ की बॉक्सिकता <math>G</math> शीर्षों के एक ही सेट पर अंतराल ग्राफ़ की न्यूनतम संख्या है जैसे कि अंतराल ग्राफ़ के किनारों के सेट का प्रतिच्छेदन है <math>G</math>.
एक ग्राफ़ में [[बॉक्सिसिटी]] अधिक से अधिक एक होती है यदि और मात्र  यदि यह एक अंतराल ग्राफ़ है; यादृच्छिक ग्राफ <math>G</math> की बॉक्सिकता अंतराल के एक ही समुच्चय पर अंतराल ग्राफ़ की न्यूनतम संख्या है जैसे कि अंतराल ग्राफ़ के किनारों के समुच्चय का प्रतिच्छेदन <math>G</math> है।


एक वृत्त के [[चाप (ज्यामिति)]] के प्रतिच्छेदन ग्राफ़ वृत्ताकार-आर्क ग्राफ़ बनाते हैं, ग्राफ़ का एक वर्ग जिसमें अंतराल ग्राफ़ होते हैं। [[ट्रेपेज़ॉइड ग्राफ]]़, ट्रैपेज़ोइड्स के चौराहे जिनके समानांतर पक्ष सभी समान दो समानांतर रेखाओं पर स्थित हैं, अंतराल ग्राफ़ का एक सामान्यीकरण भी हैं।
एक वृत्त के [[चाप (ज्यामिति)]] के प्रतिच्छेदन ग्राफ़ वृत्ताकार-वृत्त-चाप ग्राफ़ बनाते हैं, ग्राफ़ का एक वर्ग जिसमें अंतराल ग्राफ़ होते हैं। [[ट्रेपेज़ॉइड ग्राफ|समलंब चर्तुभुज ग्राफ]], समलंब चर्तुभुज के प्रतिच्छेदन जिनके समानांतर पक्ष सभी समान दो समानांतर रेखाओं पर स्थित हैं, अंतराल ग्राफ़ का एक सामान्यीकरण भी हैं।


जुड़ा हुआ त्रिकोण-मुक्त ग्राफ|त्रिकोण-मुक्त अंतराल ग्राफ बिल्कुल [[कमला का पेड़]] पेड़ हैं।{{sfnp|Eckhoff|1993}}
जुड़ा हुआ त्रिकोण-मुक्त अंतराल ग्राफ पूर्णतः [[कमला का पेड़]] पेड़ हैं।{{sfnp|Eckhoff|1993}}


=== उचित अंतराल रेखांकन ===
=== उचित अंतराल ग्राफ ===
{{main|Proper interval graph}}
{{main|Proper interval graph}}
उचित अंतराल ग्राफ़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें कोई अंतराल किसी अन्य अंतराल को [[सबसेट]] नहीं करता है; [[इकाई अंतराल ग्राफ]]़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें प्रत्येक अंतराल की इकाई लंबाई होती है। बार-बार अंतराल के बिना एक इकाई अंतराल प्रतिनिधित्व आवश्यक रूप से एक उचित अंतराल प्रतिनिधित्व है। प्रत्येक उचित अंतराल प्रतिनिधित्व एक इकाई अंतराल प्रतिनिधित्व नहीं है, लेकिन प्रत्येक उचित अंतराल ग्राफ एक इकाई अंतराल ग्राफ है, और इसके विपरीत।<ref>{{harvtxt|Roberts|1969}}; {{harvtxt|Gardi|2007}}</ref> प्रत्येक उचित अंतराल ग्राफ [[पंजा मुक्त ग्राफ]] है; इसके विपरीत, उचित अंतराल ग्राफ वास्तव में क्लॉ-फ्री अंतराल ग्राफ होते हैं। हालाँकि, क्लॉ-फ्री ग्राफ़ मौजूद हैं जो अंतराल ग्राफ़ नहीं हैं।{{sfnp|Faudree|Flandrin|Ryjáček|1997|p=89}}
उचित अंतराल ग्राफ़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें कोई अंतराल किसी अन्य अंतराल को उपसमुच्चय नहीं करता है; [[इकाई अंतराल ग्राफ]]़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें प्रत्येक अंतराल की इकाई लंबाई होती है। बार-बार अंतराल के बिना एक इकाई अंतराल प्रतिनिधित्व आवश्यक रूप से एक उचित अंतराल प्रतिनिधित्व है। प्रत्येक उचित अंतराल प्रतिनिधित्व एक इकाई अंतराल प्रतिनिधित्व नहीं है, परन्तु  प्रत्येक उचित अंतराल ग्राफ एक इकाई अंतराल ग्राफ है, और इसके विपरीत।<ref>{{harvtxt|Roberts|1969}}; {{harvtxt|Gardi|2007}}</ref> प्रत्येक उचित अंतराल ग्राफ [[पंजा मुक्त ग्राफ]] है; इसके विपरीत, उचित अंतराल ग्राफ वास्तव में क्लॉ-मुक्त अंतराल ग्राफ होते हैं। हालाँकि, क्लॉ-मुक्त ग्राफ़ स्थित हैं जो अंतराल ग्राफ़ नहीं हैं।{{sfnp|Faudree|Flandrin|Ryjáček|1997|p=89}}


एक अंतराल ग्राफ कहा जाता है <math>q</math>-उचित यदि कोई प्रतिनिधित्व है जिसमें कोई अंतराल अधिक से अधिक निहित नहीं है <math>q</math> अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-उचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है।{{sfnp|Proskurowski|Telle|1999}}
एक अंतराल ग्राफ कहा जाता है <math>q</math>-उचित यदि कोई प्रतिनिधित्व है जिसमें कोई अंतराल अधिक से अधिक निहित नहीं है <math>q</math> अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-उचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है।{{sfnp|Proskurowski|Telle|1999}}
एक अंतराल ग्राफ कहा जाता है <math>p</math>-अनुचित अगर कोई प्रतिनिधित्व है जिसमें कोई अंतराल से अधिक नहीं है <math>p</math> अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-अनुचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है।{{sfnp|Beyerl|Jamison|2008}}
एक अंतराल ग्राफ कहा जाता है <math>p</math>-अनुचित यदि  कोई प्रतिनिधित्व है जिसमें कोई अंतराल से अधिक नहीं है <math>p</math> अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-अनुचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है।{{sfnp|Beyerl|Jamison|2008}}
एक अंतराल ग्राफ है <math>k</math>-नेस्टेड अगर लंबाई की कोई श्रृंखला नहीं है <math>k+1</math> एक दूसरे में नेस्टेड अंतराल की। यह उचित अंतराल ग्राफ़ का सामान्यीकरण है क्योंकि 1-नेस्टेड अंतराल ग्राफ़ बिल्कुल उचित अंतराल ग्राफ़ हैं।{{sfnp|Klavík|Otachi|Šejnoha|2019}}
एक अंतराल ग्राफ है <math>k</math>-नीडन यदि  लंबाई की कोई श्रृंखला नहीं है <math>k+1</math> एक दूसरे में नीडन अंतराल की। यह उचित अंतराल ग्राफ़ का सामान्यीकरण है क्योंकि 1-नीडन अंतराल ग्राफ़ पूर्णतः उचित अंतराल ग्राफ़ हैं।{{sfnp|Klavík|Otachi|Šejnoha|2019}}


== अनुप्रयोग ==
== अनुप्रयोग ==
अंतराल ग्राफ़ के गणितीय सिद्धांत को [[RAND Corporation]] के गणित विभाग के शोधकर्ताओं द्वारा अनुप्रयोगों के प्रति एक दृष्टिकोण के साथ विकसित किया गया था, जिसमें युवा शोधकर्ता शामिल थे - जैसे कि पीटर सी. फिशबर्न और एलन सी. टकर और जोएल ई. कोहेन जैसे छात्र - नेताओं के अलावा - जैसे डी. आर. फुलकर्सन और (आवर्ती आगंतुक) [[विक्टर क्ले]] के रूप में।{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false ix–10]}} कोहेन ने अंतराल ग्राफ को [[जनसंख्या जीव विज्ञान]] के [[गणितीय जीव विज्ञान]], विशेष रूप से खाद्य जाले के लिए लागू किया।{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false 12–33]}}
अंतराल ग्राफ़ के गणितीय सिद्धांत को [[RAND Corporation]] के गणित विभाग के शोधकर्ताओं द्वारा अनुप्रयोगों के प्रति एक दृष्टिकोण के साथ विकसित किया गया था, जिसमें युवा शोधकर्ता सम्मिलित  थे - जैसे कि पीटर सी. फिशबर्न और एलन सी. टकर और जोएल ई. कोहेन जैसे छात्र - नेताओं के अलावा - जैसे डी. आर. फुलकर्सन और (आवर्ती आगंतुक) [[विक्टर क्ले]] के रूप में।{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false ix–10]}} कोहेन ने अंतराल ग्राफ को [[जनसंख्या जीव विज्ञान]] के [[गणितीय जीव विज्ञान]], विशेष रूप से खाद्य जाले के लिए लागू किया।{{sfnp|Cohen|1978|pp=[https://books.google.com/books/princeton?hl=en&q=interval+graph&vid=ISBN9780691082028&redir_esc=y#v=snippet&q=%22interval%20graph%22&f=false 12–33]}}


इंटरवल ग्राफ़ का उपयोग संचालन अनुसंधान और [[शेड्यूलिंग (कंप्यूटिंग)]] में संसाधन आवंटन समस्याओं का प्रतिनिधित्व करने के लिए किया जाता है। इन अनुप्रयोगों में, प्रत्येक अंतराल एक विशिष्ट अवधि के लिए एक संसाधन (जैसे एक वितरित कंप्यूटिंग सिस्टम की प्रसंस्करण इकाई या कक्षा के लिए एक कमरा) के अनुरोध का प्रतिनिधित्व करता है। ग्राफ़ के लिए अधिकतम भार स्वतंत्र सेट (ग्राफ़ सिद्धांत) अनुरोधों का सबसे अच्छा सबसेट खोजने की समस्या का प्रतिनिधित्व करता है जो बिना संघर्ष के संतुष्ट हो सकता है।{{sfnp|Bar-Noy|Bar-Yehuda|Freund|Naor|2001}} अधिक जानकारी के लिए [[अंतराल समयबद्धन]] देखें।
इंटरवल ग्राफ़ का उपयोग संचालन अनुसंधान और [[शेड्यूलिंग (कंप्यूटिंग)]] में संसाधन आवंटन समस्याओं का प्रतिनिधित्व करने के लिए किया जाता है। इन अनुप्रयोगों में, प्रत्येक अंतराल एक विशिष्ट अवधि के लिए एक संसाधन (जैसे एक वितरित कंप्यूटिंग सिस्टम की प्रसंस्करण इकाई या कक्षा के लिए एक कमरा) के अनुरोध का प्रतिनिधित्व करता है। ग्राफ़ के लिए अधिकतम भार स्वतंत्र समुच्चय (ग्राफ़ सिद्धांत) अनुरोधों का सबसे अच्छा उपसमुच्चय खोजने की समस्या का प्रतिनिधित्व करता है जो बिना संघर्ष के संतुष्ट हो सकता है।{{sfnp|Bar-Noy|Bar-Yehuda|Freund|Naor|2001}} अधिक जानकारी के लिए [[अंतराल समयबद्धन]] देखें।


अंतराल ग्राफ़ का एक इष्टतम ग्राफ़ रंग संसाधनों के असाइनमेंट का प्रतिनिधित्व करता है जो सभी अनुरोधों को यथासंभव कम संसाधनों के साथ कवर करता है; यह बहुपद समय में एक [[लालची रंग]] एल्गोरिथ्म द्वारा पाया जा सकता है जो अंतराल को उनके बाएं समापन बिंदुओं द्वारा क्रमबद्ध क्रम में रंगता है।{{sfnp|Cormen|Leiserson|Rivest|Stein|2001|p=379}}
अंतराल ग्राफ़ का एक इष्टतम ग्राफ़ रंग संसाधनों के असाइनमेंट का प्रतिनिधित्व करता है जो सभी अनुरोधों को यथासंभव कम संसाधनों के साथ कवर करता है; यह बहुपद समय में एक [[लालची रंग]] एल्गोरिथ्म द्वारा पाया जा सकता है जो अंतराल को उनके बाएं समापन बिंदुओं द्वारा क्रमबद्ध क्रम में रंगता है।{{sfnp|Cormen|Leiserson|Rivest|Stein|2001|p=379}}


अन्य अनुप्रयोगों में आनुवंशिकी, जैव सूचना विज्ञान और कंप्यूटर विज्ञान शामिल हैं। अंतराल ग्राफ का प्रतिनिधित्व करने वाले अंतरालों का एक सेट ढूँढना भी डीएनए मैपिंग में सन्निहित बाद के संयोजन के तरीके के रूप में इस्तेमाल किया जा सकता है।{{sfnp|Zhang|Schon|Fischer|Cayanis|1994}} अंतराल रेखांकन भी लौकिक तर्क में महत्वपूर्ण भूमिका निभाते हैं।{{sfnp|Golumbic|Shamir|1993}}
अन्य अनुप्रयोगों में आनुवंशिकी, जैव सूचना विज्ञान और कंप्यूटर विज्ञान सम्मिलित  हैं। अंतराल ग्राफ का प्रतिनिधित्व करने वाले अंतरालों का एक समुच्चय ढूँढना भी डीएनए प्रतिचित्रण  में सन्निहित बाद के संयोजन के तरीके के रूप में इस्तेमाल किया जा सकता है।{{sfnp|Zhang|Schon|Fischer|Cayanis|1994}} अंतराल ग्राफ भी लौकिक तर्क में महत्वपूर्ण भूमिका निभाते हैं।{{sfnp|Golumbic|Shamir|1993}}


== अंतराल पूर्णता और पाथविड्थ ==
== अंतराल पूर्णता और पाथविड्थ ==
अगर <math>G</math> एक मनमाना ग्राफ है, का अंतराल पूरा करना <math>G</math> उसी वर्टेक्स सेट पर एक अंतराल ग्राफ है जिसमें शामिल है <math>G</math> सबग्राफ के रूप में। अंतराल पूर्णता का पैरामिट्रीकृत संस्करण (अंतराल सुपरग्राफ के साथ खोजें {{mvar|k}} अतिरिक्त किनारे) पैरामिट्रीकृत जटिलता है, और इसके अलावा, पैरामिट्रीकृत उप-घातीय समय में हल करने योग्य है।{{sfnp|Villanger|Heggernes|Paul|Telle|2009}}{{sfnp|Bliznets|Fomin|Pilipczuk|Pilipczuk|2014}}
यदि  <math>G</math> एक यादृच्छिक ग्राफ है, का अंतराल पूरा करना <math>G</math> उसी शीर्ष समुच्चय पर एक अंतराल ग्राफ है जिसमें सम्मिलित  है <math>G</math> उपग्राफ के रूप में। अंतराल पूर्णता का पैरामिट्रीकृत संस्करण (अंतराल सुपरग्राफ के साथ खोजें {{mvar|k}} अतिरिक्त किनारे) पैरामिट्रीकृत जटिलता है, और इसके अलावा, पैरामिट्रीकृत उप-घातीय समय में हल करने योग्य है।{{sfnp|Villanger|Heggernes|Paul|Telle|2009}}{{sfnp|Bliznets|Fomin|Pilipczuk|Pilipczuk|2014}}


एक अंतराल ग्राफ की [[ पथचौड़ाई ]] उसके अधिकतम क्लिक के आकार से एक कम है (या समतुल्य, इसकी रंगीन संख्या से एक कम), और किसी भी ग्राफ की पाथविड्थ <math>G</math> एक अंतराल ग्राफ के सबसे छोटे पाथविड्थ के समान है जिसमें शामिल है <math>G</math> सबग्राफ के रूप में।{{sfnp|Bodlaender|1998}}
एक अंतराल ग्राफ की [[ पथचौड़ाई ]] उसके अधिकतम गुट के आकार से एक कम है (या समतुल्य, इसकी रंगीन संख्या से एक कम), और किसी भी ग्राफ की पाथविड्थ <math>G</math> एक अंतराल ग्राफ के सबसे छोटे पाथविड्थ के समान है जिसमें सम्मिलित  है <math>G</math> उपग्राफ के रूप में।{{sfnp|Bodlaender|1998}}


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 317: Line 315:




== बाहरी संबंध ==
== बा प्रत्येकी संबंध ==
* {{citation | url=http://www.graphclasses.org/classes/gc_234.html | title=interval graph
* {{citation | url=http://www.graphclasses.org/classes/gc_234.html | title=interval graph
   | work = Information System on Graph Classes and their Inclusions}}
   | work = Information System on Graph Classes and their Inclusions}}

Revision as of 16:02, 13 March 2023

Not to be confused with डी-अंतराल हाइपरग्राफ.
File:Interval graph.svg
वास्तविक रेखा पर सात अंतराल और संबंधित सात-शीर्ष अंतराल ग्राफ।

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

अंतराल ग्राफ तारकीय ग्राफ और पूर्ण ग्राफ हैं। उन्हें रैखिक समय में पहचाना जा सकता है, और इन ग्राफों में एक इष्टतम ग्राफ रंग या अधिकतम गुट रैखिक समय में पाया जा सकता है। अंतराल ग्राफ़ में सभी उचित अंतराल ग्राफ़ सम्मिलित होते हैं, ग्राफ़ को इकाई अंतराल के समुच्चय से उसी प्रकार परिभाषित किया जाता है।

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

परिभाषा

एक अंतराल ग्राफ एक अप्रत्यक्ष ग्राफ G है जो अंतराल

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