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

Revision as of 16:40, 13 March 2023

वास्तविक रेखा पर सात अंतराल और संबंधित सात-शीर्ष अंतराल ग्राफ।

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

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

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

परिभाषा

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

S_{i},\quad i=0,1,2,\dots

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

E(G)=\{(v_{i},v_{j})\mid S_{i}\cap S_{j}\neq \emptyset \}

है।

यह अंतरालों का प्रतिच्छेदन ग्राफ है।

विवरण

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

ग्राफ़ एक अंतराल ग्राफ़ है यदि और मात्र यदि यह तारकीय और एटी-मुक्त है।^[1]

अन्य विवरण वर्णन:

ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि इसके अधिकतम गुट(ग्राफ सिद्धांत) को $M_{1},M_{2},\dots ,M_{k}$

[1]

@@ Line 1: / Line 1: @@
 {{Short description|Intersection graph for intervals on the real number line}}
 {{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>
-के एक वर्ग से प्रत्येक अंतराल  {{mvar|S{{sub|i}}}} के लिए शीर्ष {{mvar|v{{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> है।
 यह अंतरालों का प्रतिच्छेदन ग्राफ है।
@@ Line 16: / Line 16: @@
 == विवरण ==
-एक ग्राफ़ में तीन शीर्ष एक क्षुद्रग्रह त्रिपक्षीय (एटी) बनाते हैं, यदि प्रत्येक दो के लिए, उन दोनों में से एक पथ स्थित है परन्तु   तीसरे का कोई निकटवर्ती   नहीं है। एक ग्राफ एटी-मुक्त है यदि इसमें कोई क्षुद्रग्रह त्रिपक्षीय नहीं है। अंतराल ग्राफ़ का सबसे प्रथम विवरण वर्णन निम्न प्रतीत होता है:
+एक ग्राफ़ में तीन शीर्ष एक क्षुद्रग्रह त्रिपक्षीय(एटी) बनाते हैं, यदि प्रत्येक दो के लिए, उन दोनों में से एक पथ स्थित है परन्तु तीसरे का कोई निकटवर्ती नहीं है। एक ग्राफ एटी-मुक्त है यदि इसमें कोई क्षुद्रग्रह त्रिपक्षीय नहीं है। अंतराल ग्राफ़ का सबसे प्रथम विवरण वर्णन निम्न प्रतीत होता है:
-* एक ग्राफ़ एक अंतराल ग्राफ़ है यदि  और मात्र  यदि  यह तारकीय और एटी-मुक्त है।{{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>
@@ Line 30: / Line 30: @@
 == कुशल पहचान एल्गोरिथ्म ==
-यह निर्धारित करना कि क्या एक  दिया गया ग्राफ <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|बूथ|ल्यूकर |1976}} का मूल रेखीय समय पहचान एल्गोरिथम उनकी जटिल पीक्यू ट्री डेटा संरचना पर आधारित है, परन्तु   {{harvtxt|हबीब |मैककोनेल|पॉल|वियनॉट|2000}} ने दिखाया कि [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज|कोषगत चौड़ाई-प्रथम खोज]] का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि एक ग्राफ एक अंतराल ग्राफ है यदि  और मात्र  यदि  यह तारकीय ग्राफ है और इसका [[पूरक (ग्राफ सिद्धांत)]] एक तुलनात्मक ग्राफ है।<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref> 6-प्रभावक्षेत्र लेक्सबीएफएस  एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण {{harvtxt|कॉर्नियल|ओलारियू|स्टीवर्ट|2009}}  में वर्णित किया गया है।
+{{harvtxt|बूथ|ल्यूकर |1976}} का मूल रेखीय समय पहचान एल्गोरिथम उनकी जटिल पीक्यू ट्री डेटा संरचना पर आधारित है, परन्तु {{harvtxt|हबीब |मैककोनेल|पॉल|वियनॉट|2000}} ने दिखाया कि [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज|कोषगत चौड़ाई-प्रथम खोज]] का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि यह तारकीय ग्राफ है और इसका [[पूरक (ग्राफ सिद्धांत)|पूरक(ग्राफ सिद्धांत)]] एक तुलनात्मक ग्राफ है।<ref>{{harvtxt|Fishburn|1985}}; {{harvtxt|Golumbic|1980}}</ref> 6-प्रभावक्षेत्र लेक्सबीएफएस एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण {{harvtxt|कॉर्नियल|ओलारियू|स्टीवर्ट|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|उचित अंतराल ग्राफ}}
-उचित अंतराल ग्राफ़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें कोई अंतराल किसी अन्य अंतराल को उपसमुच्चय नहीं करता है; [[इकाई अंतराल ग्राफ]]़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल प्रतिनिधित्व होता है जिसमें प्रत्येक अंतराल की इकाई लंबाई होती है। बार-बार अंतराल के बिना एक इकाई अंतराल प्रतिनिधित्व आवश्यक रूप से एक उचित अंतराल प्रतिनिधित्व है। प्रत्येक उचित अंतराल प्रतिनिधित्व एक इकाई अंतराल प्रतिनिधित्व नहीं है, परन्तु   प्रत्येक उचित अंतराल ग्राफ एक इकाई अंतराल ग्राफ है, और इसके विपरीत।<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}}
+विशिष्ट अंतराल ग्राफ़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल निरूपण होता है जिसमें कोई अंतराल किसी अन्य अंतराल को उपसमुच्चय नहीं करता है; [[इकाई अंतराल ग्राफ]] वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल निरूपण होता है जिसमें प्रत्येक अंतराल की इकाई लंबाई होती है। बार-बार अंतराल के बिना एक इकाई अंतराल निरूपण आवश्यक रूप से एक विशिष्ट अंतराल निरूपण है। प्रत्येक विशिष्ट अंतराल निरूपण एक इकाई अंतराल निरूपण नहीं है, परन्तु प्रत्येक विशिष्ट अंतराल ग्राफ एक इकाई अंतराल ग्राफ है, और इसके विपरीत।<ref>{{harvtxt|Roberts|1969}}; {{harvtxt|Gardi|2007}}</ref> प्रत्येक विशिष्ट अंतराल ग्राफ [[पंजा मुक्त ग्राफ|नखर मुक्त ग्राफ]] है; इसके विपरीत, विशिष्ट अंतराल ग्राफ यथार्थ नखर-मुक्त अंतराल ग्राफ होते हैं। यद्यपि, नखर-मुक्त ग्राफ़ स्थित हैं जो अंतराल ग्राफ़ नहीं हैं।{{sfnp|Faudree|Flandrin|Ryjáček|1997|p=89}}
-एक अंतराल ग्राफ कहा जाता है <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>q</math>-विशिष्ट कहा जाता है यदि कोई निरूपण है जिसमें कोई अंतराल <math>q</math> अन्य से अधिक निहित नहीं होता है। यह धारणा विशिष्ट अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-विशिष्ट अंतराल ग्राफ़ एक विशिष्ट अंतराल ग्राफ़ है।{{sfnp|Proskurowski|Telle|1999}} एक अंतराल ग्राफ को <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}}
 == अनुप्रयोग ==
-अंतराल ग्राफ़ के गणितीय सिद्धांत को [[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}}
 ==टिप्पणियाँ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 16:40, 13 March 2023

Contents

परिभाषा

विवरण