ट्री (ग्राफ सिद्धांत): 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

Revision as of 13:49, 24 May 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-पथ के अंत में इसट्री के ट्री -क्रम में तुल्यात्मक हैं मूलबद्धट्री , जो प्रायः प्रत्येक शीर्ष पर पड़ने वाले पड़ोसियों के आदेश जैसी अतिरिक्त संरचना के साथ होता है, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; इसे ट्री डेटा संरचना कहा जाता है।

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

एक लेबलबद्धट्री एकट्री होती है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। एन शीर्ष वाले एक लेबलबद्धट्री के शीर्षों को सामान्यतः लेबल 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 शीर्ष ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में शीर्ष को हटाने से ट्री को n/2 शीर्ष से कम के सबट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से ट्री ठीक n/2 शीर्षों के दो उपट्री ों में विभाजित हो जाता है।

गणना

लेबल वाले ट्री

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

{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, … .

Otter (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.

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

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

साथ $D \approx 0.43992401257...$ और एक सा $α$ ऊपर के रूप में

के पहले कुछ मान $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}}एक वन एक ऐसा अनुक्रमित आरेख होता है जिसमें किसी भी दो शीर्ष को अधिकतम एक ही पथ से युग्मित किया जाता है, या समरूपतः एक अचक्रीय निर्देशित आरेख होता है, या समरूपतः ट्री के वियोगीय संघ का एकीकृत संयोजन होता है।
-एक पॉली वृक्ष या निर्देशित वृक्ष एक निर्देशित अचक्रीय ग्राफ होता है, जिसका अंशीय अनिर्देशित ग्राफ एक पेड़ होता है। एक पॉलीफ़ॉरेस्ट या निर्देशित वन एक निर्देशित अचक्रीय ग्राफ होता है, जिसका अंशीय अनिर्देशित ग्राफ एक वन होता है।
+एक पॉलीट्री (या निर्देशित ट्री, या अभिविन्यासित ट्री, या एकलत्रिंशक नेटवर्क) एक ऐसा निर्देशित अक्रांत आरेख (डीएजी ) होता है, जिसका अंतर्निहित अनिर्देशित ग्राफ एक ट्री होता है एक पॉली वन (या निर्देशित वन या अभिविन्यासित वन) एक ऐसा निर्देशित अक्रांत आरेख  होता है, जिसका अंतर्निहित अनिर्देशित आरेख एक वन होता है।
-कंप्यूटर विज्ञान में "पेड़" के रूप में संदर्भित विभिन्न प्रकार के [[डेटा संरचनाएं]] ग्राफ थ्योरी में पेड़ होते हैं, यद्यपि ऐसे डेटा संरचनाएं सामान्यतः मूल रूप से जड़ी हुई पेड़ होती हैं। जिसे संचालित जड़ वृक्ष कहा जाता है, या तो इसके सभी सीधे बाएं तरफ दिखाने के लिए संचालित किया जाता है, एक जड़ी हुई पेड़ निर्देशित भी हो सकती है, जिसे "निर्देशित जड़ी हुई पेड़" कहा जाता है, जिसमें इसके सभी संबंधों को मूल से दूसरे वर्तमान तक दिखाता है, जिसे इस स्थिति में "वृक्षनी" या "आउट-ट्री" कहा जाता है या इसके सभी संबंधों को मूल की ओर दिखाता है - जिसे इस स्थिति में "विरोधी-वृक्षनी या "इन-ट्री" कहा जाता है। जिसे निर्देशित जड़ वाले वन कहा जाता है। जब हर जड़ वालेवृक्ष के सभी एज जड़ से दूर दिखाई देते हैं, तब उसे एक शाखन' या बाहरी-वन कहा जाता है। या इसके सभी किनारों को बनाना प्रत्येक जड़ वाले वृक्ष में जड़ की ओर इंगित करते हैं, इस विषय में इसे शाखा-विरोधी या वन कहा जाता है।
+कम्प्यूटर विज्ञान में ट्री के रूप में उल्लिखित विभिन्न प्रकार के डेटा संरचनाएं आरेख सिद्धांत में ट्री होते हैं, यद्यपि ऐसी डेटा संरचनाएं सामान्यतः रूटड ट्री होती हैं। रूटेड ट्री निर्देशित भी हो सकता है, जिसे निर्देशित रूटेड ट्री  कहा जाता है। इसमें सभी संबंध जड़ को जड़ से दूर दिखाते हैं - जिसे इस स्थिति में वृक्षता  या आउट-ट्री कहा जाता है -कुछ लेखकों ने रूटेड ट्री को स्वयं निर्देशित आरेख के रूप में परिभाषित किया है।
+रूटेड वन एक रूटेड ट्री के असंयोजित संघ है। रूटेड वन निर्देशित भी हो सकता है, जिसे निर्देशित रूटेड वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध जड़ को जड़ से दूर दिखाते हैं, तो उसे एक ब्रांचिंग या आउट-वन कहा जाता है। यदि प्रत्येक रूटेड ट्री में सभी संबंध जड़ को जड़ की ओर संकेत करते हैं, तो उसे एक एंटी-ब्रांचिंग या इन-वन कहा जाता है।
+<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}}  चक्रीय है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) |शीर्ष]] G में जोड़ा जाता है तो एक सरल चक्र बनता है।
+* {{mvar|G}}  चक्रीय है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) |शीर्ष]] G में युग्मित किया       जाता है तो एक सरल चक्र बनता है।
 * {{mvar|G}} जुड़ा हुआ है, परंतु यदि {{mvar|G}} से किसी एक शीर्ष को हटा दिया जाए तो यह असंगत हो जाएगा।
 * {{mvar|G}}  जुड़ा हुआ है और 3-शीर्ष पूर्ण आरेख K3 {{mvar|G}} का लघु नहीं है।
