ट्री (ग्राफ सिद्धांत)

Trees
A labeled tree with 6 vertices and 5 edges.
Vertices	v
Edges	v − 1
Chromatic number	2 if v > 1
Table of graphs and parameters

ग्राफ सिद्धांत में, एक पेड़ एक ऐसा अनुक्रमित ग्राफ होता है जिसमें किसी भी दो शीर्ष को बिल्कुल एक ही पथ से जोड़ा जाता है, या समरूपतः एक जुड़ा हुआ निर्दिष्टित अनिर्देशित ग्राफ होता है।एक वन एक ऐसा अनुक्रमित ग्राफ होता है जिसमें किसी भी दो शीर्ष को अधिकतम एक ही पथ से जोड़ा जाता है, या समरूपतः एक अचक्रीय निर्देशित ग्राफ होता है, या समरूपतः पेड़ों के वियोगीय संघ का एकीकृत संयोजन होता है।

एक पॉली वृक्ष या निर्देशित वृक्ष एक निर्देशित अचक्रीय ग्राफ होता है, जिसका अंशीय अनिर्देशित ग्राफ एक पेड़ होता है। एक पॉलीफ़ॉरेस्ट या निर्देशित वन एक निर्देशित अचक्रीय ग्राफ होता है, जिसका अंशीय अनिर्देशित ग्राफ एक वन होता है।

कंप्यूटर विज्ञान में "पेड़" के रूप में संदर्भित विभिन्न प्रकार के डेटा संरचनाएं ग्राफ थ्योरी में पेड़ होते हैं, यद्यपि ऐसे डेटा संरचनाएं सामान्यतः मूल रूप से जड़ी हुई पेड़ होती हैं। जिसे संचालित जड़ वृक्ष कहा जाता है, या तो इसके सभी सीधे बाएं तरफ दिखाने के लिए संचालित किया जाता है, एक जड़ी हुई पेड़ निर्देशित भी हो सकती है, जिसे "निर्देशित जड़ी हुई पेड़" कहा जाता है, जिसमें इसके सभी संबंधों को मूल से दूसरे वर्तमान तक दिखाता है, जिसे इस स्थिति में "वृक्षनी" या "आउट-ट्री" कहा जाता है या इसके सभी संबंधों को मूल की ओर दिखाता है - जिसे इस स्थिति में "विरोधी-वृक्षनी या "इन-ट्री" कहा जाता है। जिसे निर्देशित जड़ वाले वन कहा जाता है। जब हर जड़ वालेवृक्ष के सभी एज जड़ से दूर दिखाई देते हैं, तब उसे एक शाखन' या बाहरी-वन कहा जाता है। या इसके सभी किनारों को बनाना प्रत्येक जड़ वाले वृक्ष में जड़ की ओर इंगित करते हैं, इस विषय में इसे शाखा-विरोधी या वन कहा जाता है।

वृक्ष शब्द का उल्लेख पहली बार 1857 में ब्रिटिश गणितीय आर्थर केली ने किया था।

परिभाषाएँ

वृक्ष

एक वृक्ष एक अप्रत्यक्ष आरेख G है,जो निम्न समकक्ष स्थितियों में से किसी एक को पूरा करता है:

• G जुड़ा हुआ और वह अचक्रीय होता है (कोई चक्र नहीं होता)।
• G चक्रीय है, और यदि कोई शीर्ष G में जोड़ा जाता है तो एक सरल चक्र बनता है।
• G जुड़ा हुआ है, परंतु यदि G से किसी एक शीर्ष को हटा दिया जाए तो यह असंगत हो जाएगा।
• G जुड़ा हुआ है और 3-शीर्ष पूर्ण आरेख K3 G का लघु नहीं है।
• G में किन्हीं भी दो शीर्षों को एक अद्वितीय सरल पथ से जोड़ा जा सकता है।

यदि G के बहुत से शीर्ष हैं, उनमें से n मान लीजिए,तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:

• G जुड़ा हुआ है और है n − 1 शीर्ष है।
• G जुड़ा हुआ है, और हर उपआरेख का G शून्य या एक घटना शीर्षों के साथ कम से कम एक शीर्ष सम्मिलित है।
• G का कोई सरल चक्र नहीं है और इसमें n − 1 शीर्ष है।

