ट्री-डेप्थ: Difference between revisions

From Vigyanwiki
m (Sugatha moved page वृक्ष-गहराई to ट्री-डेप्थ without leaving a redirect)
No edit summary
Line 1: Line 1:
{{Short description|Numerical invariant of graphs}}
{{Short description|Numerical invariant of graphs}}
{{about|an [[graph invariant|invariant of graphs]]|the distance from the root in an abstract tree|Tree (data structure)#Terminology}}
{{about|एक [[ग्राफ़ अपरिवर्तनीय|ग्राफ़ का अपरिवर्तनीय]]|एक अमूर्त ट्री में मूल से दूरी|ट्री (डेटा संरचना) #टर्मिनोलॉजी}}
ग्राफ़ सिद्धांत में, किसी जुड़े हुए ग्राफ़ की वृक्ष-गहराई [[अप्रत्यक्ष ग्राफ]]़ होती है <math>G</math> का एक संख्यात्मक [[ग्राफ़ अपरिवर्तनीय]] है <math>G</math>, ग्राफ़ सिद्धांत#सबग्राफ़ की शब्दावली के लिए ट्रेमॉक्स पेड़ की न्यूनतम ऊंचाई <math>G</math>. इस अपरिवर्तनीय और इसके करीबी रिश्तेदारों को साहित्य में कई अलग-अलग नामों से जाना जाता है, जिसमें शीर्ष रैंकिंग संख्या, क्रमबद्ध रंगीन संख्या और न्यूनतम उन्मूलन वृक्ष की ऊंचाई शामिल है; यह [[निर्देशित ग्राफ]]के [[चक्र रैंक]] और [[नियमित भाषा]]ओं की स्टार ऊंचाई से भी निकटता से संबंधित है।<ref>{{harvtxt|Bodlaender|Deogun|Jansen|Kloks|1998}}; {{harvtxt|Rossman|2008}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 116.</ref> सहज रूप से, जहां एक ग्राफ की [[वृक्ष चौड़ाई]] मापती है कि वह एक पेड़ (ग्राफ सिद्धांत) होने से कितनी दूर है, यह पैरामीटर मापता है कि एक ग्राफ एक [[तारा (ग्राफ सिद्धांत)]] होने से कितनी दूर है।
 
ग्राफ़ सिद्धांत में, किसी जुड़े हुए ग्राफ़ की ट्री-डेप्थ [[अप्रत्यक्ष ग्राफ]] <math>G</math> का एक संख्यात्मक [[ग्राफ़ अपरिवर्तनीय]] है <math>G</math>, ग्राफ़ सिद्धांत की शब्दावली के लिए ट्रेमॉक्स ट्री की न्यूनतम ऊंचाई <math>G</math> है। इस अपरिवर्तनीय और इसके निकट आपेक्षिक को साहित्य में कई अलग-अलग नामों से जाना जाता है, जिसमें शीर्ष रैंकिंग संख्या, क्रमबद्ध रंगीन संख्या और न्यूनतम उन्मूलन ट्री की ऊंचाई सम्मिलित है; यह [[निर्देशित ग्राफ]] के [[चक्र रैंक]] और [[नियमित भाषा]]ओं की स्टार ऊंचाई से भी निकटता से संबंधित है।<ref>{{harvtxt|Bodlaender|Deogun|Jansen|Kloks|1998}}; {{harvtxt|Rossman|2008}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 116.</ref> सहज रूप से, जहां एक ग्राफ की [[वृक्ष चौड़ाई|ट्री चौड़ाई]] मापती है कि वह एक ट्री (ग्राफ सिद्धांत) होने से कितनी दूर है, यह पैरामीटर मापता है कि एक ग्राफ एक [[तारा (ग्राफ सिद्धांत)]] होने से कितनी दूर है।


==परिभाषाएँ==
==परिभाषाएँ==
ग्राफ़ की वृक्ष-गहराई <math>G</math> इसे जंगल की न्यूनतम ऊंचाई के रूप में परिभाषित किया जा सकता है (ग्राफ सिद्धांत) <math>F</math> उस संपत्ति के साथ जो हर किनारे पर है <math>G</math> नोड्स की एक जोड़ी को जोड़ता है जिनका एक दूसरे से पूर्वज-वंशज संबंध होता है <math>F</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Definition 6.1, p. 115.</ref> अगर <math>G</math> जुड़ा हुआ है, यह जंगल एक ही पेड़ होना चाहिए; इसका उपसमूह होने की आवश्यकता नहीं है <math>G</math>, लेकिन अगर ऐसा है, तो यह एक ट्रेमॉक्स पेड़ है <math>G</math>.
ग्राफ़ की ट्री-डेप्थ <math>G</math> इसे फॉरिस्ट की न्यूनतम ऊंचाई के रूप में परिभाषित किया जा सकता है (ग्राफ सिद्धांत) <math>F</math> उस विशेशता के साथ जो हर किनारे पर है <math>G</math> नोड्स की एक जोड़ी को जोड़ता है जिनका एक दूसरे से पूर्वज-वंशज संबंध होता है <math>F</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Definition 6.1, p. 115.</ref> अगर <math>G</math> जुड़ा हुआ है, यह फॉरिस्ट एक ही ट्री होना चाहिए; इसका उपसमूह होने की आवश्यकता नहीं है <math>G</math>, लेकिन अगर ऐसा है, तो यह एक ट्रेमॉक्स ट्री है <math>G</math>.


पूर्वज-वंशज जोड़ियों का समूह <math>F</math> एक तुच्छ रूप से परिपूर्ण ग्राफ बनाता है, और की ऊंचाई <math>F</math> इस ग्राफ़ में सबसे बड़े समूह (ग्राफ़ सिद्धांत) का आकार है। इस प्रकार, वृक्ष-गहराई को वैकल्पिक रूप से एक तुच्छ रूप से परिपूर्ण सुपरग्राफ में सबसे बड़े समूह के आकार के रूप में परिभाषित किया जा सकता है <math>G</math>, [[कॉर्डल ग्राफ]] सुपरग्राफ में सबसे बड़े क्लिक के आकार से एक कम के रूप में ट्रीविड्थ की परिभाषा को प्रतिबिंबित करता है <math>G</math>.<ref><!-- Strangely this seems to be the earliest reference I can find. Nesetril and Ossona de Mendez "On Low Tree-Depth Decompositions" 2014 mention this fact but are unusable as a source because they credit it to Wikipedia. It is also mentioned in two papers from 2013, Bannister et al "Parametrized complexity of 1-planarity" and Fomin et al "Computing tree-depth faster than 2^n". DE 2015-10-06. -->{{citation|first=David |last=Eppstein |author-link=David Eppstein |url=https://11011110.github.io/blog/2012/11/15/graph-parameters-and.html |title=Graph parameters and cliques in supergraphs |date=November 15, 2012 }}.</ref>
पूर्वज-वंशज जोड़ियों का समूह <math>F</math> एक तुच्छ रूप से परिपूर्ण ग्राफ बनाता है, और की ऊंचाई <math>F</math> इस ग्राफ़ में सबसे बड़े समूह (ग्राफ़ सिद्धांत) का आकार है। इस प्रकार, ट्री-डेप्थ को वैकल्पिक रूप से एक तुच्छ रूप से परिपूर्ण सुपरग्राफ में सबसे बड़े समूह के आकार के रूप में परिभाषित किया जा सकता है <math>G</math>, [[कॉर्डल ग्राफ]] सुपरग्राफ में सबसे बड़े क्लिक के आकार से एक कम के रूप में ट्रीविड्थ की परिभाषा को प्रतिबिंबित करता है <math>G</math>.<ref><!-- Strangely this seems to be the earliest reference I can find. Nesetril and Ossona de Mendez "On Low Tree-Depth Decompositions" 2014 mention this fact but are unusable as a source because they credit it to Wikipedia. It is also mentioned in two papers from 2013, Bannister et al "Parametrized complexity of 1-planarity" and Fomin et al "Computing tree-depth faster than 2^n". DE 2015-10-06. -->{{citation|first=David |last=Eppstein |author-link=David Eppstein |url=https://11011110.github.io/blog/2012/11/15/graph-parameters-and.html |title=Graph parameters and cliques in supergraphs |date=November 15, 2012 }}.</ref>
एक अन्य परिभाषा निम्नलिखित है:
एक अन्य परिभाषा निम्नलिखित है:


Line 16: Line 17:
कहाँ <math>V</math> के शीर्षों का समुच्चय है <math>G</math> और यह <math>G_i</math> के जुड़े हुए घटक हैं <math>G</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.1, p. 117.</ref> यह परिभाषा निर्देशित ग्राफ़ के चक्र रैंक की परिभाषा को प्रतिबिंबित करती है, जो अप्रत्यक्ष कनेक्टिविटी और जुड़े घटकों के स्थान पर मजबूत कनेक्टिविटी और दृढ़ता से जुड़े घटकों का उपयोग करती है।
कहाँ <math>V</math> के शीर्षों का समुच्चय है <math>G</math> और यह <math>G_i</math> के जुड़े हुए घटक हैं <math>G</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.1, p. 117.</ref> यह परिभाषा निर्देशित ग्राफ़ के चक्र रैंक की परिभाषा को प्रतिबिंबित करती है, जो अप्रत्यक्ष कनेक्टिविटी और जुड़े घटकों के स्थान पर मजबूत कनेक्टिविटी और दृढ़ता से जुड़े घटकों का उपयोग करती है।


वृक्ष-गहराई को [[ग्राफ़ रंग]] के एक रूप का उपयोग करके भी परिभाषित किया जा सकता है। किसी ग्राफ़ का केन्द्रित रंग उसके शीर्षों का रंग इस गुण के साथ होता है कि प्रत्येक जुड़े [[प्रेरित सबग्राफ]] में एक रंग होता है जो बिल्कुल एक बार दिखाई देता है। फिर, वृक्ष-गहराई दिए गए ग्राफ़ के केंद्रित रंग में रंगों की न्यूनतम संख्या है। अगर <math>F</math> ऊंचाई का जंगल है <math>d</math> उस संपत्ति के साथ जो हर किनारे पर है <math>G</math> पूर्वज और वंशज को जोड़ता है <math>F</math>, फिर एक केन्द्रित रंग <math>G</math> का उपयोग करते हुए <math>d</math> प्रत्येक शीर्ष को उसके पेड़ की जड़ से उसकी दूरी के आधार पर रंगकर रंग प्राप्त किया जा सकता है <math>F</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Section 6.5, "Centered Colorings", pp. 125–128.</ref>
ट्री-डेप्थ को [[ग्राफ़ रंग]] के एक रूप का उपयोग करके भी परिभाषित किया जा सकता है। किसी ग्राफ़ का केन्द्रित रंग उसके शीर्षों का रंग इस गुण के साथ होता है कि प्रत्येक जुड़े [[प्रेरित सबग्राफ]] में एक रंग होता है जो बिल्कुल एक बार दिखाई देता है। फिर, ट्री-डेप्थ दिए गए ग्राफ़ के केंद्रित रंग में रंगों की न्यूनतम संख्या है। अगर <math>F</math> ऊंचाई का फॉरिस्ट है <math>d</math> उस विशेशता के साथ जो हर किनारे पर है <math>G</math> पूर्वज और वंशज को जोड़ता है <math>F</math>, फिर एक केन्द्रित रंग <math>G</math> का उपयोग करते हुए <math>d</math> प्रत्येक शीर्ष को उसके ट्री की जड़ से उसकी दूरी के आधार पर रंगकर रंग प्राप्त किया जा सकता है <math>F</math>.<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Section 6.5, "Centered Colorings", pp. 125–128.</ref>
अंत में, कोई इसे [[कंकड़ खेल]] के रूप में, या अधिक सटीक रूप से [[पीछा-चोरी]] खेल के रूप में परिभाषित कर सकता है। अप्रत्यक्ष ग्राफ पर खेले गए निम्नलिखित खेल पर विचार करें। दो खिलाड़ी हैं, एक डाकू और एक पुलिसकर्मी। डाकू के पास एक कंकड़ है जिसे वह दिए गए ग्राफ के किनारों के साथ घुमा सकता है। पुलिस के पास असीमित संख्या में कंकड़ हैं, लेकिन वह अपने द्वारा उपयोग किए जाने वाले कंकड़ की मात्रा को कम करना चाहती है। ग्राफ़ पर रखे जाने के बाद पुलिस एक कंकड़ को हिला नहीं सकती। खेल इस प्रकार आगे बढ़ता है। डाकू अपना कंकड़ डालता है। पुलिस तब घोषणा करती है कि वह एक नया पुलिस कंकड़ कहाँ रखना चाहती है। इसके बाद डाकू अपने कंकड़ को किनारों के साथ ले जा सकता है, लेकिन कब्जे वाले शीर्षों के माध्यम से नहीं। जब पुलिस खिलाड़ी डाकू कंकड़ के ऊपर एक कंकड़ रखता है तो खेल खत्म हो जाता है। दिए गए ग्राफ़ की वृक्ष-गहराई पुलिस द्वारा जीत की गारंटी के लिए आवश्यक कंकड़ की न्यूनतम संख्या है।<ref>{{harvtxt|Gruber|Holzer|2008}}, Theorem 5, {{harvtxt|Hunter|2011}}, Main Theorem.</ref> एक स्टार (ग्राफ सिद्धांत) के लिए, दो कंकड़ पर्याप्त हैं: रणनीति यह है कि एक कंकड़ को केंद्र के शीर्ष पर रखें, डाकू को एक हाथ पर मजबूर करें, और फिर शेष कंकड़ को डाकू पर रखें। [[पथ ग्राफ]]़ के लिए <math>n</math> शीर्ष पर, पुलिस एक [[द्विआधारी खोज]] रणनीति का उपयोग करती है, जो अधिकतम इसकी गारंटी देती है <math>\lceil\log_2(n+1)\rceil</math> कंकड़ की जरूरत है.
अंत में, कोई इसे [[कंकड़ खेल]] के रूप में, या अधिक सटीक रूप से [[पीछा-चोरी]] खेल के रूप में परिभाषित कर सकता है। अप्रत्यक्ष ग्राफ पर खेले गए निम्नलिखित खेल पर विचार करें। दो खिलाड़ी हैं, एक डाकू और एक पुलिसकर्मी। डाकू के पास एक कंकड़ है जिसे वह दिए गए ग्राफ के किनारों के साथ घुमा सकता है। पुलिस के पास असीमित संख्या में कंकड़ हैं, लेकिन वह अपने द्वारा उपयोग किए जाने वाले कंकड़ की मात्रा को कम करना चाहती है। ग्राफ़ पर रखे जाने के बाद पुलिस एक कंकड़ को हिला नहीं सकती। खेल इस प्रकार आगे बढ़ता है। डाकू अपना कंकड़ डालता है। पुलिस तब घोषणा करती है कि वह एक नया पुलिस कंकड़ कहाँ रखना चाहती है। इसके बाद डाकू अपने कंकड़ को किनारों के साथ ले जा सकता है, लेकिन कब्जे वाले शीर्षों के माध्यम से नहीं। जब पुलिस खिलाड़ी डाकू कंकड़ के ऊपर एक कंकड़ रखता है तो खेल खत्म हो जाता है। दिए गए ग्राफ़ की ट्री-डेप्थ पुलिस द्वारा जीत की गारंटी के लिए आवश्यक कंकड़ की न्यूनतम संख्या है।<ref>{{harvtxt|Gruber|Holzer|2008}}, Theorem 5, {{harvtxt|Hunter|2011}}, Main Theorem.</ref> एक स्टार (ग्राफ सिद्धांत) के लिए, दो कंकड़ पर्याप्त हैं: रणनीति यह है कि एक कंकड़ को केंद्र के शीर्ष पर रखें, डाकू को एक हाथ पर मजबूर करें, और फिर शेष कंकड़ को डाकू पर रखें। [[पथ ग्राफ]]़ के लिए <math>n</math> शीर्ष पर, पुलिस एक [[द्विआधारी खोज]] रणनीति का उपयोग करती है, जो अधिकतम इसकी गारंटी देती है <math>\lceil\log_2(n+1)\rceil</math> कंकड़ की जरूरत है.


==उदाहरण==
==उदाहरण==
[[File:Tree-depth.svg|thumb|upright=1.66|संपूर्ण ग्राफ़ की वृक्ष-गहराई <math>K_4</math> और सं[[पूर्ण द्विदलीय ग्राफ]]़ <math>K_{3,3}</math> दोनों चार हैं, जबकि पथ ग्राफ़ की वृक्ष-गहराई <math>P_7</math> तीन है.]]एक पूर्ण ग्राफ़ की वृक्ष-गहराई उसके शीर्षों की संख्या के बराबर होती है। क्योंकि, इस मामले में, यह एकमात्र संभावित जंगल है <math>F</math> जिसके लिए शीर्षों का प्रत्येक जोड़ा पूर्वज-वंशज संबंध में एक ही पथ है। इसी प्रकार, एक पूर्ण द्विदलीय ग्राफ की वृक्ष-गहराई <math>K_{x,y}</math> है <math>\min(x,y)+1</math>. क्योंकि, वे गांठें जो जंगल की पत्तियों पर रखी जाती हैं <math>F</math> कम से कम होना ही चाहिए <math>\min(x,y)</math> पूर्वजों में <math>F</math>. इसे हासिल करने वाला एक जंगल <math>\min(x,y)+1</math> बाउंड का निर्माण द्विविभाजन के छोटे पक्ष के लिए एक पथ बनाकर किया जा सकता है, जिसमें द्विविभाजन के बड़े पक्ष पर प्रत्येक शीर्ष पर एक पत्ती बनती है <math>F</math> इस पथ के निचले शीर्ष से जुड़ा हुआ है।
[[File:Tree-depth.svg|thumb|upright=1.66|संपूर्ण ग्राफ़ की ट्री-डेप्थ <math>K_4</math> और सं[[पूर्ण द्विदलीय ग्राफ]]़ <math>K_{3,3}</math> दोनों चार हैं, जबकि पथ ग्राफ़ की ट्री-डेप्थ <math>P_7</math> तीन है.]]एक पूर्ण ग्राफ़ की ट्री-डेप्थ उसके शीर्षों की संख्या के बराबर होती है। क्योंकि, इस मामले में, यह एकमात्र संभावित फॉरिस्ट है <math>F</math> जिसके लिए शीर्षों का प्रत्येक जोड़ा पूर्वज-वंशज संबंध में एक ही पथ है। इसी प्रकार, एक पूर्ण द्विदलीय ग्राफ की ट्री-डेप्थ <math>K_{x,y}</math> है <math>\min(x,y)+1</math>. क्योंकि, वे गांठें जो फॉरिस्ट की पत्तियों पर रखी जाती हैं <math>F</math> कम से कम होना ही चाहिए <math>\min(x,y)</math> पूर्वजों में <math>F</math>. इसे हासिल करने वाला एक फॉरिस्ट <math>\min(x,y)+1</math> बाउंड का निर्माण द्विविभाजन के छोटे पक्ष के लिए एक पथ बनाकर किया जा सकता है, जिसमें द्विविभाजन के बड़े पक्ष पर प्रत्येक शीर्ष पर एक पत्ती बनती है <math>F</math> इस पथ के निचले शीर्ष से जुड़ा हुआ है।


पथ की वृक्ष-गहराई <math>n</math> शिखर बिल्कुल सही है <math>\lceil\log_2(n+1)\rceil</math>. एक जंगल <math>F</math> इस गहराई के साथ इस पथ का प्रतिनिधित्व पथ के मध्यबिंदु को मूल के रूप में रखकर बनाया जा सकता है <math>F</math> और इसके दोनों ओर दो छोटे पथों के भीतर पुनरावृत्ति करना।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Formula 6.2, p. 117.</ref>
पथ की ट्री-डेप्थ <math>n</math> शिखर बिल्कुल सही है <math>\lceil\log_2(n+1)\rceil</math>. एक फॉरिस्ट <math>F</math> इस गहराई के साथ इस पथ का प्रतिनिधित्व पथ के मध्यबिंदु को मूल के रूप में रखकर बनाया जा सकता है <math>F</math> और इसके दोनों ओर दो छोटे पथों के भीतर पुनरावृत्ति करना।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Formula 6.2, p. 117.</ref>




==पेड़ों की गहराई और पेड़ों की चौड़ाई से संबंध==
==ट्री आयाम और ट्री की चौड़ाई से संबंध==
कोई <math>n</math>-वर्टेक्स ट्री (ग्राफ सिद्धांत) में ट्री-गहराई है <math>O(\log n)</math>. क्योंकि, एक जंगल में, कोई भी हमेशा शिखरों की एक स्थिर संख्या पा सकता है, जिसके हटने पर एक जंगल बनता है जिसे अधिकतम दो छोटे उपवनों में विभाजित किया जा सकता है। <math>2n/3</math> प्रत्येक शीर्ष. इन दोनों उपवनों में से प्रत्येक को पुनरावर्ती रूप से विभाजित करके, कोई आसानी से पेड़ की गहराई पर एक लघुगणकीय ऊपरी सीमा प्राप्त कर सकता है। ग्राफ़ के वृक्ष अपघटन पर लागू की गई वही तकनीक दर्शाती है कि, यदि किसी ग्राफ़ की वृक्ष चौड़ाई <math>n</math>-वर्टेक्स ग्राफ <math>G</math> है <math>t</math>, फिर वृक्ष-गहराई की <math>G</math> है <math>O(t\log n)</math>.<ref>{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Corollary 6.1, p. 124.</ref> चूंकि [[बाह्यतलीय ग्राफ]], श्रृंखला-समानांतर ग्राफ़ और [[ हालीन ग्राफ ]]़ सभी में सीमित वृक्ष-चौड़ाई होती है, इसलिए उन सभी में अधिकतम लघुगणकीय वृक्ष-गहराई भी होती है। बड़ी ट्रीडेप्थ और छोटी ट्रीविड्थ वाले विशिष्ट ग्राफ़ [[उत्तम बाइनरी ट्री]] और पथ हैं। वस्तुतः, एक स्थिरांक है <math>C</math> निम्नलिखित संपत्ति के साथ: यदि किसी ग्राफ़ में कम से कम ट्रीडेप्थ है <math>C k^5\log^2k</math> और वृक्षचौड़ाई से कम <math>k</math> तो इसमें ऊंचाई के साथ एक आदर्श बाइनरी ट्री होता है <math>k</math> या लंबाई का पथ <math>2^k</math> एक नाबालिग के रूप में.<ref name="kr">{{harvtxt|Kawarabayashi|Rossman|2018}}</ref>
कोई <math>n</math>-वर्टेक्स ट्री (ग्राफ सिद्धांत) में ट्री-गहराई है <math>O(\log n)</math>. क्योंकि, एक फॉरिस्ट में, कोई भी हमेशा शिखरों की एक स्थिर संख्या पा सकता है, जिसके हटने पर एक फॉरिस्ट बनता है जिसे अधिकतम दो छोटे उपवनों में विभाजित किया जा सकता है। <math>2n/3</math> प्रत्येक शीर्ष. इन दोनों उपवनों में से प्रत्येक को पुनरावर्ती रूप से विभाजित करके, कोई आसानी से ट्री की गहराई पर एक लघुगणकीय ऊपरी सीमा प्राप्त कर सकता है। ग्राफ़ के ट्री अपघटन पर लागू की गई वही तकनीक दर्शाती है कि, यदि किसी ग्राफ़ की ट्री चौड़ाई <math>n</math>-वर्टेक्स ग्राफ <math>G</math> है <math>t</math>, फिर ट्री-डेप्थ की <math>G</math> है <math>O(t\log n)</math>.<ref>{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Corollary 6.1, p. 124.</ref> चूंकि [[बाह्यतलीय ग्राफ]], श्रृंखला-समानांतर ग्राफ़ और [[ हालीन ग्राफ ]]़ सभी में सीमित ट्री-चौड़ाई होती है, इसलिए उन सभी में अधिकतम लघुगणकीय ट्री-डेप्थ भी होती है। बड़ी ट्रीडेप्थ और छोटी ट्रीविड्थ वाले विशिष्ट ग्राफ़ [[उत्तम बाइनरी ट्री]] और पथ हैं। वस्तुतः, एक स्थिरांक है <math>C</math> निम्नलिखित विशेशता के साथ: यदि किसी ग्राफ़ में कम से कम ट्रीडेप्थ है <math>C k^5\log^2k</math> और ट्रीचौड़ाई से कम <math>k</math> तो इसमें ऊंचाई के साथ एक आदर्श बाइनरी ट्री होता है <math>k</math> या लंबाई का पथ <math>2^k</math> एक नाबालिग के रूप में.<ref name="kr">{{harvtxt|Kawarabayashi|Rossman|2018}}</ref>
दूसरी दिशा में, किसी ग्राफ़ की वृक्ष-चौड़ाई उसकी वृक्ष-गहराई के बराबर होती है। अधिक सटीक रूप से, वृक्ष-चौड़ाई अधिकतम [[पथ-चौड़ाई]] है, जो वृक्ष-गहराई से अधिकतम एक कम है।<ref>{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 123.</ref>
दूसरी दिशा में, किसी ग्राफ़ की ट्री-चौड़ाई उसकी ट्री-डेप्थ के बराबर होती है। अधिक सटीक रूप से, ट्री-चौड़ाई अधिकतम [[पथ-चौड़ाई]] है, जो ट्री-डेप्थ से अधिकतम एक कम है।<ref>{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}}; {{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 123.</ref>




==ग्राफ अवयस्क==
==ग्राफ अवयस्क==
ग्राफ़ का एक [[लघु (ग्राफ़ सिद्धांत)]]। <math>G</math> के सबग्राफ से बना एक और ग्राफ है <math>G</math> इसके कुछ किनारों को सिकोड़कर। ट्री-डेप्थ माइनर्स के तहत मोनोटोनिक है: ग्राफ़ का प्रत्येक माइनर <math>G</math> वृक्ष-गहराई अधिकतम वृक्ष-गहराई के बराबर होती है <math>G</math> अपने आप।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.2, p. 117.</ref> इस प्रकार, रॉबर्टसन-सेमुर प्रमेय द्वारा, प्रत्येक निश्चित के लिए <math>d</math> अधिकतम वृक्ष-गहराई वाले ग्राफ़ का सेट <math>d</math> इसमें निषिद्ध ग्राफ़ लक्षण वर्णन का एक सीमित सेट है।
ग्राफ़ का एक [[लघु (ग्राफ़ सिद्धांत)]]। <math>G</math> के सबग्राफ से बना एक और ग्राफ है <math>G</math> इसके कुछ किनारों को सिकोड़कर। ट्री-डेप्थ माइनर्स के तहत मोनोटोनिक है: ग्राफ़ का प्रत्येक माइनर <math>G</math> ट्री-डेप्थ अधिकतम ट्री-डेप्थ के बराबर होती है <math>G</math> अपने आप।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.2, p. 117.</ref> इस प्रकार, रॉबर्टसन-सेमुर प्रमेय द्वारा, प्रत्येक निश्चित के लिए <math>d</math> अधिकतम ट्री-डेप्थ वाले ग्राफ़ का सेट <math>d</math> इसमें निषिद्ध ग्राफ़ लक्षण वर्णन का एक सीमित सेट है।


अगर <math>\mathcal{F}</math> ग्राफ़ का एक वर्ग है जिसे ग्राफ़ नाबालिगों, फिर ग्राफ़ों को लेने के अंतर्गत बंद किया जाता है <math>\mathcal{F}</math> वृक्ष-गहराई है <math>O(1)</math> अगर और केवल अगर <math>\mathcal{F}</math> इसमें सभी पथ ग्राफ़ शामिल नहीं हैं.<ref name="no12-prop64">{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Proposition 6.4, p. 122.</ref>
अगर <math>\mathcal{F}</math> ग्राफ़ का एक वर्ग है जिसे ग्राफ़ नाबालिगों, फिर ग्राफ़ों को लेने के अंतर्गत बंद किया जाता है <math>\mathcal{F}</math> ट्री-डेप्थ है <math>O(1)</math> अगर और केवल अगर <math>\mathcal{F}</math> इसमें सभी पथ ग्राफ़ सम्मिलित नहीं हैं.<ref name="no12-prop64">{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Proposition 6.4, p. 122.</ref>
अधिक सटीक रूप से, एक स्थिरांक है <math>c</math> ऐसा कि पेड़ की गहराई का हर ग्राफ़ कम से कम <math>k^c</math> निम्नलिखित माइनरों में से एक शामिल है (प्रत्येक ट्रीडेप्थ कम से कम <math>k</math>):<ref name="kr"/>  
अधिक सटीक रूप से, एक स्थिरांक है <math>c</math> ऐसा कि ट्री की गहराई का हर ग्राफ़ कम से कम <math>k^c</math> निम्नलिखित माइनरों में से एक सम्मिलित है (प्रत्येक ट्रीडेप्थ कम से कम <math>k</math>):<ref name="kr"/>  
*द <math>k\times k</math> जाल,
*द <math>k\times k</math> जाल,
* ऊंचाई का पूरा बाइनरी ट्री <math>k</math>,
* ऊंचाई का पूरा बाइनरी ट्री <math>k</math>,
Line 40: Line 41:


==प्रेरित उपग्राफ==
==प्रेरित उपग्राफ==
ग्राफ माइनर के तहत अच्छा व्यवहार करने के साथ-साथ, ट्री-डेप्थ का ग्राफ के प्रेरित सबग्राफ के सिद्धांत से घनिष्ठ संबंध है। ग्राफ़ के उस वर्ग के भीतर जिसमें अधिकतम वृक्ष-गहराई है <math>d</math> (किसी भी निश्चित पूर्णांक के लिए <math>d</math>), एक प्रेरित उपसमूह होने का संबंध एक अच्छी तरह से अर्ध-क्रम बनाता है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.13, p. 137.</ref> प्रमाण का मूल विचार यह है कि यह संबंध एक अच्छी तरह से अर्ध-क्रम है, प्रेरण का उपयोग करना है <math>d</math>; ऊंचाई के जंगल <math>d</math> ऊंचाई के जंगलों के अनुक्रम के रूप में व्याख्या की जा सकती है <math>d-1</math> (ऊंचाई में पेड़ों की जड़ों को हटाकर बनाई गई-<math>d</math> वन) और हिगमैन के लेम्मा का उपयोग प्रेरण परिकल्पना के साथ एक साथ किया जा सकता है ताकि यह दिखाया जा सके कि ये अनुक्रम सुव्यवस्थित हैं।
ग्राफ माइनर के तहत अच्छा व्यवहार करने के साथ-साथ, ट्री-डेप्थ का ग्राफ के प्रेरित सबग्राफ के सिद्धांत से घनिष्ठ संबंध है। ग्राफ़ के उस वर्ग के भीतर जिसमें अधिकतम ट्री-डेप्थ है <math>d</math> (किसी भी निश्चित पूर्णांक के लिए <math>d</math>), एक प्रेरित उपसमूह होने का संबंध एक अच्छी तरह से अर्ध-क्रम बनाता है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, Lemma 6.13, p. 137.</ref> प्रमाण का मूल विचार यह है कि यह संबंध एक अच्छी तरह से अर्ध-क्रम है, प्रेरण का उपयोग करना है <math>d</math>; ऊंचाई के फॉरिस्ट <math>d</math> ऊंचाई के फॉरिस्टों के अनुक्रम के रूप में व्याख्या की जा सकती है <math>d-1</math> (ऊंचाई में ट्री की जड़ों को हटाकर बनाई गई-<math>d</math> वन) और हिगमैन के लेम्मा का उपयोग प्रेरण परिकल्पना के साथ एक साथ किया जा सकता है ताकि यह दिखाया जा सके कि ये अनुक्रम सुव्यवस्थित हैं।


अच्छी तरह से अर्ध-क्रम का तात्पर्य है कि ग्राफ़ की कोई भी संपत्ति जो प्रेरित सबग्राफ के संबंध में मोनोटोनिक है, उसमें सीमित रूप से कई निषिद्ध प्रेरित सबग्राफ हैं, और इसलिए बंधे हुए वृक्ष-गहराई के ग्राफ़ पर बहुपद समय में परीक्षण किया जा सकता है। अधिकतम वृक्ष-गहराई वाले ग्राफ़ <math>d</math> स्वयं के पास भी निषिद्ध प्रेरित उपसमूहों का एक सीमित सेट है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 138. Figure 6.6 on p. 139 shows the 14 forbidden subgraphs for graphs of tree-depth at most three, credited to the 2007 Ph.D. thesis of [[Zdeněk Dvořák]].</ref>
अच्छी तरह से अर्ध-क्रम का तात्पर्य है कि ग्राफ़ की कोई भी विशेशता जो प्रेरित सबग्राफ के संबंध में मोनोटोनिक है, उसमें सीमित रूप से कई निषिद्ध प्रेरित सबग्राफ हैं, और इसलिए बंधे हुए ट्री-डेप्थ के ग्राफ़ पर बहुपद समय में परीक्षण किया जा सकता है। अधिकतम ट्री-डेप्थ वाले ग्राफ़ <math>d</math> स्वयं के पास भी निषिद्ध प्रेरित उपसमूहों का एक सीमित सेट है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 138. Figure 6.6 on p. 139 shows the 14 forbidden subgraphs for graphs of tree-depth at most three, credited to the 2007 Ph.D. thesis of [[Zdeněk Dvořák]].</ref>
अगर <math>\mathcal{F}</math> सीमाबद्ध अध:पतन (ग्राफ़ सिद्धांत) वाले ग्राफ़ का एक वर्ग है, इसमें ग्राफ़ <math>\mathcal{F}</math> वृक्ष-गहराई को सीमित किया गया है यदि और केवल यदि कोई पथ ग्राफ है जो ग्राफ के प्रेरित उपग्राफ के रूप में नहीं हो सकता है <math>\mathcal{F}</math>.<ref name="no12-prop64"/>
अगर <math>\mathcal{F}</math> सीमाबद्ध अध:पतन (ग्राफ़ सिद्धांत) वाले ग्राफ़ का एक वर्ग है, इसमें ग्राफ़ <math>\mathcal{F}</math> ट्री-डेप्थ को सीमित किया गया है यदि और केवल यदि कोई पथ ग्राफ है जो ग्राफ के प्रेरित उपग्राफ के रूप में नहीं हो सकता है <math>\mathcal{F}</math>.<ref name="no12-prop64"/>




==जटिलता==
==जटिलता==
वृक्ष-गहराई की गणना करना कम्प्यूटेशनल रूप से कठिन है: संबंधित निर्णय समस्या एनपी-पूर्ण है।<ref name="p88">{{harvtxt|Pothen|1988}}.</ref> [[द्विदलीय ग्राफ]]के लिए समस्या एनपी-पूर्ण बनी हुई है {{harv|Bodlaender|Deogun|Jansen|Kloks|1998}}, साथ ही कॉर्डल ग्राफ़ के लिए भी।<ref>{{harvtxt|Dereniowski|Nadolski|2006}}.</ref>
ट्री-डेप्थ की गणना करना कम्प्यूटेशनल रूप से कठिन है: संबंधित निर्णय समस्या एनपी-पूर्ण है।<ref name="p88">{{harvtxt|Pothen|1988}}.</ref> [[द्विदलीय ग्राफ]] के लिए समस्या एनपी-पूर्ण बनी हुई है {{harv|Bodlaender|Deogun|Jansen|Kloks|1998}}, साथ ही कॉर्डल ग्राफ़ के लिए भी है।<ref>{{harvtxt|Dereniowski|Nadolski|2006}}.</ref>
सकारात्मक पक्ष पर, वृक्ष-गहराई की गणना अंतराल ग्राफ़ पर बहुपद समय में की जा सकती है,<ref>{{harvtxt|Aspvall|Heggernes|1994}}.</ref> साथ ही क्रमपरिवर्तन, समलम्बाकार, वृत्ताकार-चाप, वृत्ताकार क्रमपरिवर्तन ग्राफ़ और परिबद्ध आयाम के सह तुलनीयता ग्राफ़ पर भी।<ref>{{harvtxt|Deogun|Kloks|Kratsch|Müller|1999}}.</ref> अप्रत्यक्ष पेड़ों के लिए, पेड़ की गहराई की गणना रैखिक समय में की जा सकती है।<ref>{{harvtxt|Iyer|Ratliff|Vijayan|1988}}; {{harvtxt|Schäffer|1989}}.</ref>
 
धनात्मक भाग पर, ट्री-डेप्थ की गणना अंतराल ग्राफ़ पर बहुपद समय में की जा सकती है,<ref>{{harvtxt|Aspvall|Heggernes|1994}}.</ref> साथ ही क्रमपरिवर्तन, समलम्बाकार, वृत्ताकार-चाप, वृत्ताकार क्रमपरिवर्तन ग्राफ़ और परिबद्ध आयाम के सह तुलनीयता ग्राफ़ पर भी है।<ref>{{harvtxt|Deogun|Kloks|Kratsch|Müller|1999}}.</ref> अप्रत्यक्ष ट्री के लिए, ट्री की गहराई की गणना रैखिक समय में की जा सकती है।<ref>{{harvtxt|Iyer|Ratliff|Vijayan|1988}}; {{harvtxt|Schäffer|1989}}.</ref>
 
{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}} सन्निकटन अनुपात के साथ ट्री-डेप्थ के लिए एक सन्निकटन एल्गोरिदम दें <math>O((\log n)^2)</math>, इस तथ्य पर आधारित है कि ट्री-डेप्थ हमेशा एक ग्राफ़ की ट्री-चौड़ाई के लघुगणकीय कारक के भीतर होती है।


{{harvtxt|Bodlaender|Gilbert|Hafsteinsson|Kloks|1995}} सन्निकटन अनुपात के साथ वृक्ष-गहराई के लिए एक सन्निकटन एल्गोरिदम दें <math>O((\log n)^2)</math>, इस तथ्य पर आधारित है कि वृक्ष-गहराई हमेशा एक ग्राफ़ की वृक्ष-चौड़ाई के लघुगणकीय कारक के भीतर होती है।
क्योंकि ग्राफ माइनर के तहत ट्री-डेप्थ मोनोटोनिक है, यह [[पैरामीटरयुक्त जटिलता]] है | फिक्स्ड-पैरामीटर ट्रैक्टेबल: समय में चलने वाले ट्री-डेप्थ की गणना के लिए एल्गोरिदम है {{nobreak|<math>f(d) n^{O(1)}</math>,}} जहाँ <math>d</math> दिए गए ग्राफ़ की गहराई है और <math>n</math> इसके शीर्षों की संख्या है। इस प्रकार, प्रत्येक निश्चित मान के लिए <math>d</math>, यह परीक्षण करने की समस्या कि ट्री-डेप्थ अधिकतम है या नहीं <math>d</math> बहुपद समय में हल किया जा सकता है। अधिक विशेष रूप से, पर निर्भरता <math>n</math> इस एल्गोरिथ्म को निम्नलिखित विधि द्वारा रैखिक बनाया जा सकता है: पहले खोज ट्री की गहराई की गणना करें, और परीक्षण करें कि क्या ट्री-डेप्थ <math>2^d</math> से अधिक है। यदि ऐसा है, तो ग्राफ़ की ट्री-डेप्थ इससे अधिक है <math>d</math> और समस्या हल हो गई है। यदि नहीं, तो उथली गहराई वाले पहले खोज ट्री का उपयोग बंधी हुई चौड़ाई के साथ ट्री अपघटन के निर्माण के लिए किया जा सकता है, और बंधी हुई ट्री चौड़ाई के ग्राफ़ के लिए मानक [[गतिशील प्रोग्रामिंग]] तकनीकों का उपयोग रैखिक समय में गहराई की गणना करने के लिए किया जा सकता है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 138. A more complicated linear time algorithm based on the planarity of the excluded minors for tree-depth was given earlier by {{harvtxt|Bodlaender|Deogun|Jansen|Kloks|1998}}. For improved parameterized algorithms see {{harvtxt|Reidl|Rossmanith|Sánchez Villaamil|Sikdar|2014}}.</ref>


क्योंकि ग्राफ माइनर के तहत ट्री-डेप्थ मोनोटोनिक है, यह [[पैरामीटरयुक्त जटिलता]] है | फिक्स्ड-पैरामीटर ट्रैक्टेबल: समय में चलने वाले ट्री-डेप्थ की गणना के लिए एक एल्गोरिदम है {{nobreak|<math>f(d) n^{O(1)}</math>,}} कहाँ <math>d</math> दिए गए ग्राफ़ की गहराई है और <math>n</math> इसके शीर्षों की संख्या है. इस प्रकार, प्रत्येक निश्चित मान के लिए <math>d</math>, यह परीक्षण करने की समस्या कि वृक्ष-गहराई अधिकतम है या नहीं <math>d</math> बहुपद समय में हल किया जा सकता है। अधिक विशेष रूप से, पर निर्भरता <math>n</math> इस एल्गोरिथ्म को निम्नलिखित विधि द्वारा रैखिक बनाया जा सकता है: पहले खोज वृक्ष की गहराई की गणना करें, और परीक्षण करें कि क्या इस वृक्ष की गहराई इससे अधिक है <math>2^d</math>. यदि ऐसा है, तो ग्राफ़ की वृक्ष-गहराई इससे अधिक है <math>d</math> और समस्या हल हो गई है. यदि नहीं, तो उथली गहराई वाले पहले खोज वृक्ष का उपयोग बंधी हुई चौड़ाई के साथ वृक्ष अपघटन के निर्माण के लिए किया जा सकता है, और बंधी हुई वृक्ष चौड़ाई के ग्राफ़ के लिए मानक [[गतिशील प्रोग्रामिंग]] तकनीकों का उपयोग रैखिक समय में गहराई की गणना करने के लिए किया जा सकता है।<ref>{{harvtxt|Nešetřil|Ossona de Mendez|2012}}, p. 138. A more complicated linear time algorithm based on the planarity of the excluded minors for tree-depth was given earlier by {{harvtxt|Bodlaender|Deogun|Jansen|Kloks|1998}}. For improved parameterized algorithms see {{harvtxt|Reidl|Rossmanith|Sánchez Villaamil|Sikdar|2014}}.</ref>
यह भी संभव है कि, उन ग्राफ़ों के लिए ट्री-डेप्थ की सटीक गणना करना भी संभव है जिनकी ट्री-डेप्थ बड़ी हो सकती है, एक स्थिरांक <math>O(c^n)</math> के लिए <math>c</math> 2 थोड़ा छोटा है।{{sfnp|Fomin|Giannopoulou|Pilipczuk|2013}}
समय के साथ, उन ग्राफ़ों के लिए वृक्ष-गहराई की सटीक गणना करना भी संभव है जिनकी वृक्ष-गहराई बड़ी हो सकती है <math>O(c^n)</math> एक स्थिरांक के लिए <math>c</math> 2 से थोड़ा छोटा।{{sfnp|Fomin|Giannopoulou|Pilipczuk|2013}}


==टिप्पणियाँ==
==टिप्पणियाँ==

Revision as of 13:03, 7 August 2023

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

परिभाषाएँ

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

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

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

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

उदाहरण

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

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

पथ की ट्री-डेप्थ शिखर बिल्कुल सही है . एक फॉरिस्ट इस गहराई के साथ इस पथ का प्रतिनिधित्व पथ के मध्यबिंदु को मूल के रूप में रखकर बनाया जा सकता है और इसके दोनों ओर दो छोटे पथों के भीतर पुनरावृत्ति करना।[7]


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

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


ग्राफ अवयस्क

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

अगर ग्राफ़ का एक वर्ग है जिसे ग्राफ़ नाबालिगों, फिर ग्राफ़ों को लेने के अंतर्गत बंद किया जाता है ट्री-डेप्थ है अगर और केवल अगर इसमें सभी पथ ग्राफ़ सम्मिलित नहीं हैं.[12] अधिक सटीक रूप से, एक स्थिरांक है ऐसा कि ट्री की गहराई का हर ग्राफ़ कम से कम निम्नलिखित माइनरों में से एक सम्मिलित है (प्रत्येक ट्रीडेप्थ कम से कम ):[9]

  • जाल,
  • ऊंचाई का पूरा बाइनरी ट्री ,
  • व्यवस्था का मार्ग .

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

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

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


जटिलता

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

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

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

क्योंकि ग्राफ माइनर के तहत ट्री-डेप्थ मोनोटोनिक है, यह पैरामीटरयुक्त जटिलता है | फिक्स्ड-पैरामीटर ट्रैक्टेबल: समय में चलने वाले ट्री-डेप्थ की गणना के लिए एल्गोरिदम है , जहाँ दिए गए ग्राफ़ की गहराई है और इसके शीर्षों की संख्या है। इस प्रकार, प्रत्येक निश्चित मान के लिए , यह परीक्षण करने की समस्या कि ट्री-डेप्थ अधिकतम है या नहीं बहुपद समय में हल किया जा सकता है। अधिक विशेष रूप से, पर निर्भरता इस एल्गोरिथ्म को निम्नलिखित विधि द्वारा रैखिक बनाया जा सकता है: पहले खोज ट्री की गहराई की गणना करें, और परीक्षण करें कि क्या ट्री-डेप्थ से अधिक है। यदि ऐसा है, तो ग्राफ़ की ट्री-डेप्थ इससे अधिक है और समस्या हल हो गई है। यदि नहीं, तो उथली गहराई वाले पहले खोज ट्री का उपयोग बंधी हुई चौड़ाई के साथ ट्री अपघटन के निर्माण के लिए किया जा सकता है, और बंधी हुई ट्री चौड़ाई के ग्राफ़ के लिए मानक गतिशील प्रोग्रामिंग तकनीकों का उपयोग रैखिक समय में गहराई की गणना करने के लिए किया जा सकता है।[20]

यह भी संभव है कि, उन ग्राफ़ों के लिए ट्री-डेप्थ की सटीक गणना करना भी संभव है जिनकी ट्री-डेप्थ बड़ी हो सकती है, एक स्थिरांक के लिए 2 थोड़ा छोटा है।[21]

टिप्पणियाँ

  1. Bodlaender et al. (1998); Rossman (2008); Nešetřil & Ossona de Mendez (2012), p. 116.
  2. Nešetřil & Ossona de Mendez (2012), Definition 6.1, p. 115.
  3. Eppstein, David (November 15, 2012), Graph parameters and cliques in supergraphs.
  4. Nešetřil & Ossona de Mendez (2012), Lemma 6.1, p. 117.
  5. Nešetřil & Ossona de Mendez (2012), Section 6.5, "Centered Colorings", pp. 125–128.
  6. Gruber & Holzer (2008), Theorem 5, Hunter (2011), Main Theorem.
  7. Nešetřil & Ossona de Mendez (2012), Formula 6.2, p. 117.
  8. Bodlaender et al. (1995); Nešetřil & Ossona de Mendez (2012), Corollary 6.1, p. 124.
  9. 9.0 9.1 Kawarabayashi & Rossman (2018)
  10. Bodlaender et al. (1995); Nešetřil & Ossona de Mendez (2012), p. 123.
  11. Nešetřil & Ossona de Mendez (2012), Lemma 6.2, p. 117.
  12. 12.0 12.1 Nešetřil & Ossona de Mendez (2012), Proposition 6.4, p. 122.
  13. Nešetřil & Ossona de Mendez (2012), Lemma 6.13, p. 137.
  14. Nešetřil & Ossona de Mendez (2012), p. 138. Figure 6.6 on p. 139 shows the 14 forbidden subgraphs for graphs of tree-depth at most three, credited to the 2007 Ph.D. thesis of Zdeněk Dvořák.
  15. Pothen (1988).
  16. Dereniowski & Nadolski (2006).
  17. Aspvall & Heggernes (1994).
  18. Deogun et al. (1999).
  19. Iyer, Ratliff & Vijayan (1988); Schäffer (1989).
  20. Nešetřil & Ossona de Mendez (2012), p. 138. A more complicated linear time algorithm based on the planarity of the excluded minors for tree-depth was given earlier by Bodlaender et al. (1998). For improved parameterized algorithms see Reidl et al. (2014).
  21. Fomin, Giannopoulou & Pilipczuk (2013).


संदर्भ