दूरी-वंशानुगत ग्राफ
ग्राफ सिद्धांत में, असतत गणित की एक शाखा, एक दूरी-वंशानुगत ग्राफ (जिसे पूरी तरह से अलग करने योग्य ग्राफ भी कहा जाता है)[1] एक ग्राफ है जिसमें किसी भी जुड़े ग्राफ प्रेरित सबग्राफ में दूरियां वैसी ही होती हैं जैसी वे मूल ग्राफ में होती हैं। इस प्रकार, कोई भी प्रेरित सबग्राफ बड़े ग्राफ की दूरियों को प्राप्त करता है।
दूरी-वंशानुगत रेखांकन का नाम दिया गया और सबसे पहले किसके द्वारा अध्ययन किया गया Howorka (1977), हालांकि ओलारू और सैक्स द्वारा 1970 में रेखांकन के समतुल्य वर्ग को पहले से ही पूर्ण आलेख के रूप में दिखाया गया था।[2] यह कुछ समय के लिए जाना जाता है कि दूरी-वंशानुगत ग्राफ़ ग्राफ़ के एक प्रतिच्छेदन वर्ग का गठन करते हैं,[3] लेकिन कोई चौराहा मॉडल तब तक ज्ञात नहीं था जब तक कि एक द्वारा नहीं दिया गया था Gioan & Paul (2012).
परिभाषा और लक्षण वर्णन
दूरी-वंशानुगत ग्राफ की मूल परिभाषा एक ग्राफ है G जैसे कि, यदि कोई दो शीर्ष u और v एक जुड़े हुए प्रेरित सबग्राफ से संबंधित हैं H का G, फिर कुछ सबसे छोटा रास्ता कनेक्ट कर रहा है u और v में G का सबग्राफ होना चाहिए H, ताकि बीच की दूरी u और v में H में दूरी के समान है G.
दूरी-वंशानुगत रेखांकन को कई अन्य समकक्ष तरीकों से भी वर्णित किया जा सकता है:[4]
- वे ऐसे ग्राफ़ हैं जिनमें प्रत्येक प्रेरित पथ सबसे छोटा पथ है, या समतुल्य रूप से वे ग्राफ़ हैं जिनमें प्रत्येक गैर-लघु पथ में कम से कम एक किनारा है जो दो गैर-लगातार पथ शीर्षों को जोड़ता है।
- वे ऐसे ग्राफ़ हैं जिनमें पाँच या अधिक लंबाई के प्रत्येक चक्र में कम से कम दो क्रॉसिंग विकर्ण होते हैं।
- वे ऐसे ग्राफ़ हैं जिनमें प्रत्येक चार शीर्षों के लिए u, v, w, और x, दूरियों के तीन योगों में से कम से कम दो d(u, v) + d(w, x), d(u, w) + d(v, x), और d(u, x) + d(v, w) एक दूसरे के बराबर हैं।
- वे ऐसे ग्राफ़ हैं जिनमें आइसोमेट्रिक सबग्राफ के रूप में पाँच या अधिक लंबाई का कोई भी चक्र या तीन अन्य ग्राफ़ नहीं होते हैं: एक 5-चक्र एक राग के साथ, 5-चक्र दो गैर-क्रॉसिंग जीवाओं के साथ, और एक 6- विपरीत शीर्षों को जोड़ने वाली जीवा के साथ चक्र।
*वे ऐसे ग्राफ़ हैं जिन्हें निम्नलिखित तीन संक्रियाओं के अनुक्रम द्वारा एकल शीर्ष से निर्मित किया जा सकता है, जैसा कि चित्र में दिखाया गया है:
- # ग्राफ़ के मौजूदा शीर्ष पर एक किनारे से जुड़ा एक नया लटकन शीर्ष जोड़ें।
- ग्राफ़ के किसी भी शीर्ष को शीर्षों की एक जोड़ी से बदलें, जिनमें से प्रत्येक में पड़ोसियों का एक ही सेट प्रतिस्थापित शीर्ष के रूप में हो। शीर्षों के नए युग्म को एक दूसरे के मिथ्या जुड़वाँ कहा जाता है।
- ग्राफ के किसी भी शीर्ष को शीर्षों की एक जोड़ी से बदलें, जिनमें से प्रत्येक के पड़ोसी के रूप में जोड़ी के दूसरे शीर्ष के साथ प्रतिस्थापित शीर्ष के पड़ोसी हैं। वर्टिकल के नए जोड़े को एक दूसरे के ट्रू ट्विन्स कहा जाता है।
- वे ग्राफ़ हैं जिन्हें पूरी तरह से क्लिक (ग्राफ़ सिद्धांत) और सितारों (पूर्ण द्विदलीय ग्राफ़) में विघटित किया जा सकता है K1,q) एक विभाजित अपघटन द्वारा। इस अपघटन में, ग्राफ के विभाजन को दो उपसमुच्चयों में पाया जाता है, जैसे कि दो उपसमुच्चयों को अलग करने वाले किनारे एक पूर्ण द्विदलीय ग्राफ बनाते हैं, विभाजन के दो पक्षों में से प्रत्येक को एक शीर्ष से बदलकर दो छोटे ग्राफ़ बनाते हैं, और पुनरावर्ती रूप से इन दो उप-अनुच्छेदों का विभाजन।[5]
- वे ऐसे ग्राफ़ होते हैं जिनकी रैंक-चौड़ाई एक होती है, जहाँ ग्राफ़ की रैंक-चौड़ाई न्यूनतम के रूप में परिभाषित की जाती है, ग्राफ़ के कोने के सभी पदानुक्रमित विभाजनों में, ग्राफ़ के आसन्न मैट्रिक्स के कुछ सबमैट्रिसेस के बीच अधिकतम रैंक निर्धारित की जाती है विभाजन द्वारा।[6]
- वे HHDG-मुक्त ग्राफ़ हैं, जिसका अर्थ है कि उनके पास एक वर्जित ग्राफ़ विशेषता है जिसके अनुसार कोई प्रेरित सबग्राफ़ एक घर नहीं हो सकता है (पाँच-वर्टेक्स पथ ग्राफ़ का पूरक ग्राफ़), होल (पांच या अधिक वर्टिकल का चक्र ग्राफ़) ), डोमिनोज़ (छह-शीर्ष चक्र और दो विपरीत शीर्षों के बीच एक विकर्ण किनारा), या मणि (पाँच-शीर्ष चक्र और एक ही शीर्ष पर दो विकर्ण घटना)।
अन्य ग्राफ परिवारों से संबंध
हर दूरी-वंशानुगत ग्राफ एक आदर्श ग्राफ है,[7] अधिक विशेष रूप से एक पूरी तरह से क्रमबद्ध ग्राफ[8] और एक Meyniel ग्राफ। हर दूरी-वंशानुगत ग्राफ भी एक समता ग्राफ है, एक ग्राफ जिसमें एक ही जोड़े के बीच हर दो प्रेरित पथों में विषम लंबाई होती है या दोनों की लंबाई भी होती है।[9] दूरी-वंशानुगत ग्राफ की प्रत्येक सम ग्राफ शक्ति G (यानी, ग्राफ G2i अधिक से अधिक दूरी पर शीर्षों के युग्मों को जोड़कर बनाया गया है 2i में G) एक कॉर्डल ग्राफ है।[10] प्रत्येक दूरी-वंशानुगत ग्राफ को एक वृत्त पर जीवाओं के प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है, जिससे एक वृत्त ग्राफ बनता है। इसे ग्राफ़ का प्रतिनिधित्व करने वाले तारों के एक समान सेट के निर्माण के प्रत्येक चरण में लटकन शिखर, झूठे जुड़वाँ और सच्चे जुड़वाओं को जोड़कर ग्राफ का निर्माण करके देखा जा सकता है। एक पेंडेंट वर्टेक्स जोड़ना एक मौजूदा कॉर्ड के समापन बिंदुओं के पास एक कॉर्ड जोड़ने के अनुरूप है ताकि यह केवल उस कॉर्ड को पार करे; झूठे जुड़वाँ जोड़ना एक राग को दो समानांतर जीवाओं द्वारा बदलने के समान है जो अन्य जीवाओं के एक ही सेट को पार करते हैं; और सच्चे जुड़वाँ जोड़ना एक राग को दो जीवाओं से बदलने के अनुरूप है जो एक दूसरे को पार करते हैं लेकिन लगभग समानांतर हैं और अन्य जीवाओं के एक ही सेट को पार करते हैं।
एक दूरी-वंशानुगत ग्राफ द्विदलीय ग्राफ है अगर और केवल अगर यह त्रिभुज-मुक्त ग्राफ है। त्रिभुज-मुक्त। द्विदलीय दूरी-वंशानुगत ग्राफ केवल लटकन के शीर्षों और झूठे जुड़वाँ को जोड़कर एक शीर्ष से बनाया जा सकता है, क्योंकि कोई भी सच्चा जुड़वाँ एक त्रिकोण का निर्माण करेगा, लेकिन लटकन शीर्ष और झूठे जुड़वां संचालन द्विदलीयता को संरक्षित करते हैं। प्रत्येक द्विदलीय दूरी-वंशानुगत ग्राफ तारकीय द्विदलीय ग्राफ और मॉड्यूलर ग्राफ है।[11] ग्राफ़ जो किसी भी झूठे जुड़वां संचालन के बिना, लटकन के कोने और सच्चे जुड़वाँ द्वारा एकल शीर्ष से बनाए जा सकते हैं, टॉलेमिक ग्राफ़ के विशेष मामले हैं और इसमें ब्लॉक ग्राफ़ शामिल हैं। किसी भी लटकन वाले कोने के बिना झूठे जुड़वां और सच्चे जुड़वां संचालन द्वारा एक एकल शीर्ष से बनाए जा सकने वाले ग्राफ कोग्राफ हैं, जो इसलिए दूरी-वंशानुगत हैं; कोग्राफ वास्तव में व्यास-2 दूरी-वंशानुगत ग्राफ के अलग-अलग संघ हैं। दूरी-वंशानुगत ग्राफ में किसी शीर्ष का पड़ोस (ग्राफ सिद्धांत) एक कोग्राफ है। किसी भी पेड़ के किनारों (ग्राफ सिद्धांत) के लिए अभिविन्यास के किसी भी सेट को चुनकर गठित निर्देशित ग्राफ का सकर्मक समापन दूरी-वंशानुगत है; विशेष मामला जिसमें पेड़ किसी शीर्ष से लगातार दूर उन्मुख होता है, दूरी-वंशानुगत ग्राफ़ का एक उपवर्ग बनाता है, जिसे तुच्छ रूप से परिपूर्ण ग्राफ़ के रूप में जाना जाता है, जिसे कॉर्डल कॉग्राफ भी कहा जाता है।[12]
एल्गोरिदम
दूरी-वंशानुगत ग्राफ को पहचाना जा सकता है, और रैखिक समय में लटकन शीर्ष और जुड़वां संचालन के अनुक्रम में पार्स किया जा सकता है।[13] क्योंकि दूरी-वंशानुगत ग्राफ़ परिपूर्ण हैं, ग्राफ़ के अधिक सामान्य वर्गों के लिए एनपी कठिन होने के बावजूद कुछ अनुकूलन समस्याओं को उनके लिए बहुपद समय में हल किया जा सकता है। इस प्रकार, बहुपद समय में दूरी-वंशानुगत ग्राफ में अधिकतम क्लिक या अधिकतम स्वतंत्र सेट को खोजना संभव है, या किसी भी दूरी-वंशानुगत ग्राफ का एक इष्टतम ग्राफ रंग खोजने के लिए संभव है।[14] क्योंकि दूरी-वंशानुगत ग्राफ़ वृत्त ग्राफ़ हैं, वे वृत्त ग्राफ़ के लिए बहुपद समय एल्गोरिदम को इनहेरिट करते हैं; उदाहरण के लिए, यह बहुपद समय में किसी भी वृत्त ग्राफ की पेड़ की चौड़ाई और इसलिए किसी भी दूरी-वंशानुगत ग्राफ का निर्धारण संभव है।[15] इसके अतिरिक्त, किसी भी दूरी-वंशानुगत ग्राफ की क्लिक-चौड़ाई अधिक से अधिक तीन होती है।[16] नतीजतन, कौरसेल के प्रमेय द्वारा, इन ग्राफ़ पर कई समस्याओं के लिए कुशल गतिशील प्रोग्रामिंग एल्गोरिदम मौजूद हैं।[17] विशेष रूप से दूरी-वंशानुगत ग्राफ के लिए डिज़ाइन किए गए एल्गोरिदम का उपयोग करके कई अन्य अनुकूलन समस्याओं को भी अधिक कुशलता से हल किया जा सकता है। जैसा D'Atri & Moscarini (1988) दिखाएं, दूरी-वंशानुगत ग्राफ पर बहुपद समय में एक न्यूनतम जुड़ा हुआ हावी सेट (या समतुल्य रूप से पत्तियों की अधिकतम संभव संख्या वाला एक फैला हुआ पेड़) पाया जा सकता है। किसी भी दूरी-वंशानुगत ग्राफ का हैमिल्टनियन चक्र या हैमिल्टनियन पथ बहुपद समय में भी पाया जा सकता है।[18]
टिप्पणियाँ
- ↑ Hammer & Maffray (1990).
- ↑ Olaru and Sachs showed the α-perfection of the graphs in which every cycle of length five or more has a pair of crossing diagonals (Sachs 1970, Theorem 5). By Lovász (1972), α-perfection is an equivalent form of definition of perfect graphs.
- ↑ McKee & McMorris (1999)
- ↑ Howorka (1977); Bandelt & Mulder (1986); Hammer & Maffray (1990); Brandstädt, Le & Spinrad (1999), Theorem 10.1.1, p. 147.
- ↑ Gioan & Paul (2012). A closely related decomposition was used for graph drawing by Eppstein, Goodrich & Meng (2006) and (for bipartite distance-hereditary graphs) by Hui, Schaefer & Štefankovič (2004).
- ↑ Oum (2005).
- ↑ Howorka (1977).
- ↑ Brandstädt, Le & Spinrad (1999), pp. 70–71 and 82.
- ↑ Brandstädt, Le & Spinrad (1999), p.45.
- ↑ Brandstädt, Le & Spinrad (1999), Theorem 10.6.14, p.164.
- ↑ Bipartite distance-hereditary graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
- ↑ Cornelsen & Di Stefano (2005).
- ↑ Damiand, Habib & Paul (2001); Gioan & Paul (2012). An earlier linear time bound was claimed by Hammer & Maffray (1990) but it was discovered to be erroneous by Damiand.
- ↑ Cogis & Thierry (2005) present a simple direct algorithm for maximum weighted independent sets in distance-hereditary graphs, based on parsing the graph into pendant vertices and twins, correcting a previous attempt at such an algorithm by Hammer & Maffray (1990). Because distance-hereditary graphs are perfectly orderable, they can be optimally colored in linear time by using LexBFS to find a perfect ordering and then applying a greedy coloring algorithm.
- ↑ Kloks (1996); Brandstädt, Le & Spinrad (1999), p. 170.
- ↑ Golumbic & Rotics (2000).
- ↑ Courcelle, Makowski & Rotics (2000); Espelage, Gurski & Wanke (2001).
- ↑ Hsieh et al. (2002); Müller & Nicolai (1993).
संदर्भ
- Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310.
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
- Cogis, O.; Thierry, E. (2005), "Computing maximum stable sets for distance-hereditary graphs", Discrete Optimization, 2 (2): 185–188, doi:10.1016/j.disopt.2005.03.004, MR 2155518.
- Cornelsen, Sabine; Di Stefano, Gabriele (2005), "Treelike comparability graphs: characterization, recognition, and applications", Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004), Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, pp. 46–57, doi:10.1007/978-3-540-30559-0_4, MR 2158633, S2CID 14166894, ISBN 9783540241324, 9783540305590.
- Courcelle, B.; Makowski, J. A.; Rotics, U. (2000), "Linear time solvable optimization problems on graphs on bounded clique width", Theory of Computing Systems, 33 (2): 125–150, doi:10.1007/s002249910009, S2CID 15402031.
- D'Atri, Alessandro; Moscarini, Marina (1988), "Distance-hereditary graphs, Steiner trees, and connected domination", SIAM Journal on Computing, 17 (3): 521–538, doi:10.1137/0217032, MR 0941943.
- Damiand, Guillaume; Habib, Michel; Paul, Christophe (2001), "A simple paradigm for graph recognition: application to cographs and distance hereditary graphs" (PDF), Theoretical Computer Science, 263 (1–2): 99–111, doi:10.1016/S0304-3975(00)00234-6, MR 1846920.
- Eppstein, David; Goodrich, Michael T.; Meng, Jeremy Yu (2006), "Delta-confluent drawings", in Healy, Patrick; Nikolov, Nikola S. (eds.), Proc. 13th Int. Symp. Graph Drawing (GD 2005), Lecture Notes in Computer Science, vol. 3843, Springer-Verlag, pp. 165–176, arXiv:cs.CG/0510024, doi:10.1007/11618058_16, MR 2244510, S2CID 13478178.
- Espelage, W.; Gurski, F.; Wanke, E. (2001), "How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time", Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001), Lecture Notes in Computer Science, vol. 2204, Springer-Verlag, pp. 117–128.
- Gioan, Emeric; Paul, Christophe (2012), "Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs", Discrete Applied Mathematics, 160 (6): 708–733, arXiv:0810.1823, doi:10.1016/j.dam.2011.05.007, S2CID 6528410.
- Golumbic, Martin Charles; Rotics, Udi (2000), "On the clique-width of some perfect graph classes", International Journal of Foundations of Computer Science, 11 (3): 423–443, doi:10.1142/S0129054100000260, MR 1792124.
- Hammer, Peter Ladislaw; Maffray, Frédéric (1990), "Completely separable graphs", Discrete Applied Mathematics, 27 (1–2): 85–99, doi:10.1016/0166-218X(90)90131-U, MR 1055593.
- Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544.
- Hsieh, Sun-yuan; Ho, Chin-wen; Hsu, Tsan-sheng; Ko, Ming-tat (2002), "Efficient algorithms for the Hamiltonian problem on distance-hereditary graphs", Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2387, Springer-Verlag, pp. 51–75, doi:10.1007/3-540-45655-4_10, ISBN 978-3-540-43996-7, MR 2064504.
- Hui, Peter; Schaefer, Marcus; Štefankovič, Daniel (2004), "Train tracks and confluent drawings", in Pach, János (ed.), Proc. 12th Int. Symp. Graph Drawing (GD 2004), Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 318–328.
- Kloks, T. (1996), "Treewidth of circle graphs", International Journal of Foundations of Computer Science, 7 (2): 111–120, doi:10.1142/S0129054196000099.
- Lovász, László (1972), "Normal hypergraphs and the perfect graph conjecture", Discrete Mathematics, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4, MR 0302480.
- McKee, Terry A.; McMorris, F. R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, vol. 2, Philadelphia: Society for Industrial and Applied Mathematics, doi:10.1137/1.9780898719802, ISBN 0-89871-430-3, MR 1672910
- Müller, Haiko; Nicolai, Falk (1993), "Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs", Information Processing Letters, 46 (5): 225–230, doi:10.1016/0020-0190(93)90100-N, MR 1228792.
- Oum, Sang-il (2005), "Rank-width and vertex-minors", Journal of Combinatorial Theory, Series B, 95 (1): 79–100, doi:10.1016/j.jctb.2005.03.003, MR 2156341.
- Sachs, Horst (1970), "On the Berge conjecture concerning perfect graphs", Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), Gordon and Breach, pp. 377–384, MR 0272668.
