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

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

एक पॉलीट्री निर्देशित अविन्यासी आरेख (डीएजी ) होता है जिसका अंशकालिक अविन्यासहीन आरेख एक वृक्ष होता है। एक पॉलीफॉरेस्ट या निर्देशित वन या उन्मुख वन एक निर्देशित चक्रीय आरेख है जिसका अंतर्निहित अप्रत्यक्ष आरेख एक वन है।

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

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

परिभाषाएँ

वृक्ष

एक वृक्ष एक अप्रत्यक्ष आरेख है $G$ जो निम्नलिखित समतुल्य शर्तों में से किसी को भी संतुष्ट करता है:

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

अगर $G$ के बहुत से शीर्ष हैं, कहते हैं {{mvar|n}उनमें से }, तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:

$G$ जुड़ा हुआ है और है $n - 1$ किनारे।
$G$ जुड़ा हुआ है, और हर सबआरेख (आरेख थ्योरी) का $G$ शून्य या एक घटना किनारों के साथ कम से कम एक शीर्ष शामिल है। (वह है, $G$ जुड़ा हुआ है और अध: पतन (आरेख सिद्धांत)|1-पतित।)
$G$ का कोई सरल चक्र नहीं है और है $n - 1$ किनारे।

आरेख ़ सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख ़ (बिना कोने वाले आरेख ़) को आम तौर पर एक वृक्ष नहीं माना जाता है: जबकि यह रिक्त रूप से एक आरेख ़ के रूप में जुड़ा हुआ है (किसी भी दो कोने को एक पथ से जोड़ा जा सकता है), यह n नहीं है एन-जुड़ा हुआ|0-कनेक्टेड (या यहां तक कि (−1)-कनेक्टेड) बीजगणितीय टोपोलॉजी में, गैर-खाली वृक्ष ों के विपरीत, और किनारों के संबंध की तुलना में एक और शीर्ष का उल्लंघन करता है। हालाँकि, इसे शून्य वृक्ष ों वाला वन माना जा सकता है।

एक internal vertex (या इनर वर्टेक्स) कम से कम 2 डिग्री (आरेख सिद्धांत) का एक वर्टेक्स है। इसी तरह, एक external vertex (या बाहरी शीर्ष, टर्मिनल शीर्ष या पत्ती) 1 डिग्री का शीर्ष है। एक वृक्ष में एक शाखा शीर्ष कम से कम 3 डिग्री का शीर्ष है।^[8] एक irreducible tree (या शृंखला-घटा हुआ वृक्ष) एक ऐसा वृक्ष है जिसमें डिग्री 2 का कोई शीर्ष नहीं है (अनुक्रम में प्रगणित A000014 OEIS में)।^[9]

वन

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

पॉलीट्री

