ट्री (ग्राफ सिद्धांत): Difference between revisions

Trees
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

Latest revision as of 12:17, 10 June 2023

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

एक पॉलीट्री (या निर्देशित ट्री, या अभिविन्यासित ट्री, या एकलत्रिंशक नेटवर्क) एक ऐसा निर्देशित अक्रांत आरेख (डीएजी ) होता है, जिसका अंतर्निहित अनिर्देशित आरेख एक ट्री होता है एक पॉली वन (या निर्देशित वन या अभिविन्यासित वन) एक ऐसा निर्देशित अक्रांत आरेख होता है, जिसका अंतर्निहित अनिर्देशित आरेख एक वन होता है।

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

रूटेड वन एक रूटेड ट्री के असंयोजित संघ है। रूटेड वन निर्देशित भी हो सकता है, जिसे निर्देशित रूटेड वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध रूट को रूट से दूर प्रदर्शित करते है, तो उसे एक ब्रांचिंग या आउट-वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध रूट को रूट की ओर संकेत करते हैं, तो उसे एक विपरीत शाखा या आंतरिक-वन कहा जाता है।

^[2]ट्री शब्द का उल्लेख पहली बार 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 हो।^[3]

वन

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

पॉलीट्री

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

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

पॉलीवन

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

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

रूट वाला ट्री

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

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

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

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

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

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

क्रमित ट्री

क्रमबद्ध ट्री एक रूटेड ट्री है जिसमें प्रत्येक शीर्ष के उत्तराधिकारियों के लिए एक क्रमबद्धता निर्दिष्ट की जाती है। इसे "प्लेन ट्री " कहा जाता है क्योंकि उत्तराधिकारियों की क्रमबद्धता, ट्री को समतल में संपुट करने के समान होती है, जहां मूल ऊपर होता है और प्रत्येक शीर्ष के उत्तराधिकारी उस शीर्ष से नीचे होते हैं। विमान में रूट वाले ट्री की संपुटन को देखते हुए, यदि कोई उत्तराधिकारियों की दिशा को ठीक करता है, बाएं से दाएं कहें, तो एक संपुटन उत्तराधिकारियों को आदेश देता है। इसके विपरीत, एक आदेश दिया गया ट्री दिया गया है, और परंपरागत रूप से शीर्ष पर रूट खींच रहा है, फिर एक आदेशित ट्री में बच्चे के कोने को बाएं से दाएं खींचा जा सकता है, जो अनिवार्य रूप से अद्वितीय योजनाकार संपुटन प्रदान करता है।

गुण

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

ट्री में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक ट्री में हर तीन शीर्ष में एक अद्वितीय माध्यिका होती है, हर ट्री एक माध्यिका आरेख होता है।
हर ट्री का एक केंद्र होता है जिसमें एक शीर्ष या दो आसन्न शीर्ष होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक n शीर्ष ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न शीर्ष होते हैं। पहले मामले में शीर्ष को हटाने से ट्री को n/2 शीर्ष से कम के सब ट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से ट्री ठीक n/2 शीर्षों के दो उप ट्री में विभाजित हो जाता है।

गणना

नाम वाले ट्री

केली का सूत्र कहता है कि n लेबल वाले शीर्ष पर nn−2 ट्री होते हैं। प्रूफर क्रम का उपयोग करके एक प्रसिद्ध सिद्धांत का प्रमाण दिया जाता है, जो स्वतः ठोस परिणाम दिखाता है: d1, d2, ..., dn डिग्री वाले 1, 2, ..., n शीर्ष की ट्री की संख्या प्रतिस्थापनीय संख्या होती है।

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

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

बिना नाम वाले ट्री

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

1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … .

टी(एन) के पहले कुछ मान हैं(ओईआईएस में)।ओटर (1948) ने उपगामी अनुमान को सिद्ध किया

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

साथ ही $C \approx 0.534949606...$ और $α \approx 2.95576528565...$ . यहां $~$ चिह्न का अर्थ है

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

यह n सिरों वाले बिना लेबल वाले रूट वाले ट्री की संख्या r(n) के लिए उनके स्पर्शोन्मुख अनुमान का परिणाम है

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

साथ $D \approx 0.43992401257...$ और उपरोक्त के समान a (सी एफ नुथ (1997)अध्याय 2.3.4.4 और

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

1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …

ट्री के प्रकार

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

यह भी देखें

निर्णय ट्री
हाइपरट्री
हॉटलाइन
छद्मवन
ट्री संरचना (सामान्य)
ट्री (डेटा संरचना)
बिना रूट वाला बाइनरी ट्री

↑ Bender & Williamson 2010, p. 171.
↑ Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172–176.
However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist Gustav Kirchhoff investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508.
↑ DeBiasio, Louis; Lo, Allan (2019-10-09). "कुछ शाखा शीर्षों के साथ फैले पेड़". arXiv:1709.04937 [math.CO].
↑ See Li (1996).

संदर्भ

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.

[FOOTNOTEBenderWilliamson2010171-1] Bender & Williamson 2010, p. 171.

[2] Cayley (1857) "On the theory of the analytical forms called trees," Philosophical Magazine, 4th series, 13 : 172–176.
However it should be mentioned that in 1847, K.G.C. von Staudt, in his book Geometrie der Lage (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on pages 20–21. Also in 1847, the German physicist Gustav Kirchhoff investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), Annalen der Physik und Chemie, 72 (12) : 497–508.

[3] DeBiasio, Louis; Lo, Allan (2019-10-09). "कुछ शाखा शीर्षों के साथ फैले पेड़". arXiv:1709.04937 [math.CO].

[4] See Li (1996).

[1]

[2]

[3]

[4]

@@ Line 14: / Line 14: @@
 }}
