ट्री-डेप्थ

This article is about an invariant of graphs. For the distance from the root in an abstract tree, see Tree (data structure) § Terminology.

ग्राफ़ सिद्धांत में, किसी जुड़े हुए ग्राफ़ की वृक्ष-गहराई अप्रत्यक्ष ग्राफ़ होती है $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.