-* G में किन्हीं भी दो शीर्षों को एक अद्वितीय सरल पथ से जोड़ा जा सकता है।
+* G में किन्हीं भी दो शीर्षों को एक अद्वितीय सरल पथ से युग्मित किया       जा सकता है।
 यदि G के बहुत से शीर्ष हैं, उनमें से n मान लीजिए,तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:
 * {{mvar|G}} जुड़ा हुआ है और है {{math|''n'' − 1}} शीर्ष है।
 * {{mvar|G}} जुड़ा हुआ है, और हर [[सबग्राफ (ग्राफ थ्योरी)|उपआरेख]] का {{mvar|G}} शून्य या एक घटना शीर्षों के साथ कम से कम एक शीर्ष सम्मिलित है।
 * G का कोई सरल चक्र नहीं है और इसमें n − 1 शीर्ष  है।
-आरेख  सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख को सामान्यतः एक वृक्ष नहीं माना जाता है,जबकि यह रिक्त रूप से एक आरेख के रूप में जुड़ा हुआ है, बीजगणितीय टोपोलॉजी में यह 0-सम्बद्ध नहीं है,अरिक्‍त पंक्‍तिवृक्ष के विपरीत, और "शीर्षों के सापेक्ष में एक और शीर्ष" संबंध का उल्लंघन करता है। यद्यपि, इसे शून्य वृक्ष वाला जंगल माना जा सकता है।,
+आरेख  सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख को सामान्यतः एक ट्री         नहीं माना जाता है,जबकि यह रिक्त रूप से एक आरेख के रूप में जुड़ा हुआ है, बीजगणितीय टोपोलॉजी में यह 0-सम्बद्ध नहीं है,अरिक्‍त पंक्‍तिट्री         के विपरीत, और "शीर्षों के सापेक्ष में एक और शीर्ष" संबंध का उल्लंघन करता है। यद्यपि, इसे शून्य ट्री         वाला जंगल माना जा सकता है।,
-एक आंतरिक शीर्ष् कम से कम 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>
+एक आंतरिक शीर्ष् कम से कम 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>
 ===वन ===
