अंतराल ग्राफ

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

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

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

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

परिभाषा

एक अंतराल ग्राफ अप्रत्यक्ष ग्राफ $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}$ का तर्कसंगत किया जा सकता है ऐसा है कि इनमें से दो समुच्चयों से संबंधित प्रत्येक शीर्ष भी क्रम में उनके बीच सभी समुच्चयों से संबंधित है। अर्थात्, प्रत्येक $v\in M_{i}\cap M_{k}$ के लिए $i<k$ के साथ, ऐसा भी होता है कि $v\in M_{j}$ जब भी $i<j<k$ होता है।^[2]
ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि इसमें एक प्रेरित उपग्राफ के रूप में चक्र ग्राफ $C_{4}$ सम्मिलित नहीं है और एक तुलनात्मक ग्राफ का पूरक है।^[3]

अंतराल ग्राफ और प्रकार के विभिन्न अन्य विवरण वर्णन किए गए हैं।^[4]

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

यह निर्धारित करना कि क्या एक दिया गया ग्राफ $G=(V,E)$ एक अंतराल ग्राफ है, $O(|V|+|E|)$ समय में किया जा सकता है, $G$ के अधिकतम गुटों के तर्कसंगत की मांग करके जो शीर्ष समावेशन के संबंध में निरंतर है। इस समस्या के लिए कई ज्ञात एल्गोरिदम इस प्रकार से काम करते हैं, यद्यपि उनके गुट् का उपयोग किए बिना रैखिक समय में अंतराल ग्राफ को पहचानना भी संभव है।^[5]

बूथ & ल्यूकर (1976) का मूल रेखीय समय पहचान एल्गोरिथम उनकी जटिल पीक्यू ट्री डेटा संरचना पर आधारित है, परन्तु हबीब et al. (2000) ने दिखाया कि कोषगत चौड़ाई-प्रथम खोज का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि यह तारकीय ग्राफ है और इसका पूरक(ग्राफ सिद्धांत) एक तुलनात्मक ग्राफ है।^[6] 6-प्रभावक्षेत्र लेक्सबीएफएस एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण कॉर्नियल, ओलारियू & स्टीवर्ट (2009) में वर्णित किया गया है।

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

एटी-मुक्त तारकीय ग्राफ़ के रूप में अंतराल ग्राफ़ के विवरण वर्णन से,^[1] अंतराल ग्राफ़ दृढ़ता से तारकीय ग्राफ होते हैं और इसलिए उत्तम ग्राफ़ होते हैं। उनका पूरक ग्राफ तुलनीयता ग्राफ के वर्ग से संबंधित है,^[3] और तुलनीयता संबंध निश्चित रूप से अंतराल क्रम हैं।^[7]

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

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

ग्राफ़ में बॉक्सिसिटी अधिक से अधिक एक होती है यदि और मात्र यदि यह एक अंतराल ग्राफ़ है; यादृच्छिक ग्राफ $G$ की बॉक्सिकता अंतराल के एक ही समुच्चय पर अंतराल ग्राफ़ की न्यूनतम संख्या है जैसे कि अंतराल ग्राफ़ के किनारों के समुच्चय का प्रतिच्छेदन $G$ है।

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

जुड़ा हुआ त्रिकोण-मुक्त अंतराल ग्राफ पूर्णतः कैटरपिलर ट्री हैं।^[8]

विशिष्ट अंतराल ग्राफ

