दूरी-वंशानुगत ग्राफ
ग्राफ सिद्धांत में, असतत गणित की एक शाखा, दूरी-वंशानुगत ग्राफ (जिसे वियोज्य योग्य ग्राफ भी कहा जाता है)[1] है जिसमें किसी भी सम्बद्ध प्रेरित सबग्राफ में दूरियां वैसी ही होती हैं जैसी वे मूल ग्राफ में हैं। इस प्रकार, कोई भी प्रेरित सबग्राफ बड़े ग्राफ की दूरियों को प्रदर्शित करता है।
1977 में सबसे पहले होवरका द्वारा दूरी-वंशानुगत ग्राफ का नामकरण और अध्ययन किया गया, हालांकि ओलारू द्वारा 1970 में ग्राफ के समतुल्य वर्ग को पहले से ही एक परिपूर्ण आलेख के रूप में दिखाया गया था।[2]
यह पहले से ही ज्ञात है कि दूरी-वंशानुगत ग्राफ़, ग्राफ़ के एक प्रतिच्छेदन समूह का गठन करते हैं,[3]लेकिन जब तक जिओन द्वारा प्रतिच्छेदन मॉडल नहीं दिया गया तब तक कोई प्रतिच्छेदन मॉडल ज्ञात नहीं था|
परिभाषा और लक्षण वर्णन
दूरी-वंशानुगत ग्राफ की मूल परिभाषा के अनुसार G एक ऐसा ग्राफ है जिसमें कोई दो शीर्ष u और v, G से जुड़े हुए प्रेरित सबग्राफ H से संबंधित हैं, तो G में u और v को जोड़ने वाला कुछ सबसे छोटा रास्ता, H का सबग्राफ होना चाहिए, ताकि H में u और v के बीच की दूरी, 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]
- वे एचएचडीजी-मुक्त ग्राफ़ हैं, जिसका अर्थ है कि उनके पास एक वर्जित ग्राफ़ विशेषता है जिसके अनुसार कोई प्रेरित सबग्राफ़, एक समूह (पाँच-वर्टेक्स पथ ग्राफ का पूरक ग्राफ), होल (पांच या अधिक वर्टिकल का चक्र ग्राफ), डोमिनोज़ (छह-शीर्ष चक्र और दो विपरीत शीर्षों के बीच एक विकर्ण किनारा), या जेम (पाँच-शीर्ष चक्र और एक ही शीर्ष पर दो विकर्ण घटना) नहीं हो सकता है।
अन्य ग्राफ परिवारों से संबंध
हर दूरी-वंशानुगत ग्राफ एक आदर्श ग्राफ है,[7] अधिक विशेष रूप से एक पूरी तरह से क्रमबद्ध ग्राफ[8] और एक मेनिएल ग्राफ। हर दूरी-वंशानुगत ग्राफ भी एक समता ग्राफ है, जिसमें एक ही जोड़े के बीच हर दो प्रेरित पथों में विषम लंबाई होती है या दोनों की लंबाई सम भी होती है।[9] दूरी-वंशानुगत ग्राफ की प्रत्येक सम ग्राफ शक्ति G (यानी, G में अधिक से अधिक 2i दूरी पर शीर्षों के युग्मों को जोड़कर बनाया गया ग्राफ G2i है) एक कॉर्डल ग्राफ है।[10]
प्रत्येक दूरी-वंशानुगत ग्राफ को एक वृत्त पर जीवाओं के प्रतिच्छेदन ग्राफ के रूप में दर्शाया जा सकता है, जिससे एक वृत्त ग्राफ बनता है। इसे ग्राफ़ का प्रतिनिधित्व करने वाले तारों के एक समान सेट के निर्माण के प्रत्येक चरण में पेन्डन्ट शिखर, फाल्स-ट्विन्स और ट्रू- ट्विन्स को जोड़कर ग्राफ का निर्माण करके देखा जा सकता है। एक पेन्डन्ट शिखर जोड़ना एक मौजूदा कॉर्ड के समापन बिंदुओं के पास एक कॉर्ड जोड़ने के अनुरूप है ताकि यह केवल उस कॉर्ड को पार करे; फाल्स-ट्विन्स जोड़ना एक कॉर्ड को दो समानांतर कॉर्ड द्वारा बदलने के समान है जो अन्य कॉर्ड के एक ही सेट को पार करते हैं; और ट्रू- ट्विन्स जोड़ना एक कॉर्ड को दो जीवाओं से बदलने के अनुरूप है जो एक दूसरे को पार करते हैं लेकिन लगभग समानांतर हैं और अन्य कॉर्ड के एक ही सेट को पार करते हैं।
दूरी-वंशानुगत ग्राफ द्विदलीय ग्राफ है अगर और केवल अगर यह त्रिभुज-मुक्त ग्राफ है। द्विदलीय दूरी-वंशानुगत ग्राफ केवल पेन्डन्ट के शीर्षों और फाल्स-ट्विन्स को जोड़कर एक शीर्ष से बनाया जा सकता है, क्योंकि कोई भी ट्रू- ट्विन्स एक त्रिकोण का निर्माण करेगा, लेकिन पेन्डन्ट शीर्ष और फाल्स-ट्विन्स संचालन द्विदलीयता को संरक्षित करते हैं। प्रत्येक द्विदलीय दूरी-वंशानुगत ग्राफ तारकीय द्विदलीय ग्राफ और मॉड्यूलर ग्राफ है।[11]
ग्राफ़ जो किसी भी फाल्स-ट्विन्स संचालन के बिना, पेन्डन्ट के कोने और ट्रू- ट्विन्स द्वारा एकल शीर्ष से बनाए जा सकते हैं, टॉलेमिक ग्राफ़ के विशेष मामले हैं और इसमें ब्लॉक ग्राफ शामिल हैं। किसी भी पेन्डन्ट वाले कोने के बिना फाल्स-ट्विन्स और ट्रू- ट्विन्स संचालन द्वारा एकल शीर्ष से बनाए जा सकने वाले कोग्राफ हैं, जो इसी कारण दूरी-वंशानुगत हैं; कोग्राफ वास्तव में व्यास-2 दूरी-वंशानुगत ग्राफ के अलग-अलग संघ हैं। दूरी-वंशानुगत ग्राफ में किसी शीर्ष का पड़ोस (ग्राफ सिद्धांत) एक कोग्राफ है। किसी भी ट्री के किनारों (ग्राफ सिद्धांत) के लिए अभिविन्यास के किसी भी सेट को चुनकर गठित निर्देशित ग्राफ का सकर्मक समापन दूरी-वंशानुगत है; विशेष मामला जिसमें ट्री किसी शीर्ष से लगातार दूर उन्मुख होता है, दूरी-वंशानुगत ग्राफ़ का एक उपवर्ग बनाता है, जिसे तुच्छ रूप से परिपूर्ण ग्राफ़ के रूप में जाना जाता है, जिसे कॉर्डल कोग्राफ भी कहा जाता है।[12]
एल्गोरिदम
दूरी-वंशानुगत ग्राफ को पहचाना जा सकता है और रैखिक समय में पेन्डन्ट शीर्ष और जुड़वां संचालन के अनुक्रम में परिभाषित किया जा सकता है।[13]
दूरी-वंशानुगत ग्राफ़ एक परिपूर्ण ग्राफ़ हैं, अतः ग्राफ़ के अधिक सामान्य वर्गों के लिए एनपी-हार्ड होने के बावजूद कुछ अनुकूलन समस्याओं को उनके लिए बहुपद समय में हल किया जा सकता है। इस प्रकार, बहुपद समय में दूरी-वंशानुगत ग्राफ में अधिकतम क्लीक्वेस या अधिकतम स्वतंत्र सेट को खोजना संभव है, या किसी भी दूरी-वंशानुगत ग्राफ का एक इष्टतम ग्राफ कलॉरिंग खोजने के लिए संभव है।[14]क्योंकि दूरी-वंशानुगत ग्राफ़ वृत्त ग्राफ़ हैं, वे वृत्त ग्राफ़ के लिए बहुपद समय एल्गोरिदम को स्वाभाविक रूप से प्राप्त करते हैं; उदाहरण के लिए, बहुपद समय में किसी भी वृत्त ग्राफ की ट्रीविड्थ का निर्धारण संभव है और इसलिए किसी और भी दूरी-वंशानुगत ग्राफ के लिए भी।[15]इसके अतिरिक्त, किसी भी दूरी-वंशानुगत ग्राफ की क्लिक-विड्थ अधिक से अधिक तीन होती है।[16] नतीजतन, कौरसेल के प्रमेय द्वारा, इन ग्राफ़ पर कई समस्याओं के लिए कुशल गतिशील प्रोग्रामिंग एल्गोरिदम मौजूद हैं।[17]
विशेष रूप से दूरी-वंशानुगत ग्राफ के लिए डिज़ाइन किए गए एल्गोरिदम का उपयोग करके कई अन्य अनुकूलन समस्याओं को भी अधिक कुशलता से हल किया जा सकता है। जैसा डी'आत्री और मस्कारिणी (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.