-एक वन एक अविन्यास आरेख है जिसमें मात्र दो शीर्ष एक ही मार्ग से जुड़े हुए होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय आरेख है, जिसके सभी जुड़े घटक वृक्ष हैं; दूसरे शब्दों में, आरेख  में वृक्ष के आरेख का एक असम्बद्ध संघ होता है। विशेष रूप से, शून्य आदेश वाली आरेख एक एकल वृक्ष, और एक धार रहित आरेख वन के उदाहरण हैं। हर एक वृक्ष के लिए V - E = 1 होने के कारण, हम आसानी से एक वन में उपस्थित वृक्षों की संख्या को कुल शीर्ष और कुल एज के अंतर को घटाकर निकाल सकते हैं। {{math|1=''TV'' − ''TE'' =}} वन में वृक्षो की संख्या है।
+एक वन एक अविन्यास आरेख है जिसमें मात्र दो शीर्ष एक ही मार्ग से जुड़े हुए होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय आरेख है, जिसके सभी जुड़े घटक ट्री         हैं; दूसरे शब्दों में, आरेख  में ट्री         के आरेख का एक असम्बद्ध संघ होता है। विशेष रूप से, शून्य आदेश वाली आरेख एक एकल ट्री        , और एक धार रहित आरेख वन के उदाहरण हैं। हर एक ट्री         के लिए V - E = 1 होने के कारण, हम आसानी से एक वन में उपस्थित ट्री        ों की संख्या को कुल शीर्ष और कुल एज के अंतर को घटाकर निकाल सकते हैं। {{math|1=''TV'' − ''TE'' =}} वन में ट्री        ो की संख्या है।
-=== पॉलीवृक्ष           ===
+=== पॉलीट्री        ===
-एक पॉलीवृक्ष या निर्देशित वृक्ष एक निर्देशित अविसारण आरेख (डीएजी) होता है जिसका अंतर्निहित अविन्यासी आरेख एक वृक्ष होता है। दूसरे शब्दों में, यदि हक धारित एजों को अविधारित एजों से बदल दें, तो हम एक अविधारित आरेख प्राप्त करते हैं जो संयुक्त और अचक्रीय दोनों होता है।दू सरे शब्दों में, यदि हम इसकी निर्दिष्ट धाराएं अविन्यस्त धाराओं में बदल दें, तो हम एक अविन्यस्त आरेख प्राप्त करते है ।
+एक पॉलीट्री         या निर्देशित ट्री         एक निर्देशित अविसारण आरेख (डीएजी) होता है जिसका अंतर्निहित अविन्यासी आरेख एक ट्री         होता है। दूसरे शब्दों में, यदि हक धारित एजों को अविधारित एजों से बदल दें, तो हम एक अविधारित आरेख प्राप्त करते हैं जो संयुक्त और अचक्रीय दोनों होता है।दू सरे शब्दों में, यदि हम इसकी निर्दिष्ट धाराएं अविन्यस्त धाराओं में बदल दें, तो हम एक अविन्यस्त आरेख प्राप्त करते है ।
-कुछ लेखक वाक्यांश निर्देशित वृक्ष को उस विषय तक सीमित करें जहां शीर्षों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है
+कुछ लेखक वाक्यांश निर्देशित ट्री         को उस विषय तक सीमित करें जहां शीर्षों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है
 === पॉलीवन ===
@@ Line 54: / Line 57: @@
 कुछ लेखक"निर्देशित वन" शब्द अपने सीमित अर्थ में प्रयोग करते हैं, जहां प्रत्येक जुड़े हुए घटक की सभी संयुक्त तत्व एक विशिष्ट शिखर की ओर निर्देशित होते हैं या एक विशिष्ट शिखर से सभी दिशाओं में निर्देशित होते हैं।