आरेख सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख को सामान्यतः एक वृक्ष नहीं माना जाता है,जबकि यह रिक्त रूप से एक आरेख के रूप में जुड़ा हुआ है, बीजगणितीय टोपोलॉजी में यह 0-सम्बद्ध ​​नहीं है,अरिक्‍त पंक्‍तिवृक्ष के विपरीत, और "शीर्षों के सापेक्ष में एक और शीर्ष" संबंध का उल्लंघन करता है। यद्यपि, इसे शून्य वृक्ष वाला जंगल माना जा सकता है।,

एक आंतरिक शीर्ष् कम से कम 2 के डिग्री वाला शीर्ष् होता है। इसी तरह, बाहरी शीर्ष् उस शीर्ष् को कहते हैं जिसका डिग्री 1 हो, एक वृक्ष में एक शाखा शीर्ष उस शीर्ष को कहा जाता है जिसका डिग्री कम से कम 3 हो।

वन

एक वन एक अविन्यास आरेख है जिसमें मात्र दो शीर्ष एक ही मार्ग से जुड़े हुए होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय आरेख है, जिसके सभी जुड़े घटक वृक्ष हैं; दूसरे शब्दों में, आरेख में वृक्ष के आरेख का एक असम्बद्ध संघ होता है। विशेष रूप से, शून्य आदेश वाली आरेख एक एकल वृक्ष, और एक धार रहित आरेख वन के उदाहरण हैं। हर एक वृक्ष के लिए V - E = 1 होने के कारण, हम आसानी से एक वन में उपस्थित वृक्षों की संख्या को कुल शीर्ष और कुल एज के अंतर को घटाकर निकाल सकते हैं। TV − TE = वन में वृक्षो की संख्या है।

पॉलीवृक्ष

एक पॉलीवृक्ष या निर्देशित वृक्ष एक निर्देशित अविसारण आरेख (डीएजी) होता है जिसका अंतर्निहित अविन्यासी आरेख एक वृक्ष होता है। दूसरे शब्दों में, यदि हक धारित एजों को अविधारित एजों से बदल दें, तो हम एक अविधारित आरेख प्राप्त करते हैं जो संयुक्त और अचक्रीय दोनों होता है।दू सरे शब्दों में, यदि हम इसकी निर्दिष्ट धाराएं अविन्यस्त धाराओं में बदल दें, तो हम एक अविन्यस्त आरेख प्राप्त करते है ।

कुछ लेखक वाक्यांश निर्देशित वृक्ष को उस विषय तक सीमित करें जहां शीर्षों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है

पॉलीवन

पॉलीवन या निर्देशित वन)एक निर्देशित आरेख होता है जिसका अंशकारी अशिखित आरेख एक वन होता है। अर्थात् जब हम इसकी निर्देशित धुरीयों को अनिर्दिष्ट धुरीयों में बदलते हैं, तो हमें एक वन मिलता है जो कि अनुबंधित और अशिखित दोनों होता है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख प्राप्त होता है जो चक्रीय है।

कुछ लेखक"निर्देशित वन" शब्द अपने सीमित अर्थ में प्रयोग करते हैं, जहां प्रत्येक जुड़े हुए घटक की सभी संयुक्त तत्व एक विशिष्ट शिखर की ओर निर्देशित होते हैं या एक विशिष्ट शिखर से सभी दिशाओं में निर्देशित होते हैं।

जड़ वाला वृक्ष

एक जड़ी हुई पेड़ एक ऐसी पेड़ होती है जिसमें एक शीर्ष को मूल निर्धारित किया गया होता है। जड़ी हुई पेड़ के संबंधों को प्राकृतिक निर्देश दिया जा सकता है, या तो मूल से दूर या मूल की ओर, जिसके कारण संरचना एक निर्देशित जड़ी हुई पेड़ बन जाती है। जब एक निर्देशित जड़ी हुई पेड़ का मूल से दूर की ओर एक निर्देश होता है, तो उसे "वृक्षनी" या "आउट-ट्री कहा जाता है; जब उसमें मूल की ओर की एक निर्देश होती है, तो उसे "विरोधी-वृक्षनी" या "इन-ट्री कहा जाता है। पेड़ का क्रम एक आंशिक क्रमण है जो पेड़ के शीर्ष पर लगाया जाता है, जहां u < v तभी होता है जब मूल से v तक का अद्वितीय पथ u से गुजरता हो। एक ग्राफ G का उप-ग्राफ होने वाला मूलबद्ध पेड़ T एक साधारण पेड़ है यदि G में हर T-पथ के अंत में इस पेड़ के वृक्ष-क्रम में तुल्यात्मक हैं मूलबद्ध पेड़, जो प्रायः प्रत्येक शीर्ष पर पड़ने वाले पड़ोसियों के आदेश जैसी अतिरिक्त संरचना के साथ होता है, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; इसे ट्री डेटा संरचना कहा जाता है।

