अंतराल ग्राफ

Not to be confused with डी-अंतराल हाइपरग्राफ.

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

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

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

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

परिभाषा

एक अंतराल ग्राफ एक अप्रत्यक्ष ग्राफ 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 \}$ है।

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

विवरण

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

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

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

• एक ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि इसके अधिकतम गुट (ग्राफ सिद्धांत) को $M_{1},M_{2},\dots ,M_{k}$ का तर्कसंगत किया जा सकता है ऐसा है कि इनमें से दो समुच्चयों से संबंधित प्रत्येक शीर्ष भी क्रम में उनके बीच सभी समुच्चयों से संबंधित है। अर्थात्, प्रत्येक $v\in M_{i}\cap M_{k}$ के लिए $i<k$ के साथ, ऐसा भी होता है कि $v\in M_{j}$ जब भी $i<j<k$ होता है।
• एक ग्राफ एक अंतराल ग्राफ है यदि और मात्र यदि इसमें एक प्रेरित उपग्राफ के रूप में चक्र ग्राफ $C_{4}$ सम्मिलित नहीं है और एक तुलनात्मक ग्राफ का पूरक है।

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

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

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

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

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

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

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

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

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

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

जुड़ा हुआ त्रिकोण-मुक्त अंतराल ग्राफ पूर्णतः कमला का पेड़ पेड़ हैं।

उचित अंतराल ग्राफ

Main article: Proper interval graph

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

एक अंतराल ग्राफ कहा जाता है $q$-उचित यदि कोई प्रतिनिधित्व है जिसमें कोई अंतराल अधिक से अधिक निहित नहीं है $q$ अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-उचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है। एक अंतराल ग्राफ कहा जाता है $p$-अनुचित यदि कोई प्रतिनिधित्व है जिसमें कोई अंतराल से अधिक नहीं है $p$ अन्य। यह धारणा उचित अंतराल ग्राफ़ के विचार को विस्तारित करती है जैसे कि 0-अनुचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है। एक अंतराल ग्राफ है $$