-=== जड़ वाला वृक्ष            ===
+=== रूट      वाला ट्री        ===
-एक जड़ी हुई पेड़ एक ऐसी पेड़ होती है जिसमें एक शीर्ष को मूल निर्धारित किया गया होता है। जड़ी हुई पेड़ के संबंधों को प्राकृतिक निर्देश दिया जा सकता है, या तो मूल से दूर या मूल की ओर, जिसके कारण संरचना एक निर्देशित जड़ी हुई पेड़ बन जाती है। जब एक निर्देशित जड़ी हुई पेड़ का मूल से दूर की ओर एक निर्देश होता है, तो उसे "वृक्षनी" या "आउट-ट्री कहा जाता है; जब उसमें मूल की ओर की एक निर्देश होती है, तो उसे "विरोधी-वृक्षनी" या "इन-ट्री कहा जाता है। पेड़ का क्रम एक आंशिक क्रमण है जो पेड़ के शीर्ष पर लगाया जाता है, जहां u < v तभी होता है जब मूल से v तक का अद्वितीय पथ u से गुजरता हो। एक ग्राफ G का उप-ग्राफ होने वाला मूलबद्ध पेड़ T एक साधारण पेड़ है यदि G में हर T-पथ के अंत में इस पेड़ के वृक्ष-क्रम में तुल्यात्मक हैं मूलबद्ध पेड़, जो प्रायः प्रत्येक शीर्ष पर पड़ने वाले पड़ोसियों के आदेश जैसी अतिरिक्त संरचना के साथ होता है, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; इसे ट्री डेटा संरचना कहा जाता है।
+एक रूट     ी हुईट्री         एक ऐसीट्री         होती है जिसमें एक शीर्ष को मूल निर्धारित किया गया होता है। रूट     ी हुईट्री         के संबंधों को प्राकृतिक निर्देश दिया जा सकता है, या तो मूल से दूर या मूल की ओर, जिसके कारण संरचना एक निर्देशित रूट     ी हुईट्री         बन जाती है। जब एक निर्देशित रूट     ी हुईट्री         का मूल से दूर की ओर एक निर्देश होता है, तो उसे "ट्री        नी" या "आउट-ट्री कहा जाता है; जब उसमें मूल की ओर की एक निर्देश होती है, तो उसे "विरोधी-ट्री        नी" या "इन-ट्री कहा जाता है।ट्री         का क्रम एक आंशिक क्रमण है जोट्री         के शीर्ष पर लगाया जाता है, जहां u < v तभी होता है जब मूल से v तक का अद्वितीय पथ u से गुजरता हो। एक आरेख        G का उप-आरेख        होने वाला मूलबद्धट्री         T एक साधारणट्री         है यदि G में हर T-पथ के अंत में इसट्री         के ट्री        -क्रम में तुल्यात्मक हैं मूलबद्धट्री        , जो प्रायः प्रत्येक शीर्ष पर पड़ने वाले पड़ोसियों के आदेश जैसी अतिरिक्त संरचना के साथ होता है, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; इसे ट्री डेटा संरचना कहा जाता है।
-जहां पेड़ों को सामान्यतः मूल रूप में होता है, बिना किसी निर्दिष्ट मूल के पेड़ को "मुक्त पेड़" कहा जाता है।
+जहांट्री        ों को सामान्यतः मूल रूप में होता है, बिना किसी निर्दिष्ट मूल केट्री         को "मुक्तट्री        " कहा जाता है।
-एक लेबलबद्ध पेड़ एक पेड़ होती है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। एन शीर्ष वाले एक लेबलबद्ध पेड़ के शीर्षों को सामान्यतः लेबल 1, 2, ..., n दिए जाते हैं। एक आपसी रूप से जुड़ी पेड़ एक लेबलबद्ध मूलबद्ध पेड़ होती है जहां शीर्ष  लेबल वृक्ष-क्रम का पालन करते हैं अर्थात, यदि u और v दो शीर्ष के लिए u < v है, तो u का लेबल v के लेबल से छोटा होता है
+एक लेबलबद्धट्री         एकट्री         होती है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। एन शीर्ष वाले एक लेबलबद्धट्री         के शीर्षों को सामान्यतः लेबल 1, 2, ..., n दिए जाते हैं। एक आपसी रूप से जुड़ीट्री         एक लेबलबद्ध मूलबद्धट्री         होती है जहां शीर्ष  लेबल ट्री        -क्रम का पालन करते हैं अर्थात, यदि u और v दो शीर्ष के लिए u < v है, तो u का लेबल v के लेबल से छोटा होता है
-एक मूलबद्ध पेड़ में, एक शीर्ष v का माता-पिता वह शीर्ष होता है जो v को मूल की ओर जाने वाले पथ पर v से जुड़ा होता है; प्रत्येक शीर्ष का एक अद्वितीय माता-पिता होता है केवल मूल के लिए जो कोई माता-पिता नहीं होता है। एक शीर्ष v का एक बालक शीर्ष वह शीर्ष होता है जिसका v माता-पिता होता है। एक शीर्ष v का एक आगे का शीर्ष वह शीर्ष होता है जो या तो v का माता-पिता होता है या v के माता-पिता का पुनरावृत्तिक रूप से आगे का शीर्ष होता है।. एक शीर्ष v का एक वंशज वह शीर्ष होता है जो या तो v का बालक होता है या v के बालकों में से किसी एक का  वंशज होता है। शीर्ष v का एक सहोदर वह कोई अन्य शीर्ष होता है जो पेड़ में v के समान माता-पिता रखता है। एक पत्ती एक ऐसा शीर्ष है जिसके कोई बालक नहीं होते हैं।  एक आंतरिक शीर्ष एक शीर्ष होता है जो पत्ती नहीं होता है।
+एक मूलबद्धट्री         में, एक शीर्ष v का माता-पिता वह शीर्ष होता है जो v को मूल की ओर जाने वाले पथ पर v से जुड़ा होता है; प्रत्येक शीर्ष का एक अद्वितीय माता-पिता होता है केवल मूल के लिए जो कोई माता-पिता नहीं होता है। एक शीर्ष v का एक बालक शीर्ष वह शीर्ष होता है जिसका v माता-पिता होता है। एक शीर्ष v का एक आगे का शीर्ष वह शीर्ष होता है जो या तो v का माता-पिता होता है या v के माता-पिता का पुनरावृत्तिक रूप से आगे का शीर्ष होता है।. एक शीर्ष v का एक वंशज वह शीर्ष होता है जो या तो v का बालक होता है या v के बालकों में से किसी एक का  वंशज होता है। शीर्ष v का एक सहोदर वह कोई अन्य शीर्ष होता है जोट्री         में v के समान माता-पिता रखता है। एक पत्ती एक ऐसा शीर्ष है जिसके कोई बालक नहीं होते हैं।  एक आंतरिक शीर्ष एक शीर्ष होता है जो पत्ती नहीं होता है।
-एक मूलबद्ध पेड़ में एक शीर्ष की ऊँचाई वह पथ की लंबाई होती है जो उस शीर्ष से किसी पत्ती तक सबसे लंबी होती है। पेड़ की ऊँचाई मूल की ऊँचाई होती है। एक शीर्ष का गहराई वह पथ की लंबाई होती है जो उस शीर्ष से उसके मूल तक (मूल पथ) होती है। यह सामान्यतः विभिन्न स्व-संतुलित पेड़ों, विशेष रूप से पेड़ों, के प्रबंधन में आवश्यक होता है।मूल की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वाले पेड़ में गहराई और ऊँचाई शून्य होती है। पारंपरिक रूप से, एक खाली पेड़ जहां कोई शीर्ष नहीं होते हैं, यदि ऐसा स्वीकार्य होता हो की गहराई और ऊँचाई -1 होती है।
+एक मूलबद्धट्री         में एक शीर्ष की ऊँचाई वह पथ की लंबाई होती है जो उस शीर्ष से किसी पत्ती तक सबसे लंबी होती है।ट्री         की ऊँचाई मूल की ऊँचाई होती है। एक शीर्ष का गहराई वह पथ की लंबाई होती है जो उस शीर्ष से उसके मूल तक (मूल पथ) होती है। यह सामान्यतः विभिन्न स्व-संतुलितट्री        ों, विशेष रूप सेट्री        ों, के प्रबंधन में आवश्यक होता है।मूल की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वालेट्री         में गहराई और ऊँचाई शून्य होती है। पारंपरिक रूप से, एक खालीट्री         जहां कोई शीर्ष नहीं होते हैं, यदि ऐसा स्वीकार्य होता हो की गहराई और ऊँचाई -1 होती है।
-एक k-अर पेड़ एक मूलबद्ध पेड़ होता है जिसमें प्रत्येक शीर्ष के अधिकतम k बालक होते हैं। 2-अर पेड़ को सामान्यतः बाइनरी पेड़ कहा जाता है, जबकि 3-अर पेड़ को कभी-कभी टर्नरी पेड़ कहा जाता है।
+एक k-अरट्री         एक मूलबद्धट्री         होता है जिसमें प्रत्येक शीर्ष के अधिकतम k बालक होते हैं। 2-अरट्री         को सामान्यतः बाइनरीट्री         कहा जाता है, जबकि 3-अरट्री         को कभी-कभी टर्नरीट्री         कहा जाता है।
-=== क्रमित वृक्ष            ===
+=== क्रमित ट्री        ===
-एक क्रमित पेड़ (या प्लेन पेड़) एक मूलबद्ध पेड़ होता है जिसमें प्रत्येक शीर्ष के बालकों के लिए एक क्रमबद्धता निर्धारित की गई होती है। इसे "प्लेन पेड़" कहा जाता है क्योंकि बालकों की क्रमबद्धता एक प्लेन में पेड़ को एम्बेड करने के समकक्ष होती है, जिसमें मूल ऊपर होता है और प्रत्येक शीर्ष के बालक उस शीर्ष से नीचे होते हैं। यदि एक मूलबद्ध पेड़ को एक विमुद्रीकरण में दिया गया हो और एक दिशा को स्थायी किया गया हो, जैसे बाएं से दाएं, तो एक विमुद्रीकरण बालकों की क्रमबद्धता देता है। उम्रकैद, एक क्रमित पेड़ दिया गया हो और पारंपरिक रूप से मूल को शीर्ष पर चित्रित किया गया हो, तो क्रमित पेड़ में बालक शीर्षों को बाएं से दाएं चित्रित किया जा सकता है, जिससे एक मूलतः अद्यतित समतल विमुद्रीकरण मिलता है।
+एक क्रमितट्री         (या प्लेनट्री        ) एक मूलबद्धट्री         होता है जिसमें प्रत्येक शीर्ष के बालकों के लिए एक क्रमबद्धता निर्धारित की गई होती है। इसे "प्लेनट्री        " कहा जाता है क्योंकि बालकों की क्रमबद्धता एक प्लेन मेंट्री         को एम्बेड करने के समकक्ष होती है, जिसमें मूल ऊपर होता है और प्रत्येक शीर्ष के बालक उस शीर्ष से नीचे होते हैं। यदि एक मूलबद्धट्री         को एक विमुद्रीकरण में दिया गया हो और एक दिशा को स्थायी किया गया हो, जैसे बाएं से दाएं, तो एक विमुद्रीकरण बालकों की क्रमबद्धता देता है। उम्रकैद, एक क्रमितट्री         दिया गया हो और पारंपरिक रूप से मूल को शीर्ष पर चित्रित किया गया हो, तो क्रमितट्री         में बालक शीर्षों को बाएं से दाएं चित्रित किया जा सकता है, जिससे एक मूलतः अद्यतित समतल विमुद्रीकरण मिलता है।
 == गुण ==