-[[ ग्राफ सिद्धांत | आरेख सिद्धांत]] में,वृक्ष एक ऐसा [[अप्रत्यक्ष ग्राफ|अविरोधी आरेख]] है जिसमें प्रत्येक दो शीर्षो को एक ही पथ या समानरूप से एक जुड़ा हुआ अविरोधी अनिर्देशित आरेख है।{{sfn|Bender|Williamson|2010|p=171}} एक वन एक अविन्यास अभिमुखीय आरेख है जिसमें किसी भी दो शीर्षो को अधिकतम एक मार्ग द्वारा जोड़ा जाता है, समानांतर रूप से एक अविन्यास अभिमुखीय आरेख  है, या समानांतर रूप से वृक्षों का असंगठित संयुक्त संघ है।
+आरेख सिद्धांत में, ट्री एक ऐसा अनुक्रमित आरेख होता है जिसमें किसी भी दो शीर्ष को एक ही पथ से युग्मित किया जाता है, या समरूपतः एक जुड़ा हुआ निर्दिष्टित अनिर्देशित आरेख होता है।{{sfn|Bender|Williamson|2010|p=171}}एक वन एक ऐसा अनुक्रमित आरेख होता है जिसमें किसी भी दो शीर्ष को अधिकतम एक ही पथ से युग्मित किया जाता है, या समरूपतः एक अचक्रीय निर्देशित आरेख होता है, या समरूपतः ट्री के वियोगीय संघ का एकीकृत संयोजन होता है।
-एक पॉलीट्री निर्देशित अविन्यासी आरेख (डीएजी ) होता है जिसका अंशकालिक अविन्यासहीन आरेख एक वृक्ष होता है। एक पॉलीफॉरेस्ट या निर्देशित वन या उन्मुख वन एक निर्देशित चक्रीय आरेख है जिसका अंतर्निहित अप्रत्यक्ष आरेख एक वन है।
+एक पॉलीट्री (या निर्देशित ट्री, या अभिविन्यासित ट्री, या एकलत्रिंशक नेटवर्क) एक ऐसा निर्देशित अक्रांत आरेख (डीएजी ) होता है, जिसका अंतर्निहित अनिर्देशित आरेख एक ट्री होता है एक पॉली वन (या निर्देशित वन या अभिविन्यासित वन) एक ऐसा निर्देशित अक्रांत आरेख  होता है, जिसका अंतर्निहित अनिर्देशित आरेख एक वन होता है।
-कम्प्यूटर विज्ञान में वृक्ष के रूप में संदर्भित विभिन्न प्रकार के [[डेटा संरचनाएं]] आरेख सिद्धांत में वृक्ष होते हैं,यद्यपि ऐसी डेटा संरचनाएं सामान्यतः जड़ वृक्ष होते हैं। जड़ वृक्ष संचालित हो सकता है, जिसे संचालित जड़ वृक्ष कहा जाता है, या तो इसके सभी सीधे बाएं तरफ दिखाने के लिए संचालित किया जाता है - जिसके लिए इसे एक वृक्षारूपता या बाहरी- वृक्ष कहा जाता है - या फिर इसके सभी सीधे दाएं तरफ दिखाने के लिए संचालित किया जाता है - जिसके लिए इसे प्रतिरोधी-वृक्षारूपता या आंतरिक-वृक्ष कहा जाता है।{{sfn|Deo|1974|p=207}}<ref name="MehlhornSanders2008">{{cite book|author1=Kurt Mehlhorn|author-link=Kurt Mehlhorn|author2=Peter Sanders|author2-link=Peter Sanders (computer scientist)|title=Algorithms and Data Structures: The Basic Toolbox|date=2008|publisher=Springer Science & Business Media|isbn=978-3-540-77978-0|pages=52 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf |archive-url=https://web.archive.org/web/20150908084811/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/Introduction.pdf |archive-date=2015-09-08 |url-status=live}}</ref> कुछ लेखकों ने  जड़ वृक्ष को एक संचालित आरेख के रूप में परिभाषित किया है।<ref name="Makinson2012">{{cite book|author=David Makinson|author-link=David Makinson|title=कम्प्यूटिंग के लिए सेट, तर्क और गणित|year=2012|publisher=Springer Science & Business Media|isbn=978-1-4471-2499-3|pages=167–168}}</ref><ref>{{cite book|author=Kenneth Rosen|title=Discrete Mathematics and Its Applications, 7th edition|year=2011|publisher=McGraw-Hill Science|page=747|isbn=978-0-07-338309-5}}</ref><ref name="Schrijver2003">{{cite book|author=Alexander Schrijver|title=Combinatorial Optimization: Polyhedra and Efficiency|year=2003|publisher=Springer|isbn=3-540-44389-4|page=34}}</ref> एक जड़ वाले वन का अर्थ होता है कि इसमें कई अलग-अलग जड़ वाले पेड़ों का विभाजन होता है।एक जड़ वाले वन को निर्देशित भी किया जा सकता है, जिसे निर्देशित जड़ वाले वन कहा जाता है। जब हर जड़ वाले पेड़ के सभी एज जड़ से दूर दिखाई देते हैं, तब उसे एक शाखन' या बाहरी-वन कहा जाता है।- या इसके सभी किनारों को बनाना प्रत्येक जड़ वाले वृक्ष में जड़ की ओर इंगित करते हैं - इस विषय में इसे शाखा-विरोधी या वन कहा जाता है।
+कम्प्यूटर विज्ञान में ट्री के रूप में उल्लिखित विभिन्न प्रकार के डेटा संरचनाएं आरेख सिद्धांत में ट्री होते हैं, यद्यपि ऐसी डेटा संरचनाएं सामान्यतः रूटड ट्री होती हैं। रूटेड ट्री निर्देशित भी हो सकता है, जिसे निर्देशित रूटेड ट्री कहा जाता है। इसमें सभी संबंध रूट को रूट से दूर प्रदर्शित करते है, जिसे इस स्थिति में ट्री या आउट-ट्री कहा जाता है -कुछ लेखकों ने रूटेड ट्री को स्वयं निर्देशित आरेख के रूप में परिभाषित किया है।
+रूटेड वन एक रूटेड ट्री के असंयोजित संघ है। रूटेड वन निर्देशित भी हो सकता है, जिसे निर्देशित रूटेड वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध रूट को रूट से दूर प्रदर्शित करते है, तो उसे एक ब्रांचिंग या आउट-वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध रूट को रूट की ओर संकेत करते हैं, तो उसे एक विपरीत शाखा या आंतरिक-वन कहा जाता है।
+<ref>Cayley (1857) [https://books.google.com/books?id=MlEEAAAAYAAJ&pg=PA172 "On the theory of the analytical forms called trees,"] ''Philosophical Magazine'', 4th series, '''13''' : 172–176.<br>However it should be mentioned that in 1847, [[Karl Georg Christian von Staudt|K.G.C. von Staudt]], in his book ''Geometrie der Lage'' (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on [https://books.google.com/books?id=MzQAAAAAQAAJ&pg=PA20 pages 20–21]. Also in 1847, the German physicist [[Gustav Kirchhoff]] investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) [https://books.google.com/books?id=gx4AAAAAMAAJ&q=Kirchoff&pg=PA497 "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird"] (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), ''Annalen der Physik und Chemie'', '''72''' (12) : 497–508.</ref>ट्री शब्द का उल्लेख पहली बार 1857 में ब्रिटिश गणितीय [[आर्थर केली]] ने किया था।
-<ref>Cayley (1857) [https://books.google.com/books?id=MlEEAAAAYAAJ&pg=PA172 "On the theory of the analytical forms called trees,"] ''Philosophical Magazine'', 4th series, '''13''' : 172–176.<br>However it should be mentioned that in 1847, [[Karl Georg Christian von Staudt|K.G.C. von Staudt]], in his book ''Geometrie der Lage'' (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on [https://books.google.com/books?id=MzQAAAAAQAAJ&pg=PA20 pages 20–21]. Also in 1847, the German physicist [[Gustav Kirchhoff]] investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847) [https://books.google.com/books?id=gx4AAAAAMAAJ&q=Kirchoff&pg=PA497 "Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird"] (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), ''Annalen der Physik und Chemie'', '''72''' (12) : 497–508.</ref>वृक्ष शब्द का उल्लेख पहली बार 1857 में ब्रिटिश गणितीय [[आर्थर केली]] ने किया था।
@@ Line 26: / Line 29: @@
 == परिभाषाएँ ==
-=== वृक्ष            ===
+=== ट्री        ===
-एक वृक्ष             एक अप्रत्यक्ष आरेख             है {{mvar|G}} जो निम्नलिखित समतुल्य शर्तों में से किसी को भी संतुष्ट करता है:
+एक ट्री एक अप्रत्यक्ष आरेख  {{mvar|G}} है,जो निम्न समकक्ष स्थितियों में से किसी एक को पूरा करता है:
-* {{mvar|G}} जुड़ा हुआ आरेख             और साइकिल (आरेख             सिद्धांत) है (इसमें कोई चक्र नहीं है)।
+* {{mvar|G}}  जुड़ा हुआ और वह अचक्रीय होता है (कोई चक्र नहीं होता)।
-* {{mvar|G}} एसाइक्लिक है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) | किनारा (आरेख             सिद्धांत)]]  जोड़ा जाए तो एक साधारण चक्र बनता है {{mvar|G}}.
+* {{mvar|G}}  चक्रीय है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) |शीर्ष]] G में युग्मित किया जाता है तो एक सरल चक्र बनता है।
-* {{mvar|G}} जुड़ा हुआ है, लेकिन कनेक्टिविटी बन जाएगा (आरेख            ़ सिद्धांत)#कनेक्टेड आरेख            ़ अगर किसी एक किनारे को हटा दिया जाता है {{mvar|G}}.
+* {{mvar|G}} जुड़ा हुआ है, परंतु यदि {{mvar|G}} से किसी एक शीर्ष को हटा दिया जाए तो यह असंगत हो जाएगा।
-* {{mvar|G}} जुड़ा हुआ है और 3-वर्टेक्स पूर्ण आरेख            ़ है {{math|''K''{{sub|3}}}} का लघु (आरेख             सिद्धांत) नहीं है {{mvar|G}}.
+* {{mvar|G}}  जुड़ा हुआ है और 3-शीर्ष पूर्ण आरेख K3 {{mvar|G}} का लघु नहीं है।
-* कोई भी दो कोने अंदर {{mvar|G}} को एक अद्वितीय पथ (आरेख             सिद्धांत) द्वारा जोड़ा जा सकता है।
+* G में किन्हीं भी दो शीर्षों को एक अद्वितीय सरल पथ से युग्मित किया जा सकता है।
-अगर {{mvar|G}} के बहुत से शीर्ष हैं, कहते हैं {{mvar|n}उनमें से }, तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:
+यदि G के बहुत से शीर्ष हैं, उनमें से n मान लीजिए,तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:
-* {{mvar|G}} जुड़ा हुआ है और है {{math|''n'' − 1}} किनारे।
+* {{mvar|G}} जुड़ा हुआ है और है {{math|''n'' − 1}} शीर्ष है।
-* {{mvar|G}} जुड़ा हुआ है, और हर [[सबग्राफ (ग्राफ थ्योरी)|सबआरेख             (आरेख             थ्योरी)]] का {{mvar|G}} शून्य या एक घटना किनारों के साथ कम से कम एक शीर्ष शामिल है। (वह है, {{mvar|G}} जुड़ा हुआ है और [[अध: पतन (ग्राफ सिद्धांत)|अध: पतन (आरेख             सिद्धांत)]]|1-पतित।)
+* {{mvar|G}} जुड़ा हुआ है, और हर [[सबग्राफ (ग्राफ थ्योरी)|उपआरेख]] का {{mvar|G}} शून्य या एक घटना शीर्षों के साथ कम से कम एक शीर्ष सम्मिलित है।
-* {{mvar|G}} का कोई सरल चक्र नहीं है और है {{math|''n'' − 1}} किनारे।
+* G का कोई सरल चक्र नहीं है और इसमें n − 1 शीर्ष  है।
-आरेख            ़ सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख            ़ (बिना कोने वाले आरेख            ़) को आम तौर पर एक वृक्ष             नहीं माना जाता है: जबकि यह रिक्त रूप से एक आरेख            ़ के रूप में जुड़ा हुआ है (किसी भी दो कोने को एक पथ से जोड़ा जा सकता है), यह n नहीं है [[एन-जुड़ा हुआ]]|0-कनेक्टेड (या यहां तक कि (−1)-कनेक्टेड) बीजगणितीय टोपोलॉजी में, गैर-खाली वृक्ष            ों के विपरीत, और किनारों के संबंध की तुलना में एक और शीर्ष का उल्लंघन करता है। हालाँकि, इसे शून्य वृक्ष            ों वाला वन             माना जा सकता है।
+आरेख  सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख को सामान्यतः एक ट्री नहीं माना जाता है,जबकि यह रिक्त रूप से एक आरेख के रूप में जुड़ा हुआ है, बीजगणितीय टोपोलॉजी में यह 0-सम्बद्ध नहीं है,अरिक्‍त पंक्‍ति ट्री के विपरीत, और "शीर्षों के सापेक्ष में एक और शीर्ष" संबंध का उल्लंघन करता है। यद्यपि, इसे शून्य ट्री वाला वन माना जा सकता है।,
-एक {{em|internal vertex}} (या इनर वर्टेक्स) कम से कम 2 [[ डिग्री (ग्राफ सिद्धांत) | डिग्री (आरेख             सिद्धांत)]] का एक वर्टेक्स है। इसी तरह, एक {{em|external vertex}} (या बाहरी शीर्ष, टर्मिनल शीर्ष या पत्ती) 1 डिग्री का शीर्ष है। एक वृक्ष             में एक शाखा शीर्ष कम से कम 3 डिग्री का शीर्ष है।<ref>{{cite arXiv |last1=DeBiasio |first1=Louis |last2=Lo |first2=Allan |date=2019-10-09 |title=कुछ शाखा शीर्षों के साथ फैले पेड़|class=math.CO |eprint=1709.04937 }}</ref>
+एक आंतरिक शीर्ष् कम से कम 2 के डिग्री वाला शीर्ष्  होता है। इसी तरह, बाहरी शीर्ष् उस शीर्ष् को कहते हैं जिसका डिग्री 1 हो, एक ट्री में एक शाखा शीर्ष उस शीर्ष को कहा जाता है जिसका डिग्री कम से कम 3 हो।<ref>{{cite arXiv |last1=DeBiasio |first1=Louis |last2=Lo |first2=Allan |date=2019-10-09 |title=कुछ शाखा शीर्षों के साथ फैले पेड़|class=math.CO |eprint=1709.04937 }}</ref>
-एक {{em|irreducible tree}} (या शृंखला-घटा हुआ वृक्ष) एक ऐसा वृक्ष है जिसमें डिग्री 2 का कोई शीर्ष नहीं है (अनुक्रम में प्रगणित {{OEIS link|A000014}} [[OEIS]] में)।{{sfn|Harary|Prins|1959|p=150}}
 ===वन ===