विशिष्ट अंतराल ग्राफ़ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल निरूपण होता है जिसमें कोई अंतराल किसी अन्य अंतराल को उपसमुच्चय नहीं करता है; इकाई अंतराल ग्राफ वे अंतराल ग्राफ़ होते हैं जिनका एक अंतराल निरूपण होता है जिसमें प्रत्येक अंतराल की इकाई लंबाई होती है। बार-बार अंतराल के बिना एक इकाई अंतराल निरूपण आवश्यक रूप से एक विशिष्ट अंतराल निरूपण है। प्रत्येक विशिष्ट अंतराल निरूपण एक इकाई अंतराल निरूपण नहीं है, परन्तु प्रत्येक विशिष्ट अंतराल ग्राफ एक इकाई अंतराल ग्राफ है, और इसके विपरीत।^[9] प्रत्येक विशिष्ट अंतराल ग्राफ नखर मुक्त ग्राफ है; इसके विपरीत, विशिष्ट अंतराल ग्राफ यथार्थ नखर-मुक्त अंतराल ग्राफ होते हैं। यद्यपि, नखर-मुक्त ग्राफ़ स्थित हैं जो अंतराल ग्राफ़ नहीं हैं।^[10]

एक अंतराल ग्राफ को $q$ -विशिष्ट कहा जाता है यदि कोई निरूपण है जिसमें कोई अंतराल $q$ अन्य से अधिक निहित नहीं होता है। यह धारणा विशिष्ट अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-विशिष्ट अंतराल ग्राफ़ एक विशिष्ट अंतराल ग्राफ़ है।^[11] एक अंतराल ग्राफ को $p$ -अनुचित कहा जाता है यदि कोई निरूपण होता है जिसमें कोई अंतराल $p$ अन्य से अधिक नहीं होता है। यह धारणा विशिष्ट अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-अनुचित अंतराल ग्राफ़ एक विशिष्ट अंतराल ग्राफ़ है।^[12] अंतराल ग्राफ $k$ -नीडन होता है, यदि एक दूसरे में नीडन अंतराल की लंबाई $k+1$ की कोई श्रृंखला नहीं होती है। यह विशिष्ट अंतराल ग्राफ़ का सामान्यीकरण है क्योंकि 1-नीडन अंतराल ग्राफ़ पूर्णतः विशिष्ट अंतराल ग्राफ़ हैं।^[13]

अनुप्रयोग

अंतराल ग्राफ़ के गणितीय सिद्धांत को रैंड निगम के गणित विभाग के शोधकर्ताओं द्वारा अनुप्रयोगों के प्रति एक दृष्टिकोण के साथ विकसित किया गया था, जिसमें युवा शोधकर्ता सम्मिलित थे - जैसे कि पीटर सी. फिशबर्न और एलन सी. टकर और जोएल ई. कोहेन जैसे छात्र - नेताओं के अतिरिक्त - जैसे डी. आर. फुलकर्सन और(आवर्ती आगंतुक) विक्टर क्ले के रूप में।^[14] कोहेन ने अंतराल ग्राफ को जनसंख्या जीव विज्ञान के गणितीय जीव विज्ञान, विशेष रूप से खाद्य जाल के लिए लागू किया।^[15]

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

अंतराल ग्राफ़ का एक इष्टतम ग्राफ़ रंग संसाधनों के कार्यभार का निरूपण करता है जो सभी अनुरोधों को यथासंभव कम संसाधनों के साथ आच्छादन करता है; यह बहुपद समय में एक बहुभक्षक रंग एल्गोरिथ्म द्वारा पाया जा सकता है जो अंतराल को उनके बाएं समापन बिंदुओं द्वारा क्रमबद्ध क्रम में रंगता है।^[17]

अन्य अनुप्रयोगों में आनुवंशिकी, जैव सूचना विज्ञान और कंप्यूटर विज्ञान सम्मिलित हैं। अंतराल ग्राफ का निरूपण करने वाले अंतरालों का एक समुच्चय ढूँढना भी डीएनए प्रतिचित्रण में सन्निहित बाद के संयोजन की विधि के रूप में उपयोग किया जा सकता है।^[18] अंतराल ग्राफ भी अस्थायी तर्क में महत्वपूर्ण भूमिका निभाते हैं।^[19]

अंतराल पूर्णता और पथचौड़ाई