-*प्रत्येक पेड़ द्विभाज्य ग्राफ होता है। एक ग्राफ द्विभाज्य होता है यदि और केवल यदि इसमें विषम लंबाई के चक्र सम्मिलित नहीं हैं। क्योंकि पेड़ में कोई चक्र ही नहीं होता है, इसलिए यह द्विभाज्य होता है।
+*प्रत्येकट्री         द्विभाज्य आरेख        होता है। एक आरेख        द्विभाज्य होता है यदि और केवल यदि इसमें विषम लंबाई के चक्र सम्मिलित नहीं हैं। क्योंकिट्री         में कोई चक्र ही नहीं होता है, इसलिए यह द्विभाज्य होता है।
-* केवल गणनीय संख्या में शीर्ष वाले प्रत्येक पेड़ एक समतली आलेख होता है।
+* केवल गणनीय संख्या में शीर्ष वाले प्रत्येकट्री         एक समतली आलेख होता है।
-*प्रत्येक जुड़ा हुआ आरेख G में एक स्पैनिंग पेड़ होता है, जो G के हर शीर्ष को सम्मिलित करता है और जिसकी एज़ भी G की एज़ होती हैं। अधिक विशिष्ट प्रकार के फैले हुए पेड़, प्रत्येक जुड़े परिमित ग्राफ में विद्यमान हैं, इसमें गहराई-पहले खोज पेड़ और चौड़ाई-पहले खोज पेड़ सम्मिलित हैं डेप्थ-फर्स्ट-सर्च ट्री के अस्तित्व का सामान्यीकरण करते हुए, हर जुड़े हुए ग्राफ में केवल गिने-चुने कोने के साथ ट्रेमॉक्स का पेड़ होता है यद्यपि कुछ असंख्य आरेखों में ऐसा कोई पेड़ नहीं होता है।
+*प्रत्येक जुड़ा हुआ आरेख G में एक स्पैनिंगट्री         होता है, जो G के हर शीर्ष को सम्मिलित करता है और जिसकी एज़ भी G की एज़ होती हैं। अधिक विशिष्ट प्रकार के फैले हुएट्री        , प्रत्येक जुड़े परिमित आरेख        में विद्यमान हैं, इसमें गहराई-पहले खोजट्री         और चौड़ाई-पहले खोजट्री         सम्मिलित हैं डेप्थ-फर्स्ट-सर्च ट्री के अस्तित्व का सामान्यीकरण करते हुए, हर जुड़े हुए आरेख        में केवल गिने-चुने कोने के साथ ट्रेमॉक्स काट्री         होता है यद्यपि कुछ असंख्य आरेखों में ऐसा कोईट्री         नहीं होता है।
-*n > 1 के साथ n कोने वाले हर परिमित पेड़ में कम से कम दो टर्मिनल कोने (पत्ते) होते हैं। पत्तों की यह न्यूनतम संख्या पथ ग्राफ़ की विशेषता है; अधिकतम संख्या, n − 1, केवल स्टार ग्राफ़ द्वारा प्राप्त की जाती है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
+*n > 1 के साथ n कोने वाले हर परिमितट्री         में कम से कम दो टर्मिनल कोने (पत्ते) होते हैं। पत्तों की यह न्यूनतम संख्या पथ आरेख       ़ की विशेषता है; अधिकतम संख्या, n − 1, केवल स्टार आरेख       ़ द्वारा प्राप्त की जाती है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
-* एक पेड़ में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक ग्राफ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक पेड़ में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हर पेड़ एक माध्यिका ग्राफ होता है।
+* एकट्री         में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख       ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एकट्री         में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हरट्री         एक माध्यिका आरेख        होता है।
-* हर पेड़ का एक केंद्र होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक n शीर्ष ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में शीर्ष को हटाने से ट्री को n/2 शीर्ष से कम के सबट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से वृक्ष ठीक n/2 शीर्षों के दो उपवृक्षों में विभाजित हो जाता है।
+* हरट्री         का एक केंद्र होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक n शीर्ष ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में शीर्ष को हटाने से ट्री को n/2 शीर्ष से कम के सबट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से ट्री         ठीक n/2 शीर्षों के दो उपट्री        ों में विभाजित हो जाता है।
 == गणना ==