-ए {{em|forest}} एक अप्रत्यक्ष आरेख            ़ है जिसमें कोई भी दो कोने ज़्यादा से ज़्यादा एक रास्ते से जुड़े होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय आरेख             है, जिसके सभी जुड़े घटक (आरेख             सिद्धांत) वृक्ष             हैं; दूसरे शब्दों में, आरेख            ़ में वृक्ष            ों के आरेख            ़ का एक असम्बद्ध संघ होता है। विशेष मामलों के रूप में, ऑर्डर-ज़ीरो आरेख            ़ (शून्य वृक्ष            ों वाला एक वन            ), एक अकेला वृक्ष             और एक बिना धार वाला आरेख            ़, वन            ों के उदाहरण हैं।
+एक वन एक अभिमुखित आरेख है जिसमें किसी भी दो शीर्ष को अधिकतम एक पथ द्वारा जोड़ा जा सकता है। समतुल्य रूप से,, वन एक अभिमुखित अचक्र आरेख होता है, जिसमें सभी जुड़े हुए घटक ट्री होते हैं; अन्य शब्दों में,आरेख एक ट्री के असंयोजित संघ का बना होता है। विशेष स्थिति के रूप में, शून्य क्रम वाला आरेख एकल ट्री, और एजलेस आरेख, वन के उदाहरण हैं। प्रत्येक ट्री        के लिए V - E = 1 होने के कारण, हम वन के अंदर उपस्थित ट्री की संख्या का आसानी से गणना कर सकते हैं, कुल शीर्ष और कुल संकेतों के बीच अंतर को घटा करके TV - TE = वन में ट्री की संख्या होती  है।
-चूंकि हर वृक्ष             के लिए {{math|1=''V'' − ''E'' = 1}}, हम कुल शीर्षों और कुल किनारों के बीच के अंतर को घटाकर वन             के भीतर मौजूद वृक्ष            ों की संख्या आसानी से गिन सकते हैं। {{math|1=''TV'' − ''TE'' =}} वन             में वृक्ष            ों की संख्या।
-=== पॉलीट्री ===
+=== पॉलीट्री        ===
-{{main|Polytree}}
+पॉलीट्री या निर्देशित ट्री या अभिमुखी ट्री या एकल जुड़ा हुआ नेटवर्क एक निर्देशित अशंकु आरेख होता है जिसका आधारभूत अनिर्देशित आरेख एक ट्री होता है। दूसरे शब्दों में, यदि हम इसके निर्देशित संबंधों को अनिर्देशित संबंधों से बदलें, तो हम एक ऐसे अनिर्देशित आरेख प्राप्त करते हैं जो संयुक्त और अचक्र होता है।
-ए {{em|polytree}}<ref name="d99">See {{harvtxt|Dasgupta|1999}}.</ref>(या निर्देशित वृक्ष            {{sfn|Deo|1974|p=206}} या उन्मुख वृक्ष<ref name="Harary 1980">See {{harvtxt|Harary|Sumner|1980}}.</ref><ref name="s91">See {{harvtxt|Simion|1991}}.</ref>या अकेले जुड़े नेटवर्क<ref name="kp83">See {{harvtxt|Kim|Pearl|1983}}.</ref> एक निर्देशित चक्रीय आरेख             (DAG) है जिसका अंतर्निहित अप्रत्यक्ष आरेख             एक वृक्ष             है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख             प्राप्त होता है जो जुड़ा हुआ है और अचक्रीय है।
-कुछ लेखक{{who|date=November 2021}} वाक्यांश निर्देशित ट्री को उस मामले तक सीमित करें जहां किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (अरबोरेसेंस (आरेख             सिद्धांत) देखें)।
+कुछ लेखक वाक्यांश निर्देशित ट्री को उस विषय तक सीमित करें जहां शीर्षों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है
-=== पॉलीफ़ॉरेस्ट ===
+=== पॉलीवन ===
-ए {{em|polyforest}} (या निर्देशित वन या उन्मुख वन) एक निर्देशित चक्रीय आरेख             है जिसका अंतर्निहित अप्रत्यक्ष आरेख             एक वन             है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख             प्राप्त होता है जो चक्रीय है।
+पॉलीवन या निर्देशित वन एक निर्देशित आरेख होता है जिसका अंशकारी अशिखित आरेख एक वन होता है। अर्थात् जब हम इसकी निर्देशित धुरीयों को अनिर्दिष्ट धुरीयों में बदलते हैं, तो हमें एक वन मिलता है जो कि अनुबंधित और अशिखित दोनों होता है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख             प्राप्त होता है जो चक्रीय होता है।
-कुछ लेखक{{who|date=November 2021}} वाक्यांश निर्देशित वन को उस मामले तक सीमित करें जहां प्रत्येक जुड़े घटक के किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (आर्बोरेसेंस (आरेख            ़ सिद्धांत) देखें)।
+कुछ लेखक"निर्देशित वन" शब्द अपने सीमित अर्थ में प्रयोग करते हैं, जहां प्रत्येक जुड़े हुए घटक की सभी संयुक्त तत्व एक विशिष्ट शिखर की ओर निर्देशित होते हैं या एक विशिष्ट शिखर से सभी दिशाओं में निर्देशित होते हैं।
-=== जड़ वाला वृक्ष            ===
+=== रूट वाला ट्री        ===
-ए {{em|rooted tree}} एक वृक्ष है जिसमें एक शीर्ष को जड़ निर्दिष्ट किया गया है।{{sfn|Bender|Williamson|2010|p=173}} एक जड़ वाले वृक्ष             के किनारों को एक प्राकृतिक अभिविन्यास दिया जा सकता है, या तो जड़ से दूर या उसकी ओर, जिस स्थिति में संरचना एक निर्देशित जड़ वाला वृक्ष             बन जाती है। जब एक निर्देशित जड़ वाले वृक्ष             का एक अभिविन्यास जड़ से दूर होता है, तो इसे अर्बोरेसेंस कहा जाता है{{sfn|Deo|1974|p=206}} या आउट-ट्री;{{sfn|Deo|1974|p=207}} जब इसका जड़              की ओर ओरिएंटेशन होता है, तो इसे एंटी-अर्बोरेसेंस या इन-ट्री कहा जाता है।{{sfn|Deo|1974|p=207}} वृक्ष-क्रम एक वृक्ष के शीर्ष पर आंशिक क्रम है {{math|''u'' < ''v''}} अगर और केवल अगर जड़              से अद्वितीय पथ {{mvar|v}} के माध्यम से गुजरता {{mvar|u}}. एक जड़ वाला वृक्ष             {{mvar|T}} जो आरेख             थ्योरी की शब्दावली है#कुछ आरेख             के सबआरेख             {{mvar|G}} एक [[सामान्य पेड़|सामान्य वृक्ष]]             है अगर हर का अंत होता है {{mvar|T}}-पथ में {{mvar|G}} इस ट्री-ऑर्डर में तुलनीय हैं {{harv|Diestel|2005|p=15}}. जड़ वाले वृक्ष            , अक्सर अतिरिक्त संरचना के साथ जैसे कि प्रत्येक शीर्ष पर पड़ोसियों को आदेश देना, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; [[वृक्ष डेटा संरचना]] देखें।
+रूटेड ट्री एक ट्री होता है जिसमें एक शीर्ष  को मूल निर्धारित किया गया होता है। रूटेड ट्री के संबंधों को प्राकृतिक अभिमुखीकरण किया जा सकता है, या तो मूल से दूर या मूल की ओर, जिसके पश्चात संरचना एक निर्देशित रूटेड ट्री बन जाती है। जब एक निर्देशित रूटेड ट्री में मूल से दूर की ओर अभिमुखीकरण होता है, तो उसे ट्री या आउट-ट्री  कहा जाता है; जब यह मूल की ओर अभिमुखीकरण होता है, तो उसे विपरीत-ट्री  या आंतरिक-ट्री कहा जाता है। ट्री-क्रम एक आंशिक क्रमण होता है जो एक ट्री के शीर्ष पर होता है, जहां u < v है यदि जब मूल से v तक का अद्वितीय पथ u से गुजरता है, तो एक आरेख G का उपआरेख    होने वाला रूटेड ट्री T एक सामान्य ट्री होता है यदि G में हर T-पथ के अंत संगणक इस ट्री-क्रम में तुल्यात्मक हैं रूटेड ट्री प्रायः प्रत्येक शीर्ष पर पड़ोसियों के क्रमबद्धता जैसी अतिरिक्त संरचना के साथ, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना होता हैं
-ऐसे संदर्भ में जहां वृक्ष            ों की आमतौर पर जड़ होती है, बिना किसी निर्दिष्ट जड़ वाले वृक्ष             को मुक्त वृक्ष             कहा जाता है।
+जहां ट्री को सामान्यतः मूल रूप में होता है, बिना किसी निर्दिष्ट मूल के ट्री को "मुक्त ट्री" कहा जाता है।
-एक लेबल वाला वृक्ष             एक वृक्ष             है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। लेबल लगे वृक्ष             के शीर्ष पर {{mvar|n}} शीर्षों को आमतौर पर लेबल दिए जाते हैं {{math|1, 2, …, ''n''}}. एक [[पुनरावर्ती वृक्ष]] एक लेबल वाला जड़ वाला वृक्ष है जहाँ शीर्ष लेबल वृक्ष क्रम का सम्मान करते हैं (अर्थात, यदि {{math|''u'' < ''v''}} दो शीर्षों के लिए {{mvar|u}} और {{mvar|v}}, फिर का लेबल {{mvar|u}} के लेबल से छोटा है {{mvar|v}}).
+नामपत्रित ट्री ऐसा ट्री होता है जिसमें प्रत्येक शीर्ष को एक अद्वितीय नाम दिया जाता है। n शीर्ष  वाले नामपत्रण वाले ट्री के शीर्ष को सामान्यतः नाम 1, 2, ..., n दिए जाते हैं। एक आवर्ती ट्री एक नामपत्रण वाला रूटेड ट्री होता है, जहां शीर्ष की नाम ट्री-क्रम का सम्मान करती हैं (अर्थात, यदि u और v दो शीर्ष   हैं और u < v है, तो u का नाम v के नाम से छोटा होता है)।
-जड़ वाले वृक्ष             में, शीर्ष का जनक {{mvar|v}} शीर्ष से जुड़ा है {{mvar|v}} पथ पर (आरेख            ़ सिद्धांत) जड़              पर; प्रत्येक शीर्ष का एक विशिष्ट जनक होता है सिवाय उस जड़ के जिसका कोई जनक नहीं है।{{sfn|Bender|Williamson|2010|p=173}} एक शीर्ष का बच्चा {{mvar|v}} जिसका एक शीर्ष है {{mvar|v}} जनक है।{{sfn|Bender|Williamson|2010|p=173}} किसी शीर्ष का आरोही {{mvar|v}} कोई भी शीर्ष है जो या तो जनक है {{mvar|v}} या (पुनरावर्ती) माता-पिता का आरोही है {{mvar|v}}. एक शीर्ष का वंशज {{mvar|v}} कोई भी शीर्ष है जिसका या तो संतति है {{mvar|v}} या (पुनरावर्ती) किसी भी बच्चे का वंशज है {{mvar|v}}. एक शीर्ष के लिए एक भाई {{mvar|v}} वृक्ष             पर कोई अन्य शीर्ष है जिसके माता-पिता समान हैं {{mvar|v}}.{{sfn|Bender|Williamson|2010|p=173}} पत्ता बिना सन्तान वाला शीर्ष है।{{sfn|Bender|Williamson|2010|p=173}} आंतरिक शीर्ष वह शीर्ष है जो पत्ती नहीं है।{{sfn|Bender|Williamson|2010|p=173}}
+एक रूटेड ट्री  में, शीर्ष v का मूल -शीर्ष वह शीर्ष होता है जो मूल तक पथ पर v से जुड़ा होता है; हर शीर्ष का एक अद्वितीय मूल -शीर्ष होता है, केवल मूल का कोई मूल -शीर्ष नहीं होता है। शीर्ष  v का एक बालक एक ऐसा शीर्ष होता है जिसमें v मूल -शीर्ष होता है। [21] शीर्ष v का एक ऊर्ध्वगामी वही शीर्ष होता है जो या तो v का मूल -शीर्ष होता है या v के मूल -शीर्ष का (पुनरावृत्तिक) ऊर्ध्वगामी होता है। शीर्ष v का एक वंशज वही शीर्ष  होता है जो या तो v का बालक होता है या v के बालकों में से किसी भी बालक का (पुनरावृत्तिक) वंशज होता है। शीर्ष v के एक संबंधी शीर्ष वही शीर्ष होता है जिसका मूल -शीर्ष  v के समान होता है। पत्ती एक ऐसा शीर्ष   होता है जिसके कोई बालक नहीं होते हैं। आंतरिक शीर्ष एक शीर्ष  होता है जो पत्ती नहीं होता है।
-एक जड़ वाले वृक्ष             में एक शीर्ष की ऊंचाई उस शीर्ष से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। वृक्ष             की ऊंचाई जड़ की ऊंचाई है। किसी शीर्ष की गहराई उसके जड़              (जड़              पाथ) तक के पथ की लंबाई होती है। यह आमतौर पर विभिन्न स्व-संतुलन वाले वृक्ष            ों, विशेष रूप से AVL वृक्ष            ों के हेरफेर में आवश्यक है। जड़ की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वाले वृक्ष             (इसलिए जड़ और पत्ती दोनों) की गहराई और ऊँचाई शून्य होती है। परंपरागत रूप से, एक खाली वृक्ष             (बिना किसी कोने वाला वृक्ष            , अगर इसकी अनुमति है) की गहराई और ऊंचाई -1 होती है।
+एक रूटेड ट्री  में शीर्ष की ऊंचाई वह पथ की लंबाई होती है जो उस शीर्ष से उत्पन्न होकर पत्तियां नीचे की ओर सबसे लंबी होती है। ट्री की ऊंचाई मूल ऊंचाई होती है। शीर्ष की गहनता उसके मूल पथ की लंबाई होती है, यह विभिन्न स्व संतुलन ट्री  के संचालन में सामान्यतः आवश्यक होता है। मूल की गहनता और पत्तियों की ऊंचाई शून्य होती है, और एक ट्री जिसमें केवल एक शीर्ष  होता है इसलिए एक मूल की गहनता और ऊंचाई शून्य होती है। पारंपरिक रूप से, एक खाली ट्री की गहनता और ऊंचाई -1 होती है।
-एक के-आर्य वृक्ष |{{mvar|k}}-आर्य वृक्ष एक जड़ वाला वृक्ष है जिसमें प्रत्येक शीर्ष पर अधिकतम होता है {{mvar|k}} बच्चे।<ref>See {{cite web|url=http://xlinux.nist.gov/dads/HTML/karyTree.html|title=k-ary tree|last=Black|first=Paul E.|date=4 May 2007|publisher=U.S. National Institute of Standards and Technology|access-date=8 February 2015}}</ref> 2-एरी वृक्ष            ों को अक्सर [[बाइनरी ट्री]] कहा जाता है, जबकि 3-एरी वृक्ष            ों को कभी-कभी [[ त्रिगुट वृक्ष ]] कहा जाता है।
+k-आरी ट्री एक रूटेड ट्री होता है जिसमें प्रत्येक शीर्ष के अधिकतम k बालक होते हैं। 2-अरि ट्री को सामान्यतः बाइनरी ट्री कहा जाता है, जबकि 3-अरि ट्री को कभी-कभी त्रिधातु ट्री कहा जाता है।
-=== {{anchor|Plane tree}} आदेश दिया गया वृक्ष            ===
+=== क्रमित ट्री        ===
-एक आदेशित वृक्ष (या समतल वृक्ष) एक जड़ वाला वृक्ष है जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया जाता है।{{sfn|Bender|Williamson|2010|p=173}}<ref>{{citation|title=Enumerative Combinatorics, Vol. I|volume=49|series=Cambridge Studies in Advanced Mathematics|first=Richard P.|last=Stanley|author-link=Richard P. Stanley|publisher=Cambridge University Press|year=2012|isbn=9781107015425|page=573|url=https://books.google.com/books?id=0wmJntp8IBQC&pg=PA573}}</ref> इसे प्लेन ट्री कहा जाता है क्योंकि चिल्ड्रन का क्रम प्लेन में ट्री के एंबेडिंग के बराबर होता है, जिसमें जड़              सबसे ऊपर होता है और प्रत्येक वर्टेक्स के चिल्ड्रेन उस वर्टेक्स से नीचे होते हैं। विमान में जड़ वाले वृक्ष             की एम्बेडिंग को देखते हुए, यदि कोई बच्चों की दिशा को ठीक करता है, तो बाएं से दाएं कहें, तो एक एम्बेडिंग बच्चों का आदेश देता है। इसके विपरीत, एक आदेश दिया गया वृक्ष             दिया गया है, और परंपरागत रूप से शीर्ष पर जड़ खींच रहा है, फिर एक आदेशित वृक्ष             में बच्चे के कोने को बाएं से दाएं खींचा जा सकता है, जो अनिवार्य रूप से अद्वितीय प्लानर एम्बेडिंग प्रदान करता है।
+क्रमबद्ध ट्री एक रूटेड ट्री  है जिसमें प्रत्येक शीर्ष के उत्तराधिकारियों के लिए एक क्रमबद्धता निर्दिष्ट की जाती है। इसे "प्लेन ट्री " कहा जाता है क्योंकि उत्तराधिकारियों की क्रमबद्धता, ट्री  को समतल में संपुट करने के समान होती है, जहां मूल ऊपर होता है और प्रत्येक शीर्ष  के उत्तराधिकारी उस शीर्ष  से नीचे होते हैं। विमान में रूट वाले ट्री  की संपुटन को देखते हुए, यदि कोई उत्तराधिकारियों की दिशा को ठीक करता है,  बाएं से दाएं कहें, तो एक संपुटन उत्तराधिकारियों को आदेश देता है। इसके विपरीत, एक आदेश दिया गया ट्री  दिया गया है, और परंपरागत रूप से शीर्ष पर रूट खींच रहा है, फिर एक आदेशित ट्री  में बच्चे के कोने को बाएं से दाएं खींचा जा सकता है, जो अनिवार्य रूप से अद्वितीय योजनाकार संपुटन प्रदान करता है।
 == गुण ==
-* हर वृक्ष             एक द्विदलीय आरेख             है। एक आरेख             द्विदलीय है यदि और केवल यदि इसमें विषम लंबाई का कोई चक्र नहीं है। चूँकि एक वृक्ष             में कोई चक्र नहीं होता है, यह द्विदलीय होता है।
+*प्रत्येक ट्री द्विभाज्य आरेख होता है। एक आरेख द्विभाज्य होता है यदि और केवल यदि इसमें विषम लंबाई के चक्र सम्मिलित नहीं हैं। क्योंकि ट्री में कोई चक्र ही नहीं होता है, इसलिए यह द्विभाज्य होता है।
-* केवल [[ गणनीय सेट ]] कई वर्टिकल वाला हर वृक्ष             एक [[प्लेनर ग्राफ|प्लेनर आरेख]]             है।
+* केवल गणनीय संख्या में शीर्ष वाले प्रत्येक ट्री एक समतली आलेख होता है।
-* प्रत्येक जुड़ा हुआ आरेख             G एक फैले हुए वृक्ष             (गणित) को स्वीकार करता है, जो एक ऐसा वृक्ष             है जिसमें G का प्रत्येक शीर्ष होता है और जिसके किनारे G के किनारे होते हैं। अधिक विशिष्ट प्रकार के फैले हुए वृक्ष            , प्रत्येक जुड़े परिमित आरेख             में मौजूद होते हैं, जिनमें गहराई-पहले खोज वृक्ष             शामिल हैं और चौड़ाई-पहले खोज वृक्ष            । [[गहराई-पहली खोज]] के अस्तित्व को सामान्य करते हुए, केवल काउंटेबल सेट के साथ हर जुड़े आरेख             में कई वर्टिकल में एक ट्रैमॉक्स ट्री होता है।{{sfnp|Diestel|2005|loc=Prop. 8.2.4}} हालाँकि, कुछ [[बेशुमार सेट]] आरेख            ़ में ऐसा कोई वृक्ष             नहीं होता है।{{sfnp|Diestel|2005|loc=Prop. 8.5.2}}
+*प्रत्येक जुड़ा हुआ आरेख G में एक स्पैनिंग ट्री होता है, जो G के हर शीर्ष को सम्मिलित करता है और जिसकी एज़ भी G की एज़ होती हैं। अधिक विशिष्ट प्रकार के फैले हुए ट्री प्रत्येक जुड़े परिमित आरेख में विद्यमान हैं, इसमें गहराई-पहले खोज ट्री और चौड़ाई-पहले खोज ट्री सम्मिलित हैं डेप्थ-फर्स्ट-सर्च ट्री के अस्तित्व का सामान्यीकरण करते हुए, हर जुड़े हुए आरेख में केवल गिने-चुने शीर्ष के साथ ट्रेमॉक्स का ट्री होता है यद्यपि कुछ असंख्य आरेखों में ऐसा कोई ट्री नहीं होता है।
-* प्रत्येक परिमित वृक्ष n शीर्षों के साथ, साथ {{nowrap|''n'' > 1}}, कम से कम दो टर्मिनल शीर्ष (पत्तियां) हैं। पत्तों की यह न्यूनतम संख्या [[पथ ग्राफ|पथ आरेख]]            ़ की विशेषता है; अधिकतम संख्या, {{nowrap|''n'' − 1}}, केवल [[स्टार ग्राफ|स्टार आरेख]]            ़ द्वारा प्राप्त किया जाता है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
+*n > 1 के साथ n शीर्ष वाले हर परिमित ट्री  में कम से कम दो टर्मिनल शीर्ष   (पत्ते) होते हैं। पत्तों की यह न्यूनतम संख्या पथ आरेख  की विशेषता है; अधिकतम संख्या, n − 1, केवल स्टार आरेख द्वारा प्राप्त की जाती है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
-* एक वृक्ष             में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख            ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक वृक्ष             में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हर वृक्ष             एक [[माध्यिका ग्राफ|माध्यिका आरेख]]             होता है।
-* हर वृक्ष             का एक [[ग्राफ केंद्र|आरेख             केंद्र]] होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक एन-वर्टेक्स ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में वर्टेक्स को हटाने से ट्री को n/2 वर्टिकल से कम के सबट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से वृक्ष ठीक n/2 शीर्षों के दो उपवृक्षों में विभाजित हो जाता है।
+* ट्री में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक ट्री में हर तीन शीर्ष में एक अद्वितीय माध्यिका होती है, हर ट्री एक माध्यिका आरेख होता है।
+* हर ट्री का एक केंद्र होता है जिसमें एक शीर्ष या दो आसन्न शीर्ष होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक n शीर्ष ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न शीर्ष होते हैं। पहले मामले में शीर्ष को हटाने से ट्री को n/2 शीर्ष से कम के सब ट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से ट्री ठीक n/2 शीर्षों के दो उप ट्री में विभाजित हो जाता है।
 == गणना ==
-=== लेबल वाले वृक्ष            ===
+=== नाम वाले ट्री        ===
-केली के सूत्र में कहा गया है कि हैं {{math|''n''{{sup|''n''−2}}}} वृक्ष             पर {{mvar|n}} लेबल वाले शीर्ष। एक क्लासिक प्रूफ प्रुफर अनुक्रम का उपयोग करता है, जो स्वाभाविक रूप से एक मजबूत परिणाम दिखाता है: शीर्ष वाले वृक्ष            ों की संख्या {{math|1, 2, …, ''n''}} डिग्री {{math|''d''{{sub|1}}, ''d''{{sub|2}}, …, ''d{{sub|n}}''}} क्रमशः [[बहुपद प्रमेय]] है
+केली का सूत्र कहता है कि n लेबल वाले शीर्ष   पर nn−2 ट्री होते हैं। प्रूफर क्रम का उपयोग करके एक प्रसिद्ध सिद्धांत का प्रमाण दिया जाता है, जो स्वतः ठोस परिणाम दिखाता है: d1, d2, ..., dn डिग्री वाले 1, 2, ..., n शीर्ष की ट्री की संख्या प्रतिस्थापनीय संख्या होती है।
 : <math>{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.</math>
-एक अधिक सामान्य समस्या एक अप्रत्यक्ष आरेख             में फैले हुए वृक्ष            ों की गिनती करना है, जिसे [[मैट्रिक्स ट्री प्रमेय]] द्वारा संबोधित किया जाता है। (केली का सूत्र एक पूर्ण आरेख             में [[फैले पेड़|फैले वृक्ष]]            ों का विशेष मामला है।) आकार की परवाह किए बिना सभी उप-वृक्षों को गिनने की समान समस्या सामान्य स्थिति में शार्प-पी-पूर्ण|#पी-पूर्ण है ({{harvtxt|Jerrum|1994}}).
+एक और सामान्य समस्या है अविचालित आरेख में स्पैनिंग ट्री की गणना करना, जिसे मैट्रिक्स ट्री सूत्र द्वारा संबोधित किया जाता है। (केली का सूत्र पूर्ण आरेख में स्पैनिंग ट्री के विशेष स्थिति हैं।) आकार के अतिरिक्त सभी उप-ट्री की गणना करने की समान समस्या सामान्य स्थिति में P-पूर्ण होती है  ({{harvtxt|Jerrum|1994}}).
-=== बिना लेबल वाले वृक्ष            ===
+=== बिना नाम  वाले ट्री        ===
-बिना लेबल वाले मुक्त वृक्ष            ों की संख्या गिनना एक कठिन समस्या है। संख्या के लिए कोई बंद सूत्र नहीं {{math|''t''(''n'')}} वृक्ष            ों के साथ {{mvar|n}} आरेख             समाकृतिकता [[तक]] शीर्ष ज्ञात है। के पहले कुछ मान {{math|''t''(''n'')}} हैं
+अविलेखित मुक्त ट्री की संख्या की गणना करना एक कठिन समस्या है। n शीर्ष वाले ट्री की संख्या t(n), आरेख समाकृतिकता के प्रति कोई समाप्त सूत्र ज्ञात नहीं है।
-: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … {{OEIS|A000055}}.
+: 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … .
-{{harvtxt|Otter|1948}} स्पर्शोन्मुख अनुमान सिद्ध किया
+टी(एन) के पहले कुछ मान हैं(ओईआईएस में)।ओटर (1948) ने उपगामी अनुमान को सिद्ध किया
 : <math>t(n) \sim C \alpha^n n^{-5/2} \quad\text{as } n\to\infty,</math>
-साथ {{math|''C'' ≈ 0.534949606...}} और {{math|''α'' ≈ 2.95576528565...}} {{OEIS|A051491}}. यहां ही {{math|~}} चिह्न का अर्थ है
+साथ ही {{math|''C'' ≈ 0.534949606...}} और {{math|''α'' ≈ 2.95576528565...}} . यहां  {{math|~}} चिह्न का अर्थ है
 :<math>\lim_{n \to \infty} \frac{t(n)}{C \alpha^n n^{-5/2} } = 1.</math>
-यह संख्या के लिए उनके विषम अनुमान का परिणाम है {{math|''r''(''n'')}} बिना लेबल वाले जड़ वाले वृक्ष             {{mvar|n}} कोने:
+यह n सिरों वाले बिना लेबल वाले रूट वाले ट्री की संख्या r(n) के लिए उनके स्पर्शोन्मुख अनुमान का परिणाम है
 : <math>r(n) \sim D\alpha^n n^{-3/2} \quad\text{as } n\to\infty,</math>
-साथ {{math|D ≈ 0.43992401257...}} और एक सा {{mvar|α}} ऊपर के रूप में (cf. {{harvtxt|Knuth|1997}}, बच्चू। 2.3.4.4 और {{harvtxt|Flajolet|Sedgewick|2009}}, बच्चू। VII.5, पी। 475)।
+साथ {{math|D ≈ 0.43992401257...}} और उपरोक्त के समान a (सी एफ नुथ (1997)अध्याय 2.3.4.4 और
-के पहले कुछ मान {{math|''r''(''n'')}} हैं<ref>See {{harvtxt|Li|1996}}.</ref>
+r(n) के पहले कुछ मान हैं<ref>See {{harvtxt|Li|1996}}.</ref>
-: 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … {{OEIS|A000081}}
+: 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …
-== वृक्ष            ों के प्रकार ==
+== ट्री के प्रकार ==
-* एक पथ आरेख             (या रैखिक आरेख            ) के होते हैं {{mvar|n}} शीर्षों को एक पंक्ति में व्यवस्थित किया जाता है, ताकि शीर्षों को {{mvar|i}} और {{math|''i'' + 1}} किनारे से जुड़े हुए हैं {{math|1=''i'' = 1, …, ''n'' – 1}}.
+*पथ आरेख  में एक पंक्ति में व्यवस्थित n शीर्ष होते हैं, जिससे i = 1, ..., n - 1 के लिए शीर्ष   i और i + 1 एक किनारे से जुड़े होते हैं।.
-* एक तारकीय वृक्ष             में एक केंद्रीय शीर्ष होता है जिसे जड़              कहा जाता है और इससे जुड़े कई पथ आरेख             होते हैं। अधिक औपचारिक रूप से, एक वृक्ष             तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
+* तारकीय ट्री में एक केंद्रीय शीर्ष होता है जिसे रूट कहा जाता है और इससे जुड़े कई पथ आरेख होते हैं। अधिक औपचारिक रूप से, एक ट्री तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
-* एक [[तारा (ग्राफ सिद्धांत)|तारा (आरेख             सिद्धांत)]] एक वृक्ष             है जिसमें एक आंतरिक शीर्ष (और {{math|''n'' – 1}} पत्तियाँ)। दूसरे शब्दों में, आदेश का एक तारा वृक्ष {{mvar|n}} व्यवस्था का वृक्ष है {{mvar|n}} अधिक से अधिक पत्तियों के साथ।
+* तारा ट्री एक ऐसा ट्री है जिसमें एक आंतरिक शीर्ष (और n - 1 पत्ते) होते हैं। दूसरे शब्दों में, n क्रम का एक तारा ट्री n क्रम का एक ट्री है, जिसमें अधिक से अधिक पत्ते होते हैं।
-* एक कैटरपिलर वृक्ष             एक ऐसा वृक्ष             है जिसमें सभी कोने एक केंद्रीय पथ सबआरेख             की दूरी 1 के भीतर हैं।
+* कैटरपिलर ट्री एक ट्री है जिसमें सभी शीर्ष एक केंद्रीय पथ उपआरेख की दूरी 1 के अंदर हैं
-* रेखांकन की एक सूची# लॉबस्टर एक वृक्ष             है जिसमें सभी शीर्ष एक केंद्रीय पथ सबआरेख             की दूरी 2 के भीतर हैं।
+* लॉबस्टर ट्री एक ऐसा ट्री है, जिसके सभी शीर्ष एक केंद्रीय पथ उपआरेख की दूरी 2 के अंदर हैं।
-* डिग्री का एक नियमित वृक्ष             {{mvar|d}} अनंत वृक्ष है {{mvar|d}} प्रत्येक शीर्ष पर किनारों। ये [[मुक्त समूह]]ों के [[केली ग्राफ|केली आरेख]]             और [[बिल्डिंग (गणित)]] के सिद्धांत के रूप में उत्पन्न होते हैं।
+* डी डिग्री का एक नियमित ट्री प्रत्येक शीर्ष पर डी किनारों वाला अनंत ट्री है। ये मुक्त समूहों के केली आरेख और टिट्स बिल्डिंग के सिद्धांत के रूप में उत्पन्न होते हैं।।
 == यह भी देखें ==
-* [[निर्णय वृक्ष]]
+* [[निर्णय वृक्ष|निर्णय ट्री]]
 * [[हाइपरट्री]]
 * [[ हॉटलाइन ]]
 * [[ छद्मवन ]]
-* वृक्ष संरचना (सामान्य)
+* ट्री संरचना (सामान्य)
 * ट्री (डेटा संरचना)
-* बिना जड़ वाला बाइनरी ट्री
+* बिना रूट वाला बाइनरी ट्री
 ==टिप्पणियाँ==
@@ Line 182: / Line 183: @@
 {{Authority control}}
-[[Category: पेड़ (ग्राफ सिद्धांत)|*]] [[Category: द्विदलीय रेखांकन]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Commons category link is locally defined]]
 [[Category:Created On 05/05/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:द्विदलीय रेखांकन]]
+[[Category:पेड़ (ग्राफ सिद्धांत)|*]]

Anonymous

Search

ट्री (ग्राफ सिद्धांत): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:17, 10 June 2023

Contents

परिभाषाएँ

ट्री