यदि $G$ एक यादृच्छिक ग्राफ है, तो $G$ का अंतराल पूरा करना उसी शीर्ष समुच्चय पर एक अंतराल ग्राफ है जिसमें $G$ एक उपग्राफ के रूप में होता है। अंतराल पूर्णता का पैरामिट्रीकृत संस्करण( $k$ अतिरिक्त किनारों के साथ एक अंतराल सुपरग्राफ खोजें) पैरामिट्रीकृत जटिलता है, और इसके अतिरिक्त, पैरामिट्रीकृत उप-घातीय समय में हल करने योग्य है।^[20]^[21]

एक अंतराल ग्राफ की पथचौड़ाई उसके अधिकतम गुट के आकार से एक कम है(या समतुल्य, इसकी रंगीन संख्या से एक कम), और किसी भी ग्राफ की पथचौड़ाई $G$ एक अंतराल ग्राफ के सबसे छोटे पथचौड़ाई के समान है जिसमें $G$ उपग्राफ के रूप में सम्मिलित है।^[22]

संदर्भ

Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch (2001), "A unified approach to approximating resource allocation and scheduling", Journal of the ACM, 48 (5): 1069–1090, CiteSeerX 10.1.1.124.9886, doi:10.1145/502102.502107, S2CID 12329294
Beyerl, Jeffery J.; Jamison, Robert E. (2008), "Interval graphs with containment restrictions", Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 191, pp. 117–128, arXiv:1109

[FOOTNOTELekkerkerkerBoland1962-1] 1.0 ^1.1 Lekkerkerker & Boland (1962).

[2] Fulkerson & Gross (1965); Fishburn (1985)

[FOOTNOTEGilmoreHoffman1964-3] 3.0 ^3.1 Gilmore & Hoffman (1964).

[4] McKee & McMorris (1999); Brandstädt, Le & Spinrad (1999)

[FOOTNOTEHsu1992-5] Hsu (1992).

[6] Fishburn (1985); Golumbic (1980)

[FOOTNOTEFishburn1985-7] Fishburn (1985).

[FOOTNOTEEckhoff1993-8] Eckhoff (1993).

[9] Roberts (1969); Gardi (2007)

[FOOTNOTEFaudreeFlandrinRyjáček199789-10] Faudree, Flandrin & Ryjáček (1997), p. 89.

[FOOTNOTEProskurowskiTelle1999-11] Proskurowski & Telle (1999).

[FOOTNOTEBeyerlJamison2008-12] Beyerl & Jamison (2008).

[FOOTNOTEKlavíkOtachiŠejnoha2019-13] Klavík, Otachi & Šejnoha (2019).

[FOOTNOTECohen1978[httpsbooksgooglecombooksprincetonhlenqintervalgraphvidISBN9780691082028redir_escyvsnippetq22interval20graph22ffalse_ix–10]-14] Cohen (1978), pp. ix–10.

[FOOTNOTECohen1978[httpsbooksgooglecombooksprincetonhlenqintervalgraphvidISBN9780691082028redir_escyvsnippetq22interval20graph22ffalse_12–33]-15] Cohen (1978), pp. 12–33.

[FOOTNOTEBar-NoyBar-YehudaFreundNaor2001-16] Bar-Noy et al. (2001).

[FOOTNOTECormenLeisersonRivestStein2001379-17] Cormen et al. (2001), p. 379.

[FOOTNOTEZhangSchonFischerCayanis1994-18] Zhang et al. (1994).

[FOOTNOTEGolumbicShamir1993-19] Golumbic & Shamir (1993).

[FOOTNOTEVillangerHeggernesPaulTelle2009-20] Villanger et al. (2009).

[FOOTNOTEBliznetsFominPilipczukPilipczuk2014-21] Bliznets et al. (2014).

[FOOTNOTEBodlaender1998-22] Bodlaender (1998).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Anonymous

Search

अंतराल ग्राफ

Namespaces

More

Page actions

Contents