अंतराल ग्राफ

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-अनुचित अंतराल ग्राफ़ एक उचित अंतराल ग्राफ़ है। एक अंतराल ग्राफ है $k$-नीडन यदि लंबाई की कोई श्रृंखला नहीं है $k+1$ एक दूसरे में नीडन अंतराल की। यह उचित अंतराल ग्राफ़ का सामान्यीकरण है क्योंकि 1-नीडन अंतराल ग्राफ़ पूर्णतः उचित अंतराल ग्राफ़ हैं।

अनुप्रयोग

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

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

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

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

अंतराल पूर्णता और पाथविड्थ

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

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

संदर्भ

• 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.6675, MR 2489816
• Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał (2014), "A subexponential parameterized algorithm for proper interval completion", in Schulz, Andreas S.; Wagner, Dorothea (eds.), Proceedings of the 22nd Annual European Symposium on Algorithms (ESA 2014), Wroclaw, Poland, September 8–10, 2014, Lecture Notes in Computer Science, vol. 8737, Springer-Verlag, pp. 173–184, arXiv:1402.3473, doi:10.1007/978-3-662-44777-2_15, ISBN 978-3-662-44776-5, S2CID 12385294
• Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4, hdl:1874/18312
• Booth, K. S.; Lueker, G. S. (1976), "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms", Journal of Computer and System Sciences, 13 (3): 335–379, doi:10.1016/S0022-0000(76)80045-1
• Brandstädt, A.; Le, V.B.; Spinrad, J.P. (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-432-6
• Cohen, Joel E. (1978), Food webs and niche space, Monographs in Population Biology, vol. 11, Princeton, NJ: Princeton University Press, pp. 1–189, ISBN 978-0-691-08202-8, PMID 683203
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7
• Corneil, Derek; Olariu, Stephan; Stewart, Lorna (2009), "The LBFS structure and recognition of interval graphs", SIAM Journal on Discrete Mathematics, 23 (4): 1905–1953, doi:10.1137/S0895480100373455
• Eckhoff, Jürgen (1993), "Extremal interval graphs", Journal of Graph Theory, 17 (1): 117–127, doi:10.1002/jgt.3190170112
• Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221
• Fishburn, Peter C. (1985), Interval orders and interval graphs: A study of partially ordered sets, Wiley-Interscience Series in Discrete Mathematics, New York: John Wiley & Sons
• Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific Journal of Mathematics, 15 (3): 835–855, doi:10.2140/pjm.1965.15.835
• Gardi, Frédéric (2007), "The Roberts characterization of proper and unit interval graphs", Discrete Mathematics, 307 (22): 2906–2908, doi:10.1016/j.disc.2006.04.043
• Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5
• Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 978-0-12-289260-8
• Golumbic, Martin Charles; Shamir, Ron (1993), "Complexity and algorithms for reasoning about time: a graph-theoretic approach", Journal of the ACM, 40 (5): 1108–1133, CiteSeerX 10.1.1.35.528, doi:10.1145/174147.169675, S2CID 15708027
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing", Theoretical Computer Science, 234 (1–2): 59–84, doi:10.1016/S0304-3975(97)00241-7
• Hsu, Wen-Lian (1992), "A simple test for interval graphs", in Mayr, Ernst W. (ed.), Graph-Theoretic Concepts in Computer Science, 18th International Workshop, WG '92, Wiesbaden-Naurod, Germany, June 19–20, 1992, Proceedings, Lecture Notes in Computer Science, vol. 657, Springer, pp. 11–16, doi:10.1007/3-540-56402-0_31
• Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (2019), "On the classes of interval graphs of limited nesting and count of lengths", Algorithmica, 81 (4): 1490–1511, arXiv:1510.03998, doi:10.1007/s00453-018-0481-y, MR 3936165
• Lekkerkerker, C. G.; Boland, J. C. (1962), "Representation of a finite graph by a set of intervals on the real line", Fundamenta Mathematicae, 51: 45–64, doi:10.4064/fm-51-1-45-64
• McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, ISBN 978-0-89871-430-2
• Proskurowski, Andrzej; Telle, Jan Arne (1999), "Classes of graphs with restricted interval models", Discrete Mathematics & Theoretical Computer Science, 3 (4): 167–176, CiteSeerX 10.1.1.39.9532
• Roberts, F. S. (1969), "Indifference graphs", in Harary, Frank (ed.), Proof Techniques in Graph Theory, New York, NY: Academic Press, pp. 139–146, ISBN 978-0123242600, OCLC 30287853
• Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne (2009), "Interval completion is fixed parameter tractable", SIAM Journal on Computing, 38 (5): 2007–2020, CiteSeerX 10.1.1.73.8999, doi:10.1137/070710913
• Zhang, Peisen; Schon, Eric A.; Fischer, Stuart G.; Cayanis, Eftihia; Weiss, Janie; Kistler, Susan; Bourne, Philip E. (1994), "An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA", Bioinformatics, 10 (3): 309–317, doi:10.1093/bioinformatics/10.3.309, PMID 7922688

बा प्रत्येकी संबंध

• "interval graph", Information System on Graph Classes and their Inclusions
• Weisstein, Eric W., "Interval graph", MathWorld