जहां पेड़ों को सामान्यतः मूल रूप में होता है, बिना किसी निर्दिष्ट मूल के पेड़ को "मुक्त पेड़" कहा जाता है।

एक लेबलबद्ध पेड़ एक पेड़ होती है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। एन शीर्ष वाले एक लेबलबद्ध पेड़ के शीर्षों को सामान्यतः लेबल 1, 2, ..., n दिए जाते हैं। एक आपसी रूप से जुड़ी पेड़ एक लेबलबद्ध मूलबद्ध पेड़ होती है जहां शीर्ष लेबल वृक्ष-क्रम का पालन करते हैं अर्थात, यदि u और v दो शीर्ष के लिए u < v है, तो u का लेबल v के लेबल से छोटा होता है

एक मूलबद्ध पेड़ में, एक शीर्ष v का माता-पिता वह शीर्ष होता है जो v को मूल की ओर जाने वाले पथ पर v से जुड़ा होता है; प्रत्येक शीर्ष का एक अद्वितीय माता-पिता होता है केवल मूल के लिए जो कोई माता-पिता नहीं होता है। एक शीर्ष v का एक बालक शीर्ष वह शीर्ष होता है जिसका v माता-पिता होता है। एक शीर्ष v का एक आगे का शीर्ष वह शीर्ष होता है जो या तो v का माता-पिता होता है या v के माता-पिता का पुनरावृत्तिक रूप से आगे का शीर्ष होता है।. एक शीर्ष v का एक वंशज वह शीर्ष होता है जो या तो v का बालक होता है या v के बालकों में से किसी एक का वंशज होता है। शीर्ष v का एक सहोदर वह कोई अन्य शीर्ष होता है जो पेड़ में v के समान माता-पिता रखता है। एक पत्ती एक ऐसा शीर्ष है जिसके कोई बालक नहीं होते हैं। एक आंतरिक शीर्ष एक शीर्ष होता है जो पत्ती नहीं होता है।

एक मूलबद्ध पेड़ में एक शीर्ष की ऊँचाई वह पथ की लंबाई होती है जो उस शीर्ष से किसी पत्ती तक सबसे लंबी होती है। पेड़ की ऊँचाई मूल की ऊँचाई होती है। एक शीर्ष का गहराई वह पथ की लंबाई होती है जो उस शीर्ष से उसके मूल तक (मूल पथ) होती है। यह सामान्यतः विभिन्न स्व-संतुलित पेड़ों, विशेष रूप से पेड़ों, के प्रबंधन में आवश्यक होता है।मूल की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वाले पेड़ में गहराई और ऊँचाई शून्य होती है। पारंपरिक रूप से, एक खाली पेड़ जहां कोई शीर्ष नहीं होते हैं, यदि ऐसा स्वीकार्य होता हो की गहराई और ऊँचाई -1 होती है।

एक k-अर पेड़ एक मूलबद्ध पेड़ होता है जिसमें प्रत्येक शीर्ष के अधिकतम k बालक होते हैं। 2-अर पेड़ को सामान्यतः बाइनरी पेड़ कहा जाता है, जबकि 3-अर पेड़ को कभी-कभी टर्नरी पेड़ कहा जाता है।

क्रमित वृक्ष

एक क्रमित पेड़ (या प्लेन पेड़) एक मूलबद्ध पेड़ होता है जिसमें प्रत्येक शीर्ष के बालकों के लिए एक क्रमबद्धता निर्धारित की गई होती है। इसे "प्लेन पेड़" कहा जाता है क्योंकि बालकों की क्रमबद्धता एक प्लेन में पेड़ को एम्बेड करने के समकक्ष होती है, जिसमें मूल ऊपर होता है और प्रत्येक शीर्ष के बालक उस शीर्ष से नीचे होते हैं। यदि एक मूलबद्ध पेड़ को एक विमुद्रीकरण में दिया गया हो और एक दिशा को स्थायी किया गया हो, जैसे बाएं से दाएं, तो एक विमुद्रीकरण बालकों की क्रमबद्धता देता है। उम्रकैद, एक क्रमित पेड़ दिया गया हो और पारंपरिक रूप से मूल को शीर्ष पर चित्रित किया गया हो, तो क्रमित पेड़ में बालक शीर्षों को बाएं से दाएं चित्रित किया जा सकता है, जिससे एक मूलतः अद्यतित समतल विमुद्रीकरण मिलता है।