ए polytree^[10](या निर्देशित वृक्ष ^[11] या उन्मुख वृक्ष^[12]^[13]या अकेले जुड़े नेटवर्क^[14] एक निर्देशित चक्रीय आरेख (DAG) है जिसका अंतर्निहित अप्रत्यक्ष आरेख एक वृक्ष है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख प्राप्त होता है जो जुड़ा हुआ है और अचक्रीय है।

कुछ लेखक^[who?] वाक्यांश निर्देशित ट्री को उस मामले तक सीमित करें जहां किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (अरबोरेसेंस (आरेख सिद्धांत) देखें)।

पॉलीफ़ॉरेस्ट

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

कुछ लेखक^[who?] वाक्यांश निर्देशित वन को उस मामले तक सीमित करें जहां प्रत्येक जुड़े घटक के किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (आर्बोरेसेंस (आरेख ़ सिद्धांत) देखें)।

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

ए rooted tree एक वृक्ष है जिसमें एक शीर्ष को जड़ निर्दिष्ट किया गया है।^[15] एक जड़ वाले वृक्ष के किनारों को एक प्राकृतिक अभिविन्यास दिया जा सकता है, या तो जड़ से दूर या उसकी ओर, जिस स्थिति में संरचना एक निर्देशित जड़ वाला वृक्ष बन जाती है। जब एक निर्देशित जड़ वाले वृक्ष का एक अभिविन्यास जड़ से दूर होता है, तो इसे अर्बोरेसेंस कहा जाता है^[11] या आउट-ट्री;^[2] जब इसका जड़ की ओर ओरिएंटेशन होता है, तो इसे एंटी-अर्बोरेसेंस या इन-ट्री कहा जाता है।^[2] वृक्ष-क्रम एक वृक्ष के शीर्ष पर आंशिक क्रम है $u < v$ अगर और केवल अगर जड़ से अद्वितीय पथ $v$ के माध्यम से गुजरता $u$ . एक जड़ वाला वृक्ष $T$ जो आरेख थ्योरी की शब्दावली है#कुछ आरेख के सबआरेख $G$ एक सामान्य वृक्ष है अगर हर का अंत होता है $T$ -पथ में $G$ इस ट्री-ऑर्डर में तुलनीय हैं (Diestel 2005, p. 15). जड़ वाले वृक्ष , अक्सर अतिरिक्त संरचना के साथ जैसे कि प्रत्येक शीर्ष पर पड़ोसियों को आदेश देना, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; वृक्ष डेटा संरचना देखें।

ऐसे संदर्भ में जहां वृक्ष ों की आमतौर पर जड़ होती है, बिना किसी निर्दिष्ट जड़ वाले वृक्ष को मुक्त वृक्ष कहा जाता है।

एक लेबल वाला वृक्ष एक वृक्ष है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। लेबल लगे वृक्ष के शीर्ष पर $n$ शीर्षों को आमतौर पर लेबल दिए जाते हैं $1, 2, \dots, n$ . एक पुनरावर्ती वृक्ष एक लेबल वाला जड़ वाला वृक्ष है जहाँ शीर्ष लेबल वृक्ष क्रम का सम्मान करते हैं (अर्थात, यदि $u < v$ दो शीर्षों के लिए $u$ और $v$ , फिर का लेबल $u$ के लेबल से छोटा है $v$ ).

जड़ वाले वृक्ष में, शीर्ष का जनक $v$ शीर्ष से जुड़ा है $v$ पथ पर (आरेख ़ सिद्धांत) जड़ पर; प्रत्येक शीर्ष का एक विशिष्ट जनक होता है सिवाय उस जड़ के जिसका कोई जनक नहीं है।^[15] एक शीर्ष का बच्चा $v$ जिसका एक शीर्ष है $v$ जनक है।^[15] किसी शीर्ष का आरोही $v$ कोई भी शीर्ष है जो या तो जनक है $v$ या (पुनरावर्ती) माता-पिता का आरोही है $v$ . एक शीर्ष का वंशज $v$ कोई भी शीर्ष है जिसका या तो संतति है $v$ या (पुनरावर्ती) किसी भी बच्चे का वंशज है $v$ . एक शीर्ष के लिए एक भाई $v$ वृक्ष पर कोई अन्य शीर्ष है जिसके माता-पिता समान हैं $v$ .^[15] पत्ता बिना सन्तान वाला शीर्ष है।^[15] आंतरिक शीर्ष वह शीर्ष है जो पत्ती नहीं है।^[15]

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

एक के-आर्य वृक्ष | $k$ -आर्य वृक्ष एक जड़ वाला वृक्ष है जिसमें प्रत्येक शीर्ष पर अधिकतम होता है $k$ बच्चे।^[16] 2-एरी वृक्ष ों को अक्सर बाइनरी ट्री कहा जाता है, जबकि 3-एरी वृक्ष ों को कभी-कभी त्रिगुट वृक्ष कहा जाता है।

आदेश दिया गया वृक्ष

एक आदेशित वृक्ष (या समतल वृक्ष) एक जड़ वाला वृक्ष है जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया जाता है।^[15]^[17] इसे प्लेन ट्री कहा जाता है क्योंकि चिल्ड्रन का क्रम प्लेन में ट्री के एंबेडिंग के बराबर होता है, जिसमें जड़ सबसे ऊपर होता है और प्रत्येक वर्टेक्स के चिल्ड्रेन उस वर्टेक्स से नीचे होते हैं। विमान में जड़ वाले वृक्ष की एम्बेडिंग को देखते हुए, यदि कोई बच्चों की दिशा को ठीक करता है, तो बाएं से दाएं कहें, तो एक एम्बेडिंग बच्चों का आदेश देता है। इसके विपरीत, एक आदेश दिया गया वृक्ष दिया गया है, और परंपरागत रूप से शीर्ष पर जड़ खींच रहा है, फिर एक आदेशित वृक्ष में बच्चे के कोने को बाएं से दाएं खींचा जा सकता है, जो अनिवार्य रूप से अद्वितीय प्लानर एम्बेडिंग प्रदान करता है।

गुण

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

गणना

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

↑ Bender & Williamson 2010, p. 171.
↑ ^2.0 ^2.1 ^2.2 Deo 1974, p. 207.
↑ Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0. Archived (PDF) from the original on 2015-09-08.
↑ David Makinson (2012). कम्प्यूटिंग के लिए सेट, तर्क और गणित. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.
↑ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.
↑ Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.
↑ 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].
↑ Harary & Prins 1959, p. 150.
↑ See Dasgupta (1999).
↑ ^11.0 ^11.1 Deo 1974, p. 206.
↑ See Harary & Sumner (1980).
↑ See Simion (1991).
↑ See Kim & Pearl (1983).
↑ ^15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 ^15.6 Bender & Williamson 2010, p. 173.
↑ See Black, Paul E. (4 May 2007). "k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 8 February 2015.
↑ Stanley, Richard P. (2012), Enumerative Combinatorics, Vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, p. 573, ISBN 9781107015425
↑ Diestel (2005), Prop. 8.2.4.
↑ Diestel (2005), Prop. 8.5.2.
↑ 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.

[FOOTNOTEDeo1974207-2] 2.0 ^2.1 ^2.2 Deo 1974, p. 207.

[MehlhornSanders2008-3] Kurt Mehlhorn; Peter Sanders (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer Science & Business Media. p. 52. ISBN 978-3-540-77978-0. Archived (PDF) from the original on 2015-09-08.

[Makinson2012-4] David Makinson (2012). कम्प्यूटिंग के लिए सेट, तर्क और गणित. Springer Science & Business Media. pp. 167–168. ISBN 978-1-4471-2499-3.

[5] Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 747. ISBN 978-0-07-338309-5.

[Schrijver2003-6] Alexander Schrijver (2003). Combinatorial Optimization: Polyhedra and Efficiency. Springer. p. 34. ISBN 3-540-44389-4.

[7] 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.

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

[FOOTNOTEHararyPrins1959150-9] Harary & Prins 1959, p. 150.

[d99-10] See Dasgupta (1999).

[FOOTNOTEDeo1974206-11] 11.0 ^11.1 Deo 1974, p. 206.

[Harary_1980-12] See Harary & Sumner (1980).

[s91-13] See Simion (1991).

[kp83-14] See Kim & Pearl (1983).

[FOOTNOTEBenderWilliamson2010173-15] 15.0 ^15.1 ^15.2 ^15.3 ^15.4 ^15.5 ^15.6 Bender & Williamson 2010, p. 173.

[16] See Black, Paul E. (4 May 2007). "k-ary tree". U.S. National Institute of Standards and Technology. Retrieved 8 February 2015.

[17] Stanley, Richard P. (2012), Enumerative Combinatorics, Vol. I, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, p. 573, ISBN 9781107015425

[FOOTNOTEDiestel2005Prop._8.2.4-18] Diestel (2005), Prop. 8.2.4.

[FOOTNOTEDiestel2005Prop._8.5.2-19] Diestel (2005), Prop. 8.5.2.

[20] See Li (1996).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

@@ Line 14: / Line 14: @@
 }}