-=== लेबल वाले वृक्ष            ===
+=== लेबल वाले ट्री        ===
-केली के सूत्र में कहा गया है कि एन लेबल वाले कोने पर एनएन-2 पेड़ हैं। एक क्लासिक प्रूफ प्रुफर अनुक्रम का उपयोग करता है, जो स्वाभाविक रूप से एक मजबूत परिणाम दिखाता है: क्रमशः 1, 2, ..., n डिग्री d1, d2, ..., dn वाले पेड़ों की संख्या, बहुपद गुणांक है
+केली के सूत्र में कहा गया है कि एन लेबल वाले कोने पर एनएन-2ट्री         हैं। एक क्लासिक प्रूफ प्रुफर अनुक्रम का उपयोग करता है, जो स्वाभाविक रूप से एक मजबूत परिणाम दिखाता है: क्रमशः 1, 2, ..., n डिग्री d1, d2, ..., dn वालेट्री        ों की संख्या, बहुपद गुणांक है
 : <math>{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.</math>
-एक अधिक सामान्य समस्या एक अप्रत्यक्ष ग्राफ में फैले हुए पेड़ों की गिनती करना है, जिसे मैट्रिक्स ट्री प्रमेय द्वारा संबोधित किया जाता है। आकार की देखभाल किए बिना सभी उप-वृक्षों की गिनती की समान समस्या सामान्य मामले में P-पूर्ण है  ({{harvtxt|Jerrum|1994}}).
+एक अधिक सामान्य समस्या एक अप्रत्यक्ष आरेख        में फैले हुएट्री        ों की गिनती करना है, जिसे मैट्रिक्स ट्री प्रमेय द्वारा संबोधित किया जाता है। आकार की देखभाल किए बिना सभी उप-ट्री        ों की गिनती की समान समस्या सामान्य मामले में P-पूर्ण है  ({{harvtxt|Jerrum|1994}}).
-=== बिना लेबल वाले वृक्ष            ===
+=== बिना लेबल वाले ट्री        ===
-बिना लेबल वाले मुक्त पेड़ों की संख्या गिनना एक कठिन समस्या है। ग्राफ समाकृतिकता तक n शीर्षों वाले वृक्षों की संख्या t(n) के लिए कोई बंद सूत्र ज्ञात नहीं है। टी(एन) के पहले कुछ मान हैं
+बिना लेबल वाले मुक्तट्री        ों की संख्या गिनना एक कठिन समस्या है। आरेख        समाकृतिकता तक n शीर्षों वाले ट्री        ों की संख्या t(n) के लिए कोई बंद सूत्र ज्ञात नहीं है। टी(एन) के पहले कुछ मान हैं
 : 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … .
 {{harvtxt|Otter|1948}} स्पर्शोन्मुख अनुमान सिद्ध किया
@@ Line 93: / Line 96: @@
 साथ {{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}} कोने:
+यह संख्या के लिए उनके विषम अनुमान का परिणाम है {{math|''r''(''n'')}} बिना लेबल वाले रूट      वाले ट्री          {{mvar|n}} कोने:
 : <math>r(n) \sim D\alpha^n n^{-3/2} \quad\text{as } n\to\infty,</math>
 साथ {{math|D ≈ 0.43992401257...}} और एक सा {{mvar|α}} ऊपर के रूप में
@@ Line 100: / Line 103: @@
 : 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, …
-== पेड़ों के प्रकार ==
+== ट्री      ों के प्रकार ==
-*पथ ग्राफ़ (या रेखीय ग्राफ़) में एक पंक्ति में व्यवस्थित n कोने होते हैं, जिससे i = 1, ..., n - 1 के लिए कोने i और i + 1 एक किनारे से जुड़े होते हैं।.
+*पथ आरेख       ़ (या रेखीय आरेख       ़) में एक पंक्ति में व्यवस्थित n कोने होते हैं, जिससे i = 1, ..., n - 1 के लिए कोने i और i + 1 एक किनारे से जुड़े होते हैं।.
-* एक तारकीय पेड़ में एक केंद्रीय शीर्ष होता है जिसे रूट कहा जाता है और इससे जुड़े कई पथ ग्राफ होते हैं। अधिक औपचारिक रूप से, एक पेड़ तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
+* एक तारकीयट्री         में एक केंद्रीय शीर्ष होता है जिसे रूट कहा जाता है और इससे जुड़े कई पथ आरेख        होते हैं। अधिक औपचारिक रूप से, एकट्री         तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
-* एक तारा वृक्ष एक ऐसा वृक्ष है जिसमें एक आंतरिक शीर्ष (और n - 1 पत्ते) होते हैं। दूसरे शब्दों में, n क्रम का एक तारा वृक्ष n क्रम का एक वृक्ष है जिसमें अधिक से अधिक पत्ते होते हैं।
+* एक तारा ट्री         एक ऐसा ट्री         है जिसमें एक आंतरिक शीर्ष (और n - 1 पत्ते) होते हैं। दूसरे शब्दों में, n क्रम का एक तारा ट्री         n क्रम का एक ट्री         है जिसमें अधिक से अधिक पत्ते होते हैं।
-* एक कैटरपिलर पेड़ एक पेड़ है जिसमें सभी कोने एक केंद्रीय पथ उपआरेख की दूरी 1 के अंदर हैं
+* एक कैटरपिलरट्री         एकट्री         है जिसमें सभी कोने एक केंद्रीय पथ उपआरेख की दूरी 1 के अंदर हैं
-* लॉबस्टर ट्री एक ऐसा पेड़ है जिसके सभी कोने एक केंद्रीय पथ उपआरेख की दूरी 2 के  अंदर हैं।
+* लॉबस्टर ट्री एक ऐसाट्री         है जिसके सभी कोने एक केंद्रीय पथ उपआरेख की दूरी 2 के  अंदर हैं।
-* डी डिग्री का एक नियमित पेड़ प्रत्येक शीर्ष पर डी किनारों वाला अनंत पेड़ है। ये मुक्त समूहों के केली आरेख और टिट्स बिल्डिंग के सिद्धांत के रूप में उत्पन्न होते हैं।।
+* डी डिग्री का एक नियमितट्री         प्रत्येक शीर्ष पर डी किनारों वाला अनंतट्री         है। ये मुक्त समूहों के केली आरेख और टिट्स बिल्डिंग के सिद्धांत के रूप में उत्पन्न होते हैं।।
 == यह भी देखें ==
-* [[निर्णय वृक्ष]]
+* [[निर्णय वृक्ष|निर्णय ट्री]]
-* [[हाइपरट्री|हाइपरवृक्ष]]
+* [[हाइपरट्री]]
 * [[ हॉटलाइन ]]
 * [[ छद्मवन ]]
-* वृक्ष संरचना (सामान्य)
+* ट्री         संरचना (सामान्य)
-* वृक्ष  (डेटा संरचना)
+* ट्री          (डेटा संरचना)
-* बिना जड़ वाला बाइनरी वृक्ष
+* बिना रूट      वाला बाइनरी ट्री
 ==टिप्पणियाँ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 13:49, 24 May 2023

Contents

परिभाषाएँ

ट्री