गुण

• प्रत्येक पेड़ द्विभाज्य ग्राफ होता है। एक ग्राफ द्विभाज्य होता है यदि और केवल यदि इसमें विषम लंबाई के चक्र सम्मिलित नहीं हैं। क्योंकि पेड़ में कोई चक्र ही नहीं होता है, इसलिए यह द्विभाज्य होता है।
• केवल गणनीय संख्या में शीर्ष वाले प्रत्येक पेड़ एक समतली आलेख होता है।
• प्रत्येक जुड़ा हुआ आरेख G में एक स्पैनिंग पेड़ होता है, जो G के हर शीर्ष को सम्मिलित करता है और जिसकी एज़ भी G की एज़ होती हैं। अधिक विशिष्ट प्रकार के फैले हुए पेड़, प्रत्येक जुड़े परिमित ग्राफ में विद्यमान हैं, इसमें गहराई-पहले खोज पेड़ और चौड़ाई-पहले खोज पेड़ सम्मिलित हैं डेप्थ-फर्स्ट-सर्च ट्री के अस्तित्व का सामान्यीकरण करते हुए, हर जुड़े हुए ग्राफ में केवल गिने-चुने कोने के साथ ट्रेमॉक्स का पेड़ होता है यद्यपि कुछ असंख्य आरेखों में ऐसा कोई पेड़ नहीं होता है। पत्तों की यह न्यूनतम संख्या पथ ग्राफ़ की विशेषता है; अधिकतम संख्या, n − 1, केवल स्टार आरेख द्वारा प्राप्त की जाती है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।

• प्रत्येक परिमित वृक्ष n शीर्षों के साथ, साथ n > 1, कम से कम दो टर्मिनल शीर्ष (पत्तियां) हैं। पत्तों की यह न्यूनतम संख्या पथ आरेख ़ की विशेषता है; अधिकतम संख्या, n − 1, केवल स्टार आरेख ़ द्वारा प्राप्त किया जाता है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
• एक वृक्ष में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक वृक्ष में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हर वृक्ष एक माध्यिका आरेख होता है।
• हर वृक्ष का एक आरेख केंद्र होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक एन- शीर्ष् वृक्ष में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में शीर्ष् को हटाने से वृक्ष को n/2 वर्टिकल से कम के सबवृक्ष में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से वृक्ष ठीक n/2 शीर्षों के दो उपवृक्षों में विभाजित हो जाता है।

गणना

लेबल वाले वृक्ष

केली के सूत्र में कहा गया है कि हैं nⁿ⁻² वृक्ष पर n लेबल वाले शीर्ष। एक क्लासिक प्रूफ प्रुफर अनुक्रम का उपयोग करता है, जो स्वाभाविक रूप से एक मजबूत परिणाम दिखाता है: शीर्ष वाले वृक्ष ों की संख्या 1, 2, …, n डिग्री d₁, d₂, …, d_n क्रमशः बहुपद प्रमेय है