-[[ ग्राफ सिद्धांत ]] में, एक पेड़ एक [[अप्रत्यक्ष ग्राफ]] है जिसमें कोई भी दो [[ शीर्ष (ग्राफ सिद्धांत) ]] द्वारा जुड़ा हुआ है {{em|exactly one}} पथ (ग्राफ़ सिद्धांत), या समकक्ष रूप से एक [[ जुड़ा हुआ ग्राफ ]]़ चक्र (ग्राफ़ सिद्धांत) अप्रत्यक्ष ग्राफ़।{{sfn|Bender|Williamson|2010|p=171}} वन एक अप्रत्यक्ष ग्राफ है जिसमें किन्हीं भी दो शीर्षों को जोड़ा जाता है {{em|at most one}} पथ, या समतुल्य रूप से एक अचक्रीय अप्रत्यक्ष ग्राफ, या समकक्ष रूप से वृक्षों के रेखांकन का एक अलग संघ।{{sfn|Bender|Williamson|2010|p=172}}
+[[ ग्राफ सिद्धांत | आरेख सिद्धांत]] में,वृक्ष एक ऐसा [[अप्रत्यक्ष ग्राफ|अविरोधी आरेख]] है जिसमें प्रत्येक दो शीर्षो को एक ही पथ या समानरूप से एक जुड़ा हुआ अविरोधी अनिर्देशित आरेख है।{{sfn|Bender|Williamson|2010|p=171}} एक वन एक अविन्यास अभिमुखीय आरेख है जिसमें किसी भी दो शीर्षो को अधिकतम एक मार्ग द्वारा जोड़ा जाता है, समानांतर रूप से एक अविन्यास अभिमुखीय आरेख  है, या समानांतर रूप से वृक्षों का असंगठित संयुक्त संघ है।
-एक [[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) है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक पेड़ है। एक पॉलीफॉरेस्ट (या निर्देशित वन या उन्मुख वन) एक निर्देशित चक्रीय ग्राफ है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक जंगल है।
+एक पॉलीट्री निर्देशित अविन्यासी आरेख (डीएजी ) होता है जिसका अंशकालिक अविन्यासहीन आरेख एक वृक्ष होता है। एक पॉलीफॉरेस्ट या निर्देशित वन या उन्मुख वन एक निर्देशित चक्रीय आरेख है जिसका अंतर्निहित अप्रत्यक्ष आरेख एक वन है।
-[[कंप्यूटर विज्ञान]] में ट्री (डेटा संरचना) के रूप में संदर्भित विभिन्न प्रकार की डेटा संरचनाओं में [[अंतर्निहित ग्राफ]]़ होते हैं जो ग्राफ़ सिद्धांत में पेड़ होते हैं, हालांकि ऐसी [[डेटा संरचनाएं]] आमतौर पर जड़ वाले पेड़ होती हैं। एक रूटेड ट्री को डायरेक्ट किया जा सकता है, जिसे डायरेक्टेड रूटेड ट्री कहा जाता है,<ref name="Williamson1985">{{cite book|author=Stanley Gill Williamson|title=कंप्यूटर साइंस के लिए कॉम्बिनेटरिक्स|year=1985|publisher=Courier Dover Publications|isbn=978-0-486-42076-9|page=288}}</ref><ref name="multi">{{cite book|author1=Mehran Mesbahi|author2=Magnus Egerstedt|title=मल्टीएजेंट नेटवर्क में ग्राफ थ्योरिटिक तरीके|year=2010|publisher=Princeton University Press|isbn=978-1-4008-3535-5|page=38}}</ref> या तो इसके सभी किनारों को जड़ से दूर करना - जिस स्थिति में इसे आर्बोरेसेंस (ग्राफ सिद्धांत) कहा जाता है{{sfn|Deo|1974|p=206}}<ref name="DuKo2011">{{cite book|author1=Ding-Zhu Du|author2=Ker-I Ko|author3=Xiaodong Hu|title=सन्निकटन एल्गोरिदम का डिजाइन और विश्लेषण|year=2011|publisher=Springer Science & Business Media|isbn=978-1-4614-1701-9|page=108}}</ref> या आउट-ट्री{{sfn|Deo|1974|p=207}}<ref name="GrossYellen2013">{{cite book|author1=Jonathan L. Gross|author2=Jay Yellen|author3=Ping Zhang|author3-link=Ping Zhang (graph theorist)|title=हैंडबुक ऑफ़ ग्राफ थ्योरी, दूसरा संस्करण|year=2013|publisher=CRC Press|isbn=978-1-4398-8018-0|page=116}}</ref>-या इसके सभी किनारों को जड़ की ओर इंगित करना-जिस स्थिति में इसे एंटी-अर्बोरेसेंस कहा जाता है<ref name="KorteVygen2012b">{{cite book|author1=Bernhard Korte|authorlink1=Bernhard Korte|author2=Jens Vygen|title=Combinatorial Optimization: Theory and Algorithms|year=2012|publisher=Springer Science & Business Media|isbn=978-3-642-24488-9|page=28|edition=5th}}</ref> या इन-ट्री।{{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> एक जड़ वाला जंगल जड़ वाले पेड़ों का एक अलग संघ है। एक रूटेड फ़ॉरेस्ट को निर्देशित किया जा सकता है, जिसे डायरेक्टेड रूटेड फ़ॉरेस्ट कहा जाता है, या तो इसके सभी किनारों को प्रत्येक जड़ वाले पेड़ में जड़ से दूर कर दिया जाता है - जिस स्थिति में इसे आर्बोरेसेंस (ग्राफ़ सिद्धांत) या आउट-फ़ॉरेस्ट कहा जाता है - या इसके सभी किनारों को बनाना प्रत्येक जड़ वाले पेड़ में जड़ की ओर इशारा करते हैं - इस मामले में इसे शाखा-विरोधी या जंगल में कहा जाता है।
+कम्प्यूटर विज्ञान में वृक्ष के रूप में संदर्भित विभिन्न प्रकार के [[डेटा संरचनाएं]] आरेख सिद्धांत में वृक्ष होते हैं,यद्यपि ऐसी डेटा संरचनाएं सामान्यतः जड़ वृक्ष होते हैं। जड़ वृक्ष संचालित हो सकता है, जिसे संचालित जड़ वृक्ष कहा जाता है, या तो इसके सभी सीधे बाएं तरफ दिखाने के लिए संचालित किया जाता है - जिसके लिए इसे एक वृक्षारूपता या बाहरी- वृक्ष कहा जाता है - या फिर इसके सभी सीधे दाएं तरफ दिखाने के लिए संचालित किया जाता है - जिसके लिए इसे प्रतिरोधी-वृक्षारूपता या आंतरिक-वृक्ष कहा जाता है।{{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 में ब्रिटिश गणितीय [[आर्थर केली]] ने किया था।
-शब्द {{em|tree}} 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>
 == परिभाषाएँ ==
-=== पेड़ ===
+=== वृक्ष            ===
-एक पेड़ एक अप्रत्यक्ष ग्राफ है {{mvar|G}} जो निम्नलिखित समतुल्य शर्तों में से किसी को भी संतुष्ट करता है:
+एक वृक्ष             एक अप्रत्यक्ष आरेख             है {{mvar|G}} जो निम्नलिखित समतुल्य शर्तों में से किसी को भी संतुष्ट करता है:
-* {{mvar|G}} जुड़ा हुआ ग्राफ और साइकिल (ग्राफ सिद्धांत) है (इसमें कोई चक्र नहीं है)।
+* {{mvar|G}} जुड़ा हुआ आरेख             और साइकिल (आरेख             सिद्धांत) है (इसमें कोई चक्र नहीं है)।
-* {{mvar|G}} एसाइक्लिक है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) ]] जोड़ा जाए तो एक साधारण चक्र बनता है {{mvar|G}}.
+* {{mvar|G}} एसाइक्लिक है, और यदि कोई [[ किनारा (ग्राफ सिद्धांत) | किनारा (आरेख             सिद्धांत)]]  जोड़ा जाए तो एक साधारण चक्र बनता है {{mvar|G}}.
-* {{mvar|G}} जुड़ा हुआ है, लेकिन कनेक्टिविटी बन जाएगा (ग्राफ़ सिद्धांत)#कनेक्टेड ग्राफ़ अगर किसी एक किनारे को हटा दिया जाता है {{mvar|G}}.
+* {{mvar|G}} जुड़ा हुआ है, लेकिन कनेक्टिविटी बन जाएगा (आरेख            ़ सिद्धांत)#कनेक्टेड आरेख            ़ अगर किसी एक किनारे को हटा दिया जाता है {{mvar|G}}.
-* {{mvar|G}} जुड़ा हुआ है और 3-वर्टेक्स पूर्ण ग्राफ़ है {{math|''K''{{sub|3}}}} का लघु (ग्राफ सिद्धांत) नहीं है {{mvar|G}}.
+* {{mvar|G}} जुड़ा हुआ है और 3-वर्टेक्स पूर्ण आरेख            ़ है {{math|''K''{{sub|3}}}} का लघु (आरेख             सिद्धांत) नहीं है {{mvar|G}}.
-* कोई भी दो कोने अंदर {{mvar|G}} को एक अद्वितीय पथ (ग्राफ सिद्धांत) द्वारा जोड़ा जा सकता है।
+* कोई भी दो कोने अंदर {{mvar|G}} को एक अद्वितीय पथ (आरेख             सिद्धांत) द्वारा जोड़ा जा सकता है।
 अगर {{mvar|G}} के बहुत से शीर्ष हैं, कहते हैं {{mvar|n}उनमें से }, तो उपरोक्त कथन निम्न में से किसी भी स्थिति के समतुल्य हैं:
 * {{mvar|G}} जुड़ा हुआ है और है {{math|''n'' − 1}} किनारे।
-* {{mvar|G}} जुड़ा हुआ है, और हर [[सबग्राफ (ग्राफ थ्योरी)]] का {{mvar|G}} शून्य या एक घटना किनारों के साथ कम से कम एक शीर्ष शामिल है। (वह है, {{mvar|G}} जुड़ा हुआ है और [[अध: पतन (ग्राफ सिद्धांत)]]|1-पतित।)
+* {{mvar|G}} जुड़ा हुआ है, और हर [[सबग्राफ (ग्राफ थ्योरी)|सबआरेख             (आरेख             थ्योरी)]] का {{mvar|G}} शून्य या एक घटना किनारों के साथ कम से कम एक शीर्ष शामिल है। (वह है, {{mvar|G}} जुड़ा हुआ है और [[अध: पतन (ग्राफ सिद्धांत)|अध: पतन (आरेख             सिद्धांत)]]|1-पतित।)
 * {{mvar|G}} का कोई सरल चक्र नहीं है और है {{math|''n'' − 1}} किनारे।
-ग्राफ़ सिद्धांत में कहीं और के रूप में, क्रम-शून्य ग्राफ़ (बिना कोने वाले ग्राफ़) को आम तौर पर एक पेड़ नहीं माना जाता है: जबकि यह रिक्त रूप से एक ग्राफ़ के रूप में जुड़ा हुआ है (किसी भी दो कोने को एक पथ से जोड़ा जा सकता है), यह n नहीं है [[एन-जुड़ा हुआ]]|0-कनेक्टेड (या यहां तक कि (−1)-कनेक्टेड) बीजगणितीय टोपोलॉजी में, गैर-खाली पेड़ों के विपरीत, और किनारों के संबंध की तुलना में एक और शीर्ष का उल्लंघन करता है। हालाँकि, इसे शून्य पेड़ों वाला जंगल माना जा सकता है।
+आरेख            ़ सिद्धांत में कहीं और के रूप में, क्रम-शून्य आरेख            ़ (बिना कोने वाले आरेख            ़) को आम तौर पर एक वृक्ष             नहीं माना जाता है: जबकि यह रिक्त रूप से एक आरेख            ़ के रूप में जुड़ा हुआ है (किसी भी दो कोने को एक पथ से जोड़ा जा सकता है), यह n नहीं है [[एन-जुड़ा हुआ]]|0-कनेक्टेड (या यहां तक कि (−1)-कनेक्टेड) बीजगणितीय टोपोलॉजी में, गैर-खाली वृक्ष            ों के विपरीत, और किनारों के संबंध की तुलना में एक और शीर्ष का उल्लंघन करता है। हालाँकि, इसे शून्य वृक्ष            ों वाला वन             माना जा सकता है।
-एक {{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>
+एक {{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>
 एक {{em|irreducible tree}} (या शृंखला-घटा हुआ वृक्ष) एक ऐसा वृक्ष है जिसमें डिग्री 2 का कोई शीर्ष नहीं है (अनुक्रम में प्रगणित {{OEIS link|A000014}} [[OEIS]] में)।{{sfn|Harary|Prins|1959|p=150}}
 ===वन ===
-ए {{em|forest}} एक अप्रत्यक्ष ग्राफ़ है जिसमें कोई भी दो कोने ज़्यादा से ज़्यादा एक रास्ते से जुड़े होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय ग्राफ है, जिसके सभी जुड़े घटक (ग्राफ सिद्धांत) पेड़ हैं; दूसरे शब्दों में, ग्राफ़ में पेड़ों के ग्राफ़ का एक असम्बद्ध संघ होता है। विशेष मामलों के रूप में, ऑर्डर-ज़ीरो ग्राफ़ (शून्य पेड़ों वाला एक जंगल), एक अकेला पेड़ और एक बिना धार वाला ग्राफ़, जंगलों के उदाहरण हैं।
+ए {{em|forest}} एक अप्रत्यक्ष आरेख            ़ है जिसमें कोई भी दो कोने ज़्यादा से ज़्यादा एक रास्ते से जुड़े होते हैं। समतुल्य रूप से, वन एक अप्रत्यक्ष चक्रीय आरेख             है, जिसके सभी जुड़े घटक (आरेख             सिद्धांत) वृक्ष             हैं; दूसरे शब्दों में, आरेख            ़ में वृक्ष            ों के आरेख            ़ का एक असम्बद्ध संघ होता है। विशेष मामलों के रूप में, ऑर्डर-ज़ीरो आरेख            ़ (शून्य वृक्ष            ों वाला एक वन            ), एक अकेला वृक्ष             और एक बिना धार वाला आरेख            ़, वन            ों के उदाहरण हैं।
-चूंकि हर पेड़ के लिए {{math|1=''V'' − ''E'' = 1}}, हम कुल शीर्षों और कुल किनारों के बीच के अंतर को घटाकर जंगल के भीतर मौजूद पेड़ों की संख्या आसानी से गिन सकते हैं। {{math|1=''TV'' − ''TE'' =}} जंगल में पेड़ों की संख्या।
+चूंकि हर वृक्ष             के लिए {{math|1=''V'' − ''E'' = 1}}, हम कुल शीर्षों और कुल किनारों के बीच के अंतर को घटाकर वन             के भीतर मौजूद वृक्ष            ों की संख्या आसानी से गिन सकते हैं। {{math|1=''TV'' − ''TE'' =}} वन             में वृक्ष            ों की संख्या।
 === पॉलीट्री ===
 {{main|Polytree}}
-ए {{em|polytree}}<ref name="d99"/>(या निर्देशित पेड़{{sfn|Deo|1974|p=206}} या उन्मुख वृक्ष<ref name="Harary 1980"/><ref name="s91"/>या अकेले जुड़े नेटवर्क<ref name="kp83"/> एक निर्देशित चक्रीय ग्राफ (DAG) है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक पेड़ है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष ग्राफ प्राप्त होता है जो जुड़ा हुआ है और अचक्रीय है।
+ए {{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}} वाक्यांश निर्देशित ट्री को उस मामले तक सीमित करें जहां किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (अरबोरेसेंस (ग्राफ सिद्धांत) देखें)।
+कुछ लेखक{{who|date=November 2021}} वाक्यांश निर्देशित ट्री को उस मामले तक सीमित करें जहां किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (अरबोरेसेंस (आरेख             सिद्धांत) देखें)।
 === पॉलीफ़ॉरेस्ट ===
-ए {{em|polyforest}} (या निर्देशित वन या उन्मुख वन) एक निर्देशित चक्रीय ग्राफ है जिसका अंतर्निहित अप्रत्यक्ष ग्राफ एक जंगल है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष ग्राफ प्राप्त होता है जो चक्रीय है।
+ए {{em|polyforest}} (या निर्देशित वन या उन्मुख वन) एक निर्देशित चक्रीय आरेख             है जिसका अंतर्निहित अप्रत्यक्ष आरेख             एक वन             है। दूसरे शब्दों में, यदि हम इसके निर्देशित किनारों को अप्रत्यक्ष किनारों से प्रतिस्थापित करते हैं, तो हमें एक अप्रत्यक्ष आरेख             प्राप्त होता है जो चक्रीय है।
-कुछ लेखक{{who|date=November 2021}} वाक्यांश निर्देशित वन को उस मामले तक सीमित करें जहां प्रत्येक जुड़े घटक के किनारों को एक विशेष शीर्ष की ओर निर्देशित किया जाता है, या सभी को एक विशेष शीर्ष से दूर निर्देशित किया जाता है (आर्बोरेसेंस (ग्राफ़ सिद्धांत) देखें)।
+कुछ लेखक{{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}}. जड़ वाले पेड़, अक्सर अतिरिक्त संरचना के साथ जैसे कि प्रत्येक शीर्ष पर पड़ोसियों को आदेश देना, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; [[वृक्ष डेटा संरचना]] देखें।
+ए {{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}}. जड़ वाले वृक्ष            , अक्सर अतिरिक्त संरचना के साथ जैसे कि प्रत्येक शीर्ष पर पड़ोसियों को आदेश देना, कंप्यूटर विज्ञान में एक महत्वपूर्ण डेटा संरचना है; [[वृक्ष डेटा संरचना]] देखें।
-ऐसे संदर्भ में जहां पेड़ों की आमतौर पर जड़ होती है, बिना किसी निर्दिष्ट जड़ वाले पेड़ को मुक्त पेड़ कहा जाता है।
+ऐसे संदर्भ में जहां वृक्ष            ों की आमतौर पर जड़ होती है, बिना किसी निर्दिष्ट जड़ वाले वृक्ष             को मुक्त वृक्ष             कहा जाता है।
-एक लेबल वाला पेड़ एक पेड़ है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। लेबल लगे पेड़ के शीर्ष पर {{mvar|n}} शीर्षों को आमतौर पर लेबल दिए जाते हैं {{math|1, 2, …, ''n''}}. एक [[पुनरावर्ती वृक्ष]] एक लेबल वाला जड़ वाला वृक्ष है जहाँ शीर्ष लेबल वृक्ष क्रम का सम्मान करते हैं (अर्थात, यदि {{math|''u'' < ''v''}} दो शीर्षों के लिए {{mvar|u}} और {{mvar|v}}, फिर का लेबल {{mvar|u}} के लेबल से छोटा है {{mvar|v}}).
+एक लेबल वाला वृक्ष             एक वृक्ष             है जिसमें प्रत्येक शीर्ष को एक अद्वितीय लेबल दिया जाता है। लेबल लगे वृक्ष             के शीर्ष पर {{mvar|n}} शीर्षों को आमतौर पर लेबल दिए जाते हैं {{math|1, 2, …, ''n''}}. एक [[पुनरावर्ती वृक्ष]] एक लेबल वाला जड़ वाला वृक्ष है जहाँ शीर्ष लेबल वृक्ष क्रम का सम्मान करते हैं (अर्थात, यदि {{math|''u'' < ''v''}} दो शीर्षों के लिए {{mvar|u}} और {{mvar|v}}, फिर का लेबल {{mvar|u}} के लेबल से छोटा है {{mvar|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}}
+जड़ वाले वृक्ष             में, शीर्ष का जनक {{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}}
-एक जड़ वाले पेड़ में एक शीर्ष की ऊंचाई उस शीर्ष से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। पेड़ की ऊंचाई जड़ की ऊंचाई है। किसी शीर्ष की गहराई उसके रूट (रूट पाथ) तक के पथ की लंबाई होती है। यह आमतौर पर विभिन्न स्व-संतुलन वाले पेड़ों, विशेष रूप से AVL पेड़ों के हेरफेर में आवश्यक है। जड़ की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वाले पेड़ (इसलिए जड़ और पत्ती दोनों) की गहराई और ऊँचाई शून्य होती है। परंपरागत रूप से, एक खाली पेड़ (बिना किसी कोने वाला पेड़, अगर इसकी अनुमति है) की गहराई और ऊंचाई -1 होती है।
+एक जड़ वाले वृक्ष             में एक शीर्ष की ऊंचाई उस शीर्ष से एक पत्ती के सबसे लंबे नीचे की ओर जाने वाले पथ की लंबाई है। वृक्ष             की ऊंचाई जड़ की ऊंचाई है। किसी शीर्ष की गहराई उसके जड़              (जड़              पाथ) तक के पथ की लंबाई होती है। यह आमतौर पर विभिन्न स्व-संतुलन वाले वृक्ष            ों, विशेष रूप से AVL वृक्ष            ों के हेरफेर में आवश्यक है। जड़ की गहराई शून्य होती है, पत्तियों की ऊँचाई शून्य होती है, और केवल एक शीर्ष वाले वृक्ष             (इसलिए जड़ और पत्ती दोनों) की गहराई और ऊँचाई शून्य होती है। परंपरागत रूप से, एक खाली वृक्ष             (बिना किसी कोने वाला वृक्ष            , अगर इसकी अनुमति है) की गहराई और ऊंचाई -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-एरी पेड़ों को कभी-कभी [[ त्रिगुट वृक्ष ]] कहा जाता है।
+एक के-आर्य वृक्ष |{{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-एरी वृक्ष            ों को कभी-कभी [[ त्रिगुट वृक्ष ]] कहा जाता है।
-=== {{anchor|Plane tree}} आदेश दिया गया पेड़ ===
+=== {{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> इसे प्लेन ट्री कहा जाता है क्योंकि चिल्ड्रन का क्रम प्लेन में ट्री के एंबेडिंग के बराबर होता है, जिसमें रूट सबसे ऊपर होता है और प्रत्येक वर्टेक्स के चिल्ड्रेन उस वर्टेक्स से नीचे होते हैं। विमान में जड़ वाले पेड़ की एम्बेडिंग को देखते हुए, यदि कोई बच्चों की दिशा को ठीक करता है, तो बाएं से दाएं कहें, तो एक एम्बेडिंग बच्चों का आदेश देता है। इसके विपरीत, एक आदेश दिया गया पेड़ दिया गया है, और परंपरागत रूप से शीर्ष पर जड़ खींच रहा है, फिर एक आदेशित पेड़ में बच्चे के कोने को बाएं से दाएं खींचा जा सकता है, जो अनिवार्य रूप से अद्वितीय प्लानर एम्बेडिंग प्रदान करता है।
+एक आदेशित वृक्ष (या समतल वृक्ष) एक जड़ वाला वृक्ष है जिसमें प्रत्येक शीर्ष के बच्चों के लिए एक क्रम निर्दिष्ट किया जाता है।{{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 के किनारे होते हैं। अधिक विशिष्ट प्रकार के फैले हुए वृक्ष            , प्रत्येक जुड़े परिमित आरेख             में मौजूद होते हैं, जिनमें गहराई-पहले खोज वृक्ष             शामिल हैं और चौड़ाई-पहले खोज वृक्ष            । [[गहराई-पहली खोज]] के अस्तित्व को सामान्य करते हुए, केवल काउंटेबल सेट के साथ हर जुड़े आरेख             में कई वर्टिकल में एक ट्रैमॉक्स ट्री होता है।{{sfnp|Diestel|2005|loc=Prop. 8.2.4}} हालाँकि, कुछ [[बेशुमार सेट]] आरेख            ़ में ऐसा कोई वृक्ष             नहीं होता है।{{sfnp|Diestel|2005|loc=Prop. 8.5.2}}
-* प्रत्येक परिमित वृक्ष n शीर्षों के साथ, साथ {{nowrap|''n'' > 1}}, कम से कम दो टर्मिनल शीर्ष (पत्तियां) हैं। पत्तों की यह न्यूनतम संख्या [[पथ ग्राफ]]़ की विशेषता है; अधिकतम संख्या, {{nowrap|''n'' − 1}}, केवल [[स्टार ग्राफ]]़ द्वारा प्राप्त किया जाता है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
+* प्रत्येक परिमित वृक्ष n शीर्षों के साथ, साथ {{nowrap|''n'' > 1}}, कम से कम दो टर्मिनल शीर्ष (पत्तियां) हैं। पत्तों की यह न्यूनतम संख्या [[पथ ग्राफ|पथ आरेख]]            ़ की विशेषता है; अधिकतम संख्या, {{nowrap|''n'' − 1}}, केवल [[स्टार ग्राफ|स्टार आरेख]]            ़ द्वारा प्राप्त किया जाता है। पत्तियों की संख्या कम से कम अधिकतम शीर्ष डिग्री है।
-* एक पेड़ में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक ग्राफ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक पेड़ में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हर पेड़ एक [[माध्यिका ग्राफ]] होता है।
+* एक वृक्ष             में किन्हीं तीन शीर्षों के लिए, उनके बीच के तीन रास्तों में ठीक एक शीर्ष उभयनिष्ठ होता है। अधिक आम तौर पर, एक आरेख            ़ में एक शीर्ष जो तीन शीर्षों में से तीन सबसे छोटे पथों से संबंधित होता है, इन शीर्षों का माध्यिका कहलाता है। क्योंकि एक वृक्ष             में हर तीन कोने में एक अद्वितीय माध्यिका होती है, हर वृक्ष             एक [[माध्यिका ग्राफ|माध्यिका आरेख]]             होता है।
-* हर पेड़ का एक [[ग्राफ केंद्र]] होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक एन-वर्टेक्स ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में वर्टेक्स को हटाने से ट्री को n/2 वर्टिकल से कम के सबट्री में विभाजित किया जाता है। दूसरे मामले में, दो केन्द्रकीय शीर्षों के बीच के किनारे को हटाने से वृक्ष ठीक n/2 शीर्षों के दो उपवृक्षों में विभाजित हो जाता है।
+* हर वृक्ष             का एक [[ग्राफ केंद्र|आरेख             केंद्र]] होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। केंद्र प्रत्येक सबसे लंबे पथ में मध्य शीर्ष या मध्य दो शीर्ष होता है। इसी तरह, प्रत्येक एन-वर्टेक्स ट्री में एक केन्द्रक होता है जिसमें एक शीर्ष या दो आसन्न कोने होते हैं। पहले मामले में वर्टेक्स को हटाने से ट्री को 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}}''}} क्रमशः [[बहुपद प्रमेय]] है
+केली के सूत्र में कहा गया है कि हैं {{math|''n''{{sup|''n''−2}}}} वृक्ष             पर {{mvar|n}} लेबल वाले शीर्ष। एक क्लासिक प्रूफ प्रुफर अनुक्रम का उपयोग करता है, जो स्वाभाविक रूप से एक मजबूत परिणाम दिखाता है: शीर्ष वाले वृक्ष            ों की संख्या {{math|1, 2, …, ''n''}} डिग्री {{math|''d''{{sub|1}}, ''d''{{sub|2}}, …, ''d{{sub|n}}''}} क्रमशः [[बहुपद प्रमेय]] है
 : <math>{n - 2 \choose d_1 - 1, d_2 - 1, \ldots, d_n - 1}.</math>
-एक अधिक सामान्य समस्या एक अप्रत्यक्ष ग्राफ में फैले हुए पेड़ों की गिनती करना है, जिसे [[मैट्रिक्स ट्री प्रमेय]] द्वारा संबोधित किया जाता है। (केली का सूत्र एक पूर्ण ग्राफ में [[फैले पेड़]]ों का विशेष मामला है।) आकार की परवाह किए बिना सभी उप-वृक्षों को गिनने की समान समस्या सामान्य स्थिति में शार्प-पी-पूर्ण|#पी-पूर्ण है ({{harvtxt|Jerrum|1994}}).
+एक अधिक सामान्य समस्या एक अप्रत्यक्ष आरेख             में फैले हुए वृक्ष            ों की गिनती करना है, जिसे [[मैट्रिक्स ट्री प्रमेय]] द्वारा संबोधित किया जाता है। (केली का सूत्र एक पूर्ण आरेख             में [[फैले पेड़|फैले वृक्ष]]            ों का विशेष मामला है।) आकार की परवाह किए बिना सभी उप-वृक्षों को गिनने की समान समस्या सामान्य स्थिति में शार्प-पी-पूर्ण|#पी-पूर्ण है ({{harvtxt|Jerrum|1994}}).
-=== बिना लेबल वाले पेड़ ===
+=== बिना लेबल वाले वृक्ष            ===
-बिना लेबल वाले मुक्त पेड़ों की संख्या गिनना एक कठिन समस्या है। संख्या के लिए कोई बंद सूत्र नहीं {{math|''t''(''n'')}} पेड़ों के साथ {{mvar|n}} ग्राफ समाकृतिकता [[तक]] शीर्ष ज्ञात है। के पहले कुछ मान {{math|''t''(''n'')}} हैं
+बिना लेबल वाले मुक्त वृक्ष            ों की संख्या गिनना एक कठिन समस्या है। संख्या के लिए कोई बंद सूत्र नहीं {{math|''t''(''n'')}} वृक्ष            ों के साथ {{mvar|n}} आरेख             समाकृतिकता [[तक]] शीर्ष ज्ञात है। के पहले कुछ मान {{math|''t''(''n'')}} हैं
 : 1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … {{OEIS|A000055}}.
 {{harvtxt|Otter|1948}} स्पर्शोन्मुख अनुमान सिद्ध किया
@@ Line 94: / Line 95: @@
 साथ {{math|''C'' ≈ 0.534949606...}} और {{math|''α'' ≈ 2.95576528565...}} {{OEIS|A051491}}. यहां ही {{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|α}} ऊपर के रूप में (cf. {{harvtxt|Knuth|1997}}, बच्चू। 2.3.4.4 और {{harvtxt|Flajolet|Sedgewick|2009}}, बच्चू। VII.5, पी। 475)।
@@ Line 101: / Line 102: @@
 : 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … {{OEIS|A000081}}
-== पेड़ों के प्रकार ==
+== वृक्ष            ों के प्रकार ==
-* एक पथ ग्राफ (या रैखिक ग्राफ) के होते हैं {{mvar|n}} शीर्षों को एक पंक्ति में व्यवस्थित किया जाता है, ताकि शीर्षों को {{mvar|i}} और {{math|''i'' + 1}} किनारे से जुड़े हुए हैं {{math|1=''i'' = 1, …, ''n'' – 1}}.
+* एक पथ आरेख             (या रैखिक आरेख            ) के होते हैं {{mvar|n}} शीर्षों को एक पंक्ति में व्यवस्थित किया जाता है, ताकि शीर्षों को {{mvar|i}} और {{math|''i'' + 1}} किनारे से जुड़े हुए हैं {{math|1=''i'' = 1, …, ''n'' – 1}}.
-* एक तारकीय पेड़ में एक केंद्रीय शीर्ष होता है जिसे रूट कहा जाता है और इससे जुड़े कई पथ ग्राफ होते हैं। अधिक औपचारिक रूप से, एक पेड़ तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
+* एक तारकीय वृक्ष             में एक केंद्रीय शीर्ष होता है जिसे जड़              कहा जाता है और इससे जुड़े कई पथ आरेख             होते हैं। अधिक औपचारिक रूप से, एक वृक्ष             तारे जैसा होता है यदि उसके पास 2 से अधिक डिग्री का ठीक एक शीर्ष होता है।
-* एक [[तारा (ग्राफ सिद्धांत)]] एक पेड़ है जिसमें एक आंतरिक शीर्ष (और {{math|''n'' – 1}} पत्तियाँ)। दूसरे शब्दों में, आदेश का एक तारा वृक्ष {{mvar|n}} व्यवस्था का वृक्ष है {{mvar|n}} अधिक से अधिक पत्तियों के साथ।
+* एक [[तारा (ग्राफ सिद्धांत)|तारा (आरेख             सिद्धांत)]] एक वृक्ष             है जिसमें एक आंतरिक शीर्ष (और {{math|''n'' – 1}} पत्तियाँ)। दूसरे शब्दों में, आदेश का एक तारा वृक्ष {{mvar|n}} व्यवस्था का वृक्ष है {{mvar|n}} अधिक से अधिक पत्तियों के साथ।
-* एक कैटरपिलर पेड़ एक ऐसा पेड़ है जिसमें सभी कोने एक केंद्रीय पथ सबग्राफ की दूरी 1 के भीतर हैं।
+* एक कैटरपिलर वृक्ष             एक ऐसा वृक्ष             है जिसमें सभी कोने एक केंद्रीय पथ सबआरेख             की दूरी 1 के भीतर हैं।
-* रेखांकन की एक सूची# लॉबस्टर एक पेड़ है जिसमें सभी शीर्ष एक केंद्रीय पथ सबग्राफ की दूरी 2 के भीतर हैं।
+* रेखांकन की एक सूची# लॉबस्टर एक वृक्ष             है जिसमें सभी शीर्ष एक केंद्रीय पथ सबआरेख             की दूरी 2 के भीतर हैं।
-* डिग्री का एक नियमित पेड़ {{mvar|d}} अनंत वृक्ष है {{mvar|d}} प्रत्येक शीर्ष पर किनारों। ये [[मुक्त समूह]]ों के [[केली ग्राफ]] और [[बिल्डिंग (गणित)]] के सिद्धांत के रूप में उत्पन्न होते हैं।
+* डिग्री का एक नियमित वृक्ष             {{mvar|d}} अनंत वृक्ष है {{mvar|d}} प्रत्येक शीर्ष पर किनारों। ये [[मुक्त समूह]]ों के [[केली ग्राफ|केली आरेख]]             और [[बिल्डिंग (गणित)]] के सिद्धांत के रूप में उत्पन्न होते हैं।
 == यह भी देखें ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:28, 12 May 2023

Contents

परिभाषाएँ

वृक्ष

वन

पॉलीट्री

पॉलीफ़ॉरेस्ट

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

आदेश दिया गया वृक्ष

गुण

गणना

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:28, 12 May 2023

परिभाषाएँ

वृक्ष

वन

पॉलीट्री

पॉलीफ़ॉरेस्ट

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

आदेश दिया गया वृक्ष

गुण

गणना

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories