ट्री-डेप्थ

This article is about एक ग्राफ़ का अपरिवर्तनीय. For एक अमूर्त ट्री में मूल से दूरी, see ट्री (डेटा संरचना) § टर्मिनोलॉजी.

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

परिभाषाएँ

ग्राफ़ की ट्री-डेप्थ $G$ इसे फॉरिस्ट की न्यूनतम ऊंचाई के रूप में परिभाषित किया जा सकता है (ग्राफ सिद्धांत) $F$ उस विशेशता के साथ जो हर किनारे पर है $G$ नोड्स की एक जोड़ी को जोड़ता है जिनका एक दूसरे से पूर्वज-वंशज संबंध होता है $F$. अगर $G$ जुड़ा हुआ है, यह फॉरिस्ट एक ही ट्री होना चाहिए; इसका उपसमूह होने की आवश्यकता नहीं है $G$, लेकिन अगर ऐसा है, तो यह एक ट्रेमॉक्स ट्री है $G$.

पूर्वज-वंशज जोड़ियों का समूह $F$ एक तुच्छ रूप से परिपूर्ण ग्राफ बनाता है, और की ऊंचाई $F$ इस ग्राफ़ में सबसे बड़े समूह (ग्राफ़ सिद्धांत) का आकार है। इस प्रकार, ट्री-डेप्थ को वैकल्पिक रूप से एक तुच्छ रूप से परिपूर्ण सुपरग्राफ में सबसे बड़े समूह के आकार के रूप में परिभाषित किया जा सकता है $G$, कॉर्डल ग्राफ सुपरग्राफ में सबसे बड़े क्लिक के आकार से एक कम के रूप में ट्रीविड्थ की परिभाषा को प्रतिबिंबित करता है $G$. एक अन्य परिभाषा निम्नलिखित है:

$$\operatorname {td} (G)={\begin{cases}1,&{\text{if }}|G|=1;\\1+\min _{v\in V}\operatorname {td} (G-v),&{\text{if }}G{\text{ is connected and }}|G|>1;\\\max _{i}{\rm {td}}(G_{i}),&{\text{otherwise}};\end{cases}}$$

कहाँ $V$ के शीर्षों का समुच्चय है $G$ और यह $G_{i}$ के जुड़े हुए घटक हैं $G$. यह परिभाषा निर्देशित ग्राफ़ के चक्र रैंक की परिभाषा को प्रतिबिंबित करती है, जो अप्रत्यक्ष कनेक्टिविटी और जुड़े घटकों के स्थान पर मजबूत कनेक्टिविटी और दृढ़ता से जुड़े घटकों का उपयोग करती है।

ट्री-डेप्थ को ग्राफ़ रंग के एक रूप का उपयोग करके भी परिभाषित किया जा सकता है। किसी ग्राफ़ का केन्द्रित रंग उसके शीर्षों का रंग इस गुण के साथ होता है कि प्रत्येक जुड़े प्रेरित सबग्राफ में एक रंग होता है जो बिल्कुल एक बार दिखाई देता है। फिर, ट्री-डेप्थ दिए गए ग्राफ़ के केंद्रित रंग में रंगों की न्यूनतम संख्या है। अगर $F$ ऊंचाई का फॉरिस्ट है $d$ उस विशेशता के साथ जो हर किनारे पर है $G$ पूर्वज और वंशज को जोड़ता है $F$, फिर एक केन्द्रित रंग $G$ का उपयोग करते हुए $d$ प्रत्येक शीर्ष को उसके ट्री की जड़ से उसकी दूरी के आधार पर रंगकर रंग प्राप्त किया जा सकता है $F$. अंत में, कोई इसे कंकड़ खेल के रूप में, या अधिक सटीक रूप से पीछा-चोरी खेल के रूप में परिभाषित कर सकता है। अप्रत्यक्ष ग्राफ पर खेले गए निम्नलिखित खेल पर विचार करें। दो खिलाड़ी हैं, एक डाकू और एक पुलिसकर्मी। डाकू के पास एक कंकड़ है जिसे वह दिए गए ग्राफ के किनारों के साथ घुमा सकता है। पुलिस के पास असीमित संख्या में कंकड़ हैं, लेकिन वह अपने द्वारा उपयोग किए जाने वाले कंकड़ की मात्रा को कम करना चाहती है। ग्राफ़ पर रखे जाने के बाद पुलिस एक कंकड़ को हिला नहीं सकती। खेल इस प्रकार आगे बढ़ता है। डाकू अपना कंकड़ डालता है। पुलिस तब घोषणा करती है कि वह एक नया पुलिस कंकड़ कहाँ रखना चाहती है। इसके बाद डाकू अपने कंकड़ को किनारों के साथ ले जा सकता है, लेकिन कब्जे वाले शीर्षों के माध्यम से नहीं। जब पुलिस खिलाड़ी डाकू कंकड़ के ऊपर एक कंकड़ रखता है तो खेल खत्म हो जाता है। दिए गए ग्राफ़ की ट्री-डेप्थ पुलिस द्वारा जीत की गारंटी के लिए आवश्यक कंकड़ की न्यूनतम संख्या है। एक स्टार (ग्राफ सिद्धांत) के लिए, दो कंकड़ पर्याप्त हैं: रणनीति यह है कि एक कंकड़ को केंद्र के शीर्ष पर रखें, डाकू को एक हाथ पर मजबूर करें, और फिर शेष कंकड़ को डाकू पर रखें। पथ ग्राफ़ के लिए $n$ शीर्ष पर, पुलिस एक द्विआधारी खोज रणनीति का उपयोग करती है, जो अधिकतम इसकी गारंटी देती है $\lceil \log _{2}(n+1)\rceil$ कंकड़ की जरूरत है.

उदाहरण

संपूर्ण ग्राफ़ की ट्री-डेप्थ $K_{4}$ और संपूर्ण द्विदलीय ग्राफ़ $K_{3,3}$ दोनों चार हैं, जबकि पथ ग्राफ़ की ट्री-डेप्थ $P_{7}$ तीन है.

एक पूर्ण ग्राफ़ की ट्री-डेप्थ उसके शीर्षों की संख्या के बराबर होती है। क्योंकि, इस मामले में, यह एकमात्र संभावित फॉरिस्ट है $F$ जिसके लिए शीर्षों का प्रत्येक जोड़ा पूर्वज-वंशज संबंध में एक ही पथ है। इसी प्रकार, एक पूर्ण द्विदलीय ग्राफ की ट्री-डेप्थ $K_{x,y}$ है $\min(x,y)+1$. क्योंकि, वे गांठें जो फॉरिस्ट की पत्तियों पर रखी जाती हैं $F$ कम से कम होना ही चाहिए $\min(x,y)$ पूर्वजों में $F$. इसे हासिल करने वाला एक फॉरिस्ट $\min(x,y)+1$ बाउंड का निर्माण द्विविभाजन के छोटे पक्ष के लिए एक पथ बनाकर किया जा सकता है, जिसमें द्विविभाजन के बड़े पक्ष पर प्रत्येक शीर्ष पर एक पत्ती बनती है $F$ इस पथ के निचले शीर्ष से जुड़ा हुआ है।

पथ की ट्री-डेप्थ $n$ शिखर बिल्कुल सही है $\lceil \log _{2}(n+1)\rceil$. एक फॉरिस्ट $F$ इस गहराई के साथ इस पथ का प्रतिनिधित्व पथ के मध्यबिंदु को मूल के रूप में रखकर बनाया जा सकता है $F$ और इसके दोनों ओर दो छोटे पथों के भीतर पुनरावृत्ति करना।

ट्री आयाम और ट्री की चौड़ाई से संबंध

कोई $n$-वर्टेक्स ट्री (ग्राफ सिद्धांत) में ट्री-गहराई है $O(\log n)$. क्योंकि, एक फॉरिस्ट में, कोई भी हमेशा शिखरों की एक स्थिर संख्या पा सकता है, जिसके हटने पर एक फॉरिस्ट बनता है जिसे अधिकतम दो छोटे उपवनों में विभाजित किया जा सकता है। $2n/3$ प्रत्येक शीर्ष. इन दोनों उपवनों में से प्रत्येक को पुनरावर्ती रूप से विभाजित करके, कोई आसानी से ट्री की गहराई पर एक लघुगणकीय ऊपरी सीमा प्राप्त कर सकता है। ग्राफ़ के ट्री अपघटन पर लागू की गई वही तकनीक दर्शाती है कि, यदि किसी ग्राफ़ की ट्री चौड़ाई $n$-वर्टेक्स ग्राफ $G$ है $t$, फिर ट्री-डेप्थ की $G$ है $O(t\log n)$. चूंकि बाह्यतलीय ग्राफ, श्रृंखला-समानांतर ग्राफ़ और हालीन ग्राफ ़ सभी में सीमित ट्री-चौड़ाई होती है, इसलिए उन सभी में अधिकतम लघुगणकीय ट्री-डेप्थ भी होती है। बड़ी ट्रीडेप्थ और छोटी ट्रीविड्थ वाले विशिष्ट ग्राफ़ उत्तम बाइनरी ट्री और पथ हैं। वस्तुतः, एक स्थिरांक है $C$ निम्नलिखित विशेशता के साथ: यदि किसी ग्राफ़ में कम से कम ट्रीडेप्थ है $Ck^{5}\log ^{2}k$ और ट्रीचौड़ाई से कम $k$ तो इसमें ऊंचाई के साथ एक आदर्श बाइनरी ट्री होता है $k$ या लंबाई का पथ $2^{k}$ एक नाबालिग के रूप में. दूसरी दिशा में, किसी ग्राफ़ की ट्री-चौड़ाई उसकी ट्री-डेप्थ के बराबर होती है। अधिक सटीक रूप से, ट्री-चौड़ाई अधिकतम पथ-चौड़ाई है, जो ट्री-डेप्थ से अधिकतम एक कम है।

ग्राफ अवयस्क

ग्राफ़ का एक लघु (ग्राफ़ सिद्धांत)। $G$ के सबग्राफ से बना एक और ग्राफ है $G$ इसके कुछ किनारों को सिकोड़कर। ट्री-डेप्थ माइनर्स के तहत मोनोटोनिक है: ग्राफ़ का प्रत्येक माइनर $G$ ट्री-डेप्थ अधिकतम ट्री-डेप्थ के बराबर होती है $G$ अपने आप। इस प्रकार, रॉबर्टसन-सेमुर प्रमेय द्वारा, प्रत्येक निश्चित के लिए $d$ अधिकतम ट्री-डेप्थ वाले ग्राफ़ का सेट $d$ इसमें निषिद्ध ग्राफ़ लक्षण वर्णन का एक सीमित सेट है।

अगर ${\mathcal {F}}$ ग्राफ़ का एक वर्ग है जिसे ग्राफ़ नाबालिगों, फिर ग्राफ़ों को लेने के अंतर्गत बंद किया जाता है ${\mathcal {F}}$ ट्री-डेप्थ है $O(1)$ अगर और केवल अगर ${\mathcal {F}}$ इसमें सभी पथ ग्राफ़ सम्मिलित नहीं हैं. अधिक सटीक रूप से, एक स्थिरांक है $c$ ऐसा कि ट्री की गहराई का हर ग्राफ़ कम से कम $k^{c}$ निम्नलिखित माइनरों में से एक सम्मिलित है (प्रत्येक ट्रीडेप्थ कम से कम $k$):

• द $k\times k$ जाल,
• ऊंचाई का पूरा बाइनरी ट्री $k$,
• व्यवस्था का मार्ग $2^{k}$.

प्रेरित उपग्राफ

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

अच्छी तरह से अर्ध-क्रम का तात्पर्य है कि ग्राफ़ की कोई भी विशेशता जो प्रेरित सबग्राफ के संबंध में मोनोटोनिक है, उसमें सीमित रूप से कई निषिद्ध प्रेरित सबग्राफ हैं, और इसलिए बंधे हुए ट्री-डेप्थ के ग्राफ़ पर बहुपद समय में परीक्षण किया जा सकता है। अधिकतम ट्री-डेप्थ वाले ग्राफ़ $d$ स्वयं के पास भी निषिद्ध प्रेरित उपसमूहों का एक सीमित सेट है। अगर ${\mathcal {F}}$ सीमाबद्ध अध:पतन (ग्राफ़ सिद्धांत) वाले ग्राफ़ का एक वर्ग है, इसमें ग्राफ़ ${\mathcal {F}}$ ट्री-डेप्थ को सीमित किया गया है यदि और केवल यदि कोई पथ ग्राफ है जो ग्राफ के प्रेरित उपग्राफ के रूप में नहीं हो सकता है ${\mathcal {F}}$.

जटिलता

ट्री-डेप्थ की गणना करना कम्प्यूटेशनल रूप से कठिन है: संबंधित निर्णय समस्या एनपी-पूर्ण है। द्विदलीय ग्राफ के लिए समस्या एनपी-पूर्ण बनी हुई है (Bodlaender et al. 1998), साथ ही कॉर्डल ग्राफ़ के लिए भी है।

धनात्मक भाग पर, ट्री-डेप्थ की गणना अंतराल ग्राफ़ पर बहुपद समय में की जा सकती है, साथ ही क्रमपरिवर्तन, समलम्बाकार, वृत्ताकार-चाप, वृत्ताकार क्रमपरिवर्तन ग्राफ़ और परिबद्ध आयाम के सह तुलनीयता ग्राफ़ पर भी है। अप्रत्यक्ष ट्री के लिए, ट्री की गहराई की गणना रैखिक समय में की जा सकती है।

Bodlaender et al. (1995) सन्निकटन अनुपात के साथ ट्री-डेप्थ के लिए एक सन्निकटन एल्गोरिदम दें $O((\log n)^{2})$, इस तथ्य पर आधारित है कि ट्री-डेप्थ हमेशा एक ग्राफ़ की ट्री-चौड़ाई के लघुगणकीय कारक के भीतर होती है।

क्योंकि ग्राफ माइनर के तहत ट्री-डेप्थ मोनोटोनिक है, यह पैरामीटरयुक्त जटिलता है | फिक्स्ड-पैरामीटर ट्रैक्टेबल: समय में चलने वाले ट्री-डेप्थ की गणना के लिए एल्गोरिदम है $f(d)n^{O(1)}$, जहाँ $d$ दिए गए ग्राफ़ की गहराई है और $n$ इसके शीर्षों की संख्या है। इस प्रकार, प्रत्येक निश्चित मान के लिए $d$, यह परीक्षण करने की समस्या कि ट्री-डेप्थ अधिकतम है या नहीं $d$ बहुपद समय में हल किया जा सकता है। अधिक विशेष रूप से, पर निर्भरता $n$ इस एल्गोरिथ्म को निम्नलिखित विधि द्वारा रैखिक बनाया जा सकता है: पहले खोज ट्री की गहराई की गणना करें, और परीक्षण करें कि क्या ट्री-डेप्थ $2^{d}$ से अधिक है। यदि ऐसा है, तो ग्राफ़ की ट्री-डेप्थ इससे अधिक है $d$ और समस्या हल हो गई है। यदि नहीं, तो उथली गहराई वाले पहले खोज ट्री का उपयोग बंधी हुई चौड़ाई के साथ ट्री अपघटन के निर्माण के लिए किया जा सकता है, और बंधी हुई ट्री चौड़ाई के ग्राफ़ के लिए मानक गतिशील प्रोग्रामिंग तकनीकों का उपयोग रैखिक समय में गहराई की गणना करने के लिए किया जा सकता है।

यह भी संभव है कि, उन ग्राफ़ों के लिए ट्री-डेप्थ की सटीक गणना करना भी संभव है जिनकी ट्री-डेप्थ बड़ी हो सकती है, एक स्थिरांक $O(c^{n})$ के लिए $c$ 2 थोड़ा छोटा है।

संदर्भ

• Aspvall, Bengt; Heggernes, Pinar (1994), "Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time", BIT, 34 (4): 484–509, doi:10.1007/BF01934264, S2CID 16141974.
• Bodlaender, Hans L.; Deogun, Jitender S.; Jansen, Klaus; Kloks, Ton; Kratsch, Dieter; Müller, Haiko; Tuza, Zsolt (1998), "Rankings of graphs" (PDF), SIAM Journal on Discrete Mathematics, 11 (1): 168–181, doi:10.1137/S0895480195282550
• Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1995), "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms, 18 (2): 238–255, CiteSeerX 10.1.1.29.7198, doi:10.1006/jagm.1995.1009.
• Deogun, Jitender S.; Kloks, Ton; Kratsch, Dieter; Müller, Haiko (1999), "On the vertex ranking problem for trapezoid, circular-arc and other graphs", Discrete Applied Mathematics, 98 (1–2): 39–63, doi:10.1016/S0166-218X(99)00179-1.
• Dereniowski, D.; Nadolski, A. (2006), "Vertex rankings of chordal graphs and weighted trees", Information Processing Letters, 98 (3): 96–100, doi:10.1016/j.ipl.2005.12.006.
• Fomin, Fedor V.; Giannopoulou, Archontia C.; Pilipczuk, Michał (2013), "Computing tree-depth faster than 2ⁿ", in Gutin, Gregory; Szeider, Stefan (eds.), Parameterized and Exact Computation: 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8246, pp. 137–149, arXiv:1306.3857, doi:10.1007/978-3-319-03898-8_13.
• Gruber, Hermann; Holzer, Markus (2008), "Finite automata, digraph connectivity, and regular expression size" (PDF), Proc. 35th International Colloquium on Automata, Languages and Programming, Lecture Notes on Computer Science, vol. 5126, Springer-Verlag, pp. 39–50, doi:10.1007/978-3-540-70583-3_4.
• Hunter, Paul (2011), "LIFO-Search on Digraphs: A Searching Game for Cycle-Rank", 18th International Symposium on Fundamentals of Computation Theory, Lecture Notes on Computer Science, vol. 6914, Springer-Verlag, pp. 217–228, arXiv:1103.6019, doi:10.1007/978-3-642-22953-4_19, S2CID 14278138
• Iyer, Ananth V.; Ratliff, H. Donald; Vijayan, Gopalakrishnan (1988), "Optimal node ranking of trees", Information Processing Letters, 28 (5): 225–229, doi:10.1016/0020-0190(88)90194-9.
• Kawarabayashi, Ken-ichi; Rossman, Benjamin (2018), "A Polynomial Excluded-Minor Approximation of Treedepth", Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 234–246, doi:10.1137/1.9781611975031.17.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Chapter 6. Bounded height trees and tree-depth", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, pp. 115–144, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
• Pothen, Alex (1988), The complexity of optimal elimination trees, Tech. Report CS-88-13, Pennsylvania State University.
• Reidl, Felix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath (2014), "A faster parameterized algorithm for treedepth", in Esparza, Javier; Fraigniaud, Pierre; Husfeldt, Thore; et al. (eds.), Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8–11, 2014, Proceedings, Part I, Lecture Notes in Computer Science, vol. 8572, pp. 931–942, arXiv:1401.7540, doi:10.1007/978-3-662-43948-7_77, S2CID 7235055.
• Rossman, Benjamin (2008), "Homomorphism preservation theorems", Journal of the ACM, 55 (3): Article 15, doi:10.1145/1379759.1379763, S2CID 306577.
• Schäffer, Alejandro A. (1989), "Optimal node ranking of trees in linear time", Information Processing Letters, 33 (2): 91–96, doi:10.1016/0020-0190(89)90161-0.