${n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.$

एक अधिक सामान्य समस्या एक अप्रत्यक्ष आरेख में फैले हुए वृक्ष ों की गिनती करना है, जिसे मैट्रिक्स वृक्ष प्रमेय द्वारा संबोधित किया जाता है। (केली का सूत्र एक पूर्ण आरेख में फैले वृक्ष ों का विशेष मामला है।) आकार की परवाह किए बिना सभी उप-वृक्षों को गिनने की समान समस्या सामान्य स्थिति में शार्प-पी-पूर्ण|#पी-पूर्ण है (Jerrum (1994)).

बिना लेबल वाले वृक्ष

बिना लेबल वाले मुक्त वृक्ष ों की संख्या गिनना एक कठिन समस्या है। संख्या के लिए कोई बंद सूत्र नहीं t(n) वृक्ष ों के साथ n आरेख समाकृतिकता तक शीर्ष ज्ञात है। के पहले कुछ मान t(n) हैं

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (sequence A000055 in the OEIS).

Otter (1948) स्पर्शोन्मुख अनुमान सिद्ध किया

$t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,$

साथ C ≈ 0.534949606... और α ≈ 2.95576528565... (sequence A051491 in the OEIS). यहां ही ~ चिह्न का अर्थ है

$\lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.$

यह संख्या के लिए उनके विषम अनुमान का परिणाम है r(n) बिना लेबल वाले जड़ वाले वृक्ष n कोने:

$r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,$

साथ D ≈ 0.43992401257... और एक सा α ऊपर के रूप में (cf. Knuth (1997), बच्चू। 2.3.4.4 और Flajolet & Sedgewick (2009), बच्चू। VII.5, पी। 475)।

के पहले कुछ मान r(n) हैं

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (sequence A000081 in the OEIS)

वृक्ष ों के प्रकार

• एक पथ आरेख (या रैखिक आरेख ) के होते हैं n शीर्षों को एक पंक्ति में व्यवस्थित किया जाता है, ताकि शीर्षों को i और i + 1 किनारे से जुड़े हुए हैं i = 1, …, n – 1.
• एक तारकीय वृक्ष में एक केंद्रीय शीर्ष होता है जिसे जड़ कहा जाता है और इससे जुड़े कई पथ आरेख होते हैं। अधिक औपचारिक रूप से, एक वृक्ष तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
• एक तारा (आरेख सिद्धांत) एक वृक्ष है जिसमें एक आंतरिक शीर्ष (और n – 1 पत्तियाँ)। दूसरे शब्दों में, आदेश का एक तारा वृक्ष n व्यवस्था का वृक्ष है n अधिक से अधिक पत्तियों के साथ।
• एक कैटरपिलर वृक्ष एक ऐसा वृक्ष है जिसमें सभी कोने एक केंद्रीय पथ सबआरेख की दूरी 1 के भीतर हैं।
• रेखांकन की एक सूची# लॉबस्टर एक वृक्ष है जिसमें सभी शीर्ष एक केंद्रीय पथ सबआरेख की दूरी 2 के भीतर हैं।
• डिग्री का एक नियमित वृक्ष d अनंत वृक्ष है d प्रत्येक शीर्ष पर किनारों। ये मुक्त समूहों के केली आरेख और बिल्डिंग (गणित) के सिद्धांत के रूप में उत्पन्न होते हैं।

यह भी देखें

• निर्णय वृक्ष
• हाइपरवृक्ष
• हॉटलाइन
• छद्मवन
• वृक्ष संरचना (सामान्य)
• वृक्ष (डेटा संरचना)
• बिना जड़ वाला बाइनरी वृक्ष

संदर्भ

• Bender, Edward A.; Williamson, S. Gill (2010), Lists, Decisions and Graphs. With an Introduction to Probability
• Dasgupta, Sanjoy (1999), "Learning polytrees", in Proc. 15th Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999 (PDF), pp. 134–141.
• Deo, Narsingh (1974), Graph Theory with Applications to Engineering and Computer Science (PDF), Englewood, New Jersey: Prentice-Hall, ISBN 0-13-363473-6, archived (PDF) from the original on 2019-05-17
• Harary, Frank; Prins, Geert (1959), "The number of homeomorphically irreducible trees, and other species", Acta Mathematica (in English), 101 (1–2): 141–162, doi:10.1007/BF02559543, ISSN 0001-5962
• Harary, Frank; Sumner, David (1980), "The dichromatic number of an oriented tree", Journal of Combinatorics, Information & System Sciences, 5 (3): 184–187, MR 0603363.
• Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines", in Proc. 8th International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983 (PDF), pp. 190–193.
• Li, Gang (1996), "Generation of Rooted Trees and Free Trees", M.S. Thesis, Dept. of Computer Science, University of Victoria, BC, Canada (PDF), p. 9.
• Simion, Rodica (1991), "Trees with 1-factors and oriented trees", Discrete Mathematics, 88 (1): 93–104, doi:10.1016/0012-365X(91)90061-6, MR 1099270.

अग्रिम पठन

• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
• Flajolet, Philippe; Sedgewick, Robert (2009), Analytic Combinatorics, Cambridge University Press, ISBN 978-0-521-89806-5
• "Tree", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Knuth, Donald E. (November 14, 1997), The Art of Computer Programming Volume 1: Fundamental Algorithms (3rd ed.), Addison-Wesley Professional
• Jerrum, Mark (1994), "Counting trees in a graph is #P-complete", Information Processing Letters, 51 (3): 111–116, doi:10.1016/0020-0190(94)00085-9, ISSN 0020-0190.
• Otter, Richard (1948), "The Number of Trees", Annals of Mathematics, Second Series, 49 (3): 583–599, doi:10.2307/1969046, JSTOR 1969046.