अंतराल ग्राफ

Not to be confused with D-interval hypergraph.

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

ग्राफ सिद्धांत में, एक अंतराल ग्राफ वास्तविक रेखा पर अंतराल (गणित) के एक सेट से बना एक अप्रत्यक्ष ग्राफ है,

प्रत्येक अंतराल के लिए एक शीर्ष और उन शीर्षों के बीच एक किनारे के साथ जिनके अंतराल प्रतिच्छेद करते हैं। यह अंतरालों का प्रतिच्छेदन ग्राफ है।

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

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

परिभाषा

एक अंतराल ग्राफ एक अप्रत्यक्ष ग्राफ है G अंतराल के एक परिवार से गठित

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

एक शीर्ष बनाकर v_i प्रत्येक अंतराल के लिए S_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$ जो वर्टेक्स समावेशन के संबंध में लगातार है। इस समस्या के लिए कई ज्ञात एल्गोरिदम इस तरह से काम करते हैं, हालांकि उनके क्लिक्स का उपयोग किए बिना रैखिक समय में अंतराल ग्राफ को पहचानना भी संभव है।

का मूल रेखीय समय पहचान एल्गोरिथम Booth & Lueker (1976) उनकी जटिल PQ ट्री डेटा संरचना पर आधारित है, लेकिन Habib et al. (2000) ने दिखाया कि लेक्सिकोग्राफिक चौड़ाई-पहली खोज का उपयोग करके समस्या को और अधिक सरलता से कैसे हल किया जाए, इस तथ्य के आधार पर कि एक ग्राफ एक अंतराल ग्राफ है अगर और केवल अगर यह कॉर्डल ग्राफ है और इसका पूरक (ग्राफ सिद्धांत) एक तुलनात्मक ग्राफ है। 6-स्वीप LexBFS एल्गोरिथम का उपयोग करते हुए एक समान दृष्टिकोण में वर्णित है Corneil, Olariu & Stewart (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