स्पेनिंग ट्री: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Tree which includes all vertices of a graph}} {{About||the network protocol|Spanning Tree Protocol|other uses|}} File:4x4 grid spanning tree.svg|thumb|[...")
 
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Tree which includes all vertices of a graph}}
{{Short description|Tree which includes all vertices of a graph}}
{{About||the network protocol|Spanning Tree Protocol|other uses|}}
{{About||नेटवर्क प्रोटोकॉल|स्पेनिंग ट्री प्रोटोकॉल|अन्य उपयोग|}}


[[File:4x4 grid spanning tree.svg|thumb|[[ग्रिड ग्राफ]]़ का एक फैला हुआ पेड़ (नीले भारी किनारे)।]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, एक [[अप्रत्यक्ष ग्राफ]] ''जी'' का एक फैला हुआ पेड़ ''टी'' एक उपग्राफ है जो एक पेड़ (ग्राफ सिद्धांत) है जिसमें ''जी'' के सभी वर्टेक्स (ग्राफ सिद्धांत) शामिल हैं ''.<ref name="NetworkX 2.6.2 documentation">{{cite web | title=पेड़| website=NetworkX 2.6.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/tree.html | access-date=2021-12-10 | quote=For trees and arborescence, the adjective “spanning” may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph. }}</ref> सामान्य तौर पर, एक ग्राफ़ में कई फैले हुए पेड़ हो सकते हैं, लेकिन एक ग्राफ़ जो ग्राफ़ से जुड़ा नहीं है, उसमें एक फैला हुआ पेड़ नहीं होगा (नीचे #फैले हुए जंगलों के बारे में देखें)। यदि G के सभी किनारे (ग्राफ़ सिद्धांत) भी G के फैले हुए पेड़ T के किनारे हैं, तो G एक पेड़ है और T के समान है (अर्थात, एक पेड़ में एक अद्वितीय फैला हुआ पेड़ होता है और वह स्वयं होता है)।
[[File:4x4 grid spanning tree.svg|thumb|[[ग्रिड ग्राफ]] का स्पेनिंग ट्री (नीले भारी किनारे)।]][[ग्राफ सिद्धांत]] के गणित क्षेत्र में, [[अप्रत्यक्ष ग्राफ]] ''G'' का '''स्पेनिंग ट्री''' T उप-ग्राफ है जो ट्री (ग्राफ सिद्धांत) है जिसमें G के सभी शीर्ष सम्मिलित हैं।''<ref name="NetworkX 2.6.2 documentation">{{cite web | title=पेड़| website=NetworkX 2.6.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/tree.html | access-date=2021-12-10 | quote=For trees and arborescence, the adjective “spanning” may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph. }}</ref>''सामान्यतः'','' एक ग्राफ़ में कई स्पेनिंग ट्री हो सकते हैं, किन्तु जो ग्राफ़ जुड़ा नहीं है उसमें स्पेनिंग ट्री नहीं होगा (नीचे स्पेनिंग फारेस्टों के बारे में देखें)। यदि G के सभी किनारे (ग्राफ़ सिद्धांत) भी G स्पेनिंग ट्री T के किनारे हैं, तो G ट्री है और T के समान है (अर्थात, ट्री में अद्वितीय स्पेनिंग ट्री होता है और वह स्वयं होता है)।


==अनुप्रयोग==
==अनुप्रयोग==
डिज्क्स्ट्रा के एल्गोरिदम और ए[[ए* खोज एल्गोरिदम]] सहित कई [[ पथ खोज ]] एल्गोरिदम, समस्या को हल करने में एक मध्यवर्ती चरण के रूप में आंतरिक रूप से एक स्पैनिंग ट्री का निर्माण करते हैं।
डिज्क्स्ट्रा के एल्गोरिदम और [[ए* खोज एल्गोरिदम|A* सर्च एल्गोरिदम]] सहित कई[[ पथ खोज | पाथफाइंडिंग]] एल्गोरिदम, समस्या को समाधान करने में मध्यवर्ती चरण के रूप में आंतरिक रूप से स्पैनिंग ट्री का निर्माण करते हैं।


बिजली नेटवर्क, वायरिंग कनेक्शन, पाइपिंग, स्वचालित वाक् पहचान आदि की लागत को कम करने के लिए, लोग अक्सर एल्गोरिदम का उपयोग करते हैं जो [[न्यूनतम फैलाव वाला पेड़]] खोजने की प्रक्रिया में मध्यवर्ती चरणों के रूप में धीरे-धीरे एक स्पैनिंग ट्री (या ऐसे कई पेड़) बनाते हैं। .<ref>{{cite web|first1=R. L.|last1=Graham|first2=Pavol|last2=Hell|url=http://www.math.ucsd.edu/~ronspubs/85_07_minimum_spanning_tree.pdf|title=न्यूनतम स्पैनिंग वृक्ष समस्या के इतिहास पर|date=1985}}</ref>
विद्युत् नेटवर्क, वायरिंग कनेक्शन, पाइपिंग, स्वचालित वाक् पहचान आदि के व्यय को कम करने के लिए, लोग प्रायः एल्गोरिदम का उपयोग करते हैं जो [[न्यूनतम फैलाव वाला पेड़|न्यूनतम स्पैनिंग ट्री]] शोध की प्रक्रिया में मध्यवर्ती चरणों के रूप में धीरे-धीरे स्पैनिंग ट्री (या ऐसे कई ट्री) बनाते हैं।<ref>{{cite web|first1=R. L.|last1=Graham|first2=Pavol|last2=Hell|url=http://www.math.ucsd.edu/~ronspubs/85_07_minimum_spanning_tree.pdf|title=न्यूनतम स्पैनिंग वृक्ष समस्या के इतिहास पर|date=1985}}</ref>
इंटरनेट और कई अन्य [[दूरसंचार नेटवर्क]] में ट्रांसमिशन लिंक होते हैं जो नोड्स को एक [[जाल टोपोलॉजी]] में एक साथ जोड़ते हैं जिसमें कुछ लूप शामिल होते हैं।
[[ब्रिज लूप]] और [[रूटिंग लूप]] से बचने के लिए, ऐसे नेटवर्क के लिए डिज़ाइन किए गए कई रूटिंग प्रोटोकॉल - जिनमें [[ स्पेनिंग ट्री प्रोटोकॉल ]], [[पहले सबसे छोटा रास्ता खोलो]], [[लिंक-स्टेट रूटिंग प्रोटोकॉल]], [[संवर्धित वृक्ष-आधारित रूटिंग]] आदि शामिल हैं - प्रत्येक राउटर को याद रखने की आवश्यकता होती है। फैला हुआ पेड़।<रेफ नाम= https://en.wikipedia.org/w/index.php?title=Spanning_tree&action=edit# >{{cite web |last1=Borg |first1=Anita |title=नेटवर्क प्रोटोकॉल डिज़ाइन की लोककथाएँ|url=https://www.youtube.com/watch?v=CcmfS8Ue7G4 |website=YouTube |publisher=Microsoft Research |access-date=13 May 2022}}</ref>


अधिकतम [[जीनस (गणित)]] के साथ [[ग्राफ एम्बेडिंग]] खोजने के लिए [[टोपोलॉजिकल ग्राफ सिद्धांत]] में एक विशेष प्रकार के फैले हुए पेड़, ज़ुओंग पेड़ का उपयोग किया जाता है। ज़ुओंग पेड़ एक फैला हुआ पेड़ है, जैसे कि, शेष ग्राफ़ में, विषम संख्या में किनारों के साथ जुड़े घटकों की संख्या यथासंभव छोटी होती है। एक ज़ुओंग पेड़ और एक संबद्ध अधिकतम-जीनस एम्बेडिंग बहुपद समय में पाया जा सकता है।
इंटरनेट और कई अन्य [[दूरसंचार नेटवर्क]] में ट्रांसमिशन लिंक होते हैं जो नोड्स को [[जाल टोपोलॉजी|मेश टोपोलॉजी]] में साथ जोड़ते हैं जिसमें कुछ लूप सम्मिलित होते हैं। [[ब्रिज लूप]] और [[रूटिंग लूप]] से बचने के लिए, ऐसे नेटवर्क के लिए डिज़ाइन किए गए कई रूटिंग प्रोटोकॉल - जिनमें [[ स्पेनिंग ट्री प्रोटोकॉल |स्पेनिंग ट्री प्रोटोकॉल]], [[पहले सबसे छोटा रास्ता खोलो|विवृत शॉर्टेस्ट पाथ फर्स्ट]], [[लिंक-स्टेट रूटिंग प्रोटोकॉल]], [[संवर्धित वृक्ष-आधारित रूटिंग|ऑगमेंटेड ट्री-आधारित रूटिंग]] आदि सम्मिलित हैं- प्रत्येक राउटर को याद रखने की आवश्यकता होती है।
रेफरी>{{citation
 
| last1 = Beineke | first1 = Lowell W. | author1-link = L. W. Beineke
अधिकतम [[जीनस (गणित)]] के साथ [[ग्राफ एम्बेडिंग]] शोध के लिए [[टोपोलॉजिकल ग्राफ सिद्धांत]] में विशेष प्रकार के स्पैनिंग ट्री, ज़ुओंग ट्री का उपयोग किया जाता है। ज़ुओंग ट्री स्पैनिंग ट्री है, जैसे कि, शेष ग्राफ़ में, विषम संख्या में किनारों के साथ जुड़े घटकों की संख्या यथासंभव छोटी होती है। ज़ुओंग ट्री और संबद्ध अधिकतम-जीनस एम्बेडिंग बहुपद समय में पाया जा सकता है।
| last2 = Wilson | first2 = Robin J. | author2-link = Robin Wilson (mathematician)
| doi = 10.1017/CBO9781139087223
| isbn = 978-0-521-80230-7
| mr = 2581536
| page = 36
| publisher = Cambridge University Press, Cambridge
| series = Encyclopedia of Mathematics and its Applications
| title = Topics in topological graph theory
| volume = 128
| year = 2009}}</ref>


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


===मौलिक चक्र===
===मौलिक चक्र===
फैले हुए पेड़ में सिर्फ एक किनारा जोड़ने से एक चक्र बन जाएगा; ऐसे चक्र को उस पेड़ के संबंध में मौलिक चक्र कहा जाता है। फैले हुए पेड़ में नहीं बल्कि प्रत्येक किनारे के लिए एक अलग मौलिक चक्र होता है; इस प्रकार, मूलभूत चक्रों और किनारों के बीच एक-से-एक पत्राचार होता है जो फैले हुए पेड़ में नहीं होता है। ''V'' शीर्षों के साथ जुड़े ग्राफ़ के लिए, किसी भी फैले हुए पेड़ में ''V'' - 1 किनारे होंगे, और इस प्रकार, ''E'' किनारों के ग्राफ़ और उसके फैले हुए पेड़ों में से एक में ''E'' होगा ' - ''V'' + 1 मौलिक चक्र (एक फैले हुए पेड़ में शामिल किनारों की संख्या से घटाए गए किनारों की संख्या; फैले हुए पेड़ में शामिल नहीं किए गए किनारों की संख्या देना)। किसी भी फैले हुए पेड़ के लिए सभी ''ई'' - ''वी'' + 1 मौलिक चक्रों का सेट एक [[चक्र आधार]] बनाता है, यानी, [[चक्र स्थान]] के लिए एक आधार।<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;65–67.</ref>
स्पैनिंग ट्री में सिर्फ किनारा जोड़ने से चक्र बन जाएगा; ऐसे चक्र को उस ट्री के संबंध में मौलिक चक्र कहा जाता है। स्पैनिंग ट्री में नहीं अन्यथा प्रत्येक किनारे के लिए भिन्न मौलिक चक्र होता है; इस प्रकार, मूलभूत चक्रों और किनारों के मध्य पत्राचार होता है जो स्पैनिंग ट्री में नहीं होता है। ''V'' शीर्षों के साथ जुड़े ग्राफ़ के लिए, किसी भी स्पैनिंग ट्री में ''V'' - 1 किनारे होंगे, और इस प्रकार, ''E'' किनारों के ग्राफ़ और उसके स्पैनिंग ट्री में से E - ''V'' + 1 मौलिक चक्र (स्पैनिंग ट्री में सम्मिलित किनारों की संख्या से घटाए गए किनारों की संख्या; स्पैनिंग ट्री में सम्मिलित नहीं किए गए किनारों की संख्या) है। किसी भी स्पैनिंग ट्री के लिए सभी ''E'' − ''V'' + 1 मौलिक चक्रों का समुच्चय [[चक्र आधार]] बनाता है, अर्थात, [[चक्र स्थान|चक्र समिष्ट]] के लिए आधार है।<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;65–67.</ref>


'''मौलिक कटसेट्स'''


===मौलिक कटसेट===
मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए स्पैनिंग ट्री के संबंध में मौलिक कटसेट्स की धारणा भी दोहरी है। स्पैनिंग ट्री के केवल किनारे को विस्थापित करके, शीर्षों को दो असंयुक्त समुच्चयों में विभाजित किया गया है। मौलिक कटसेट्स को किनारों के समुच्चय के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूर्ण करने के लिए ग्राफ़ ''G'' से विस्थापित किया जाना चाहिए। इस प्रकार, प्रत्येक स्पैनिंग ट्री ''V'' के समुच्चय को परिभाषित करता है- 1 मौलिक कटसेट्स, स्पैनिंग ट्री के प्रत्येक किनारे के लिए है।<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;67–69.</ref>
एक मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए फैले हुए पेड़ के संबंध में एक मौलिक कटसेट की धारणा भी दोहरी है। फैले हुए पेड़ के केवल एक किनारे को हटाकर, शीर्षों को दो असंयुक्त सेटों में विभाजित किया गया है। मौलिक कटसेट को किनारों के सेट के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूरा करने के लिए ग्राफ़ ''जी'' से हटाया जाना चाहिए। इस प्रकार, प्रत्येक स्पैनिंग ट्री ''V'' के एक सेट को परिभाषित करता है - 1 मौलिक कटसेट, स्पैनिंग ट्री के प्रत्येक किनारे के लिए एक।<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;67–69.</ref>
मौलिक कटसेट और मौलिक चक्रों के बीच द्वंद्व यह देखते हुए स्थापित किया गया है कि चक्र किनारे फैले हुए पेड़ में नहीं हैं, केवल चक्र में अन्य किनारों के कटसेट में दिखाई दे सकते हैं; और इसके विपरीत: कटसेट में किनारे केवल उन चक्रों में दिखाई दे सकते हैं जिनमें कटसेट के अनुरूप किनारा होता है। इस द्वंद्व को मैट्रोइड्स के सिद्धांत का उपयोग करके भी व्यक्त किया जा सकता है, जिसके अनुसार एक फैला हुआ पेड़ [[ग्राफ़िक मैट्रोइड]] का आधार है, एक मौलिक चक्र आधार में एक तत्व जोड़कर बनाए गए सेट के भीतर अद्वितीय सर्किट है, और मौलिक कटसेट को परिभाषित किया गया है उसी तरह [[दोहरी [[matroid]]]] से।<ref>{{citation |title=Matroid Theory |volume=3 |series=Oxford [[Graduate Texts in Mathematics]] |first=J. G. |last=Oxley |author-link=James Oxley |publisher=Oxford University Press |year=2006 |isbn=978-0-19-920250-8 |page=141 |url=https://books.google.com/books?id=puKta1Hdz-8C&pg=PA141}}.</ref>


मौलिक कटसेट्स और मौलिक चक्रों के मध्य द्वंद्व यह देखते हुए स्थापित किया गया है कि चक्र किनारे स्पैनिंग ट्री में नहीं हैं, केवल चक्र में अन्य किनारों के कटसेट्स में दिखाई दे सकते हैं; और इसके विपरीत: कटसेट्स में किनारे केवल उन चक्रों में दिखाई दे सकते हैं जिनमें कटसेट्स के अनुरूप किनारा होता है। इस द्वंद्व को मैट्रोइड्स के सिद्धांत का उपयोग करके भी व्यक्त किया जा सकता है, जिसके अनुसार स्पैनिंग ट्री [[ग्राफ़िक मैट्रोइड]] का आधार है, मौलिक चक्र आधार में तत्व जोड़कर बनाए गए समुच्चय के भीतर अद्वितीय परिपथ है, और मौलिक कटसेट्स को परिभाषित किया गया है उसी प्रकार दोहरी [[matroid|मैट्रोइड]] है।<ref>{{citation |title=Matroid Theory |volume=3 |series=Oxford [[Graduate Texts in Mathematics]] |first=J. G. |last=Oxley |author-link=James Oxley |publisher=Oxford University Press |year=2006 |isbn=978-0-19-920250-8 |page=141 |url=https://books.google.com/books?id=puKta1Hdz-8C&pg=PA141}}.</ref>


===विस्तारित वन===
'''स्पैनिंग फारेस्ट'''
ग्राफ़ में फैला हुआ जंगल एक उपग्राफ़ है जो एक अतिरिक्त आवश्यकता वाला जंगल है। उपयोग में दो असंगत आवश्यकताएँ हैं, जिनमें से एक अपेक्षाकृत दुर्लभ है।


* लगभग सभी ग्राफ़ सिद्धांत पुस्तकें और लेख एक फैले हुए जंगल को एक ऐसे जंगल के रूप में परिभाषित करते हैं जो सभी शीर्षों तक फैला हुआ है, जिसका अर्थ केवल यह है कि ग्राफ़ का प्रत्येक शीर्ष जंगल में एक शीर्ष है। एक कनेक्टेड ग्राफ़ में एक अलग फैला हुआ जंगल हो सकता है, जैसे कि बिना किनारों वाला जंगल, जिसमें प्रत्येक शीर्ष एक एकल-शीर्ष वृक्ष बनाता है।<ref name="pearls">{{citation |title=Pearls in Graph Theory: A Comprehensive Introduction|title-link= Pearls in Graph Theory
ग्राफ़ में स्पैनिंग फारेस्ट उप-ग्राफ़ है जो अतिरिक्त आवश्यकता वाला फारेस्ट है। उपयोग में दो असंगत आवश्यकताएँ हैं, जिनमें से अपेक्षाकृत दुर्लभ है।
 
* लगभग सभी ग्राफ़ सिद्धांत पुस्तकें और लेख स्पैनिंग फारेस्ट को ऐसे फारेस्ट के रूप में परिभाषित करते हैं जो सभी शीर्षों तक स्पैनिंग है, जिसका अर्थ केवल यह है कि ग्राफ़ का प्रत्येक शीर्ष फारेस्ट में शीर्ष है। कनेक्टेड ग्राफ़ में भिन्न स्पैनिंग फारेस्ट हो सकता है, जैसे कि बिना किनारों वाला फारेस्ट, जिसमें प्रत्येक शीर्ष एकल-शीर्ष ट्री बनाता है।<ref name="pearls">{{citation |title=Pearls in Graph Theory: A Comprehensive Introduction|title-link= Pearls in Graph Theory
  |last1=Hartsfield |first1=Nora |author1-link=Nora Hartsfield |last2=Ringel |first2=Gerhard |author2-link=Gerhard Ringel |publisher=Courier Dover Publications |year=2003 |isbn=978-0-486-43232-8 |at=[https://books.google.com/books?id=R6pq0fbQG0QC&pg=PA100 p. 100]}}.</ref><ref>{{citation |title=Combinatorics: Topics, Techniques, Algorithms |first=Peter J. |last=Cameron |author-link=Peter Cameron (mathematician) |publisher=Cambridge University Press |year=1994 |isbn=978-0-521-45761-3 |page=163 |url=https://books.google.com/books?id=_aJIKWcifDwC&pg=PA163}}.</ref>
  |last1=Hartsfield |first1=Nora |author1-link=Nora Hartsfield |last2=Ringel |first2=Gerhard |author2-link=Gerhard Ringel |publisher=Courier Dover Publications |year=2003 |isbn=978-0-486-43232-8 |at=[https://books.google.com/books?id=R6pq0fbQG0QC&pg=PA100 p. 100]}}.</ref><ref>{{citation |title=Combinatorics: Topics, Techniques, Algorithms |first=Peter J. |last=Cameron |author-link=Peter Cameron (mathematician) |publisher=Cambridge University Press |year=1994 |isbn=978-0-521-45761-3 |page=163 |url=https://books.google.com/books?id=_aJIKWcifDwC&pg=PA163}}.</ref>
* कुछ ग्राफ़ सिद्धांत लेखक एक फैले हुए जंगल को दिए गए ग्राफ़ का अधिकतम एसाइक्लिक सबग्राफ, या समकक्ष रूप से ग्राफ़ के प्रत्येक कनेक्टेड घटक (ग्राफ सिद्धांत) में एक फैले हुए पेड़ से युक्त एक सबग्राफ के रूप में परिभाषित करते हैं।<ref>{{citation |title=Modern Graph Theory |volume=184 |series=Graduate Texts in Mathematics |first=Béla |last=Bollobás |author-link=Béla Bollobás |publisher=Springer |year=1998 |isbn=978-0-387-98488-9 |page=350 |url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA350}}; {{citation |title=LEDA: A Platform for Combinatorial and Geometric Computing |first=Kurt |last=Mehlhorn |author-link=Kurt Mehlhorn |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-56329-1 |page=260 |url=https://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA260}}.</ref>
* कुछ ग्राफ़ सिद्धांत लेखक स्पैनिंग फारेस्ट को दिए गए ग्राफ़ का अधिकतम एसाइक्लिक उप-ग्राफ, या समकक्ष रूप से ग्राफ़ के प्रत्येक कनेक्टेड घटक (ग्राफ सिद्धांत) में स्पैनिंग ट्री से युक्त उप-ग्राफ के रूप में परिभाषित करते हैं।<ref>{{citation |title=Modern Graph Theory |volume=184 |series=Graduate Texts in Mathematics |first=Béla |last=Bollobás |author-link=Béla Bollobás |publisher=Springer |year=1998 |isbn=978-0-387-98488-9 |page=350 |url=https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA350}}; {{citation |title=LEDA: A Platform for Combinatorial and Geometric Computing |first=Kurt |last=Mehlhorn |author-link=Kurt Mehlhorn |publisher=Cambridge University Press |year=1999 |isbn=978-0-521-56329-1 |page=260 |url=https://books.google.com/books?id=Q2aXZl3fgvMC&pg=PA260}}.</ref>
इन दो परिभाषाओं के बीच भ्रम से बचने के लिए, {{harvtxt|Gross|Yellen|2005}} दिए गए ग्राफ के समान घटकों (यानी, एक अधिकतम जंगल) के साथ एक फैले हुए जंगल के लिए पूर्ण फैले हुए जंगल शब्द का सुझाव दें, जबकि {{harvtxt|Bondy|Murty|2008}} इसके बजाय इस प्रकार के जंगल को अधिकतम फैला हुआ जंगल कहें (जो अनावश्यक है, क्योंकि अधिकतम जंगल में आवश्यक रूप से प्रत्येक शीर्ष शामिल होता है)।<ref>{{citation |title=Graph Theory and Its Applications |edition=2nd |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |publisher=CRC Press |year=2005 |isbn=978-1-58488-505-4 |page=168 |url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA168}}; {{citation |title=Graph Theory |volume=244 |series=Graduate Texts in Mathematics |first1=J. A. |last1=Bondy |first2=U. S. R. |last2=Murty |publisher=Springer |year=2008 |isbn=978-1-84628-970-5 |page=578 |url=https://books.google.com/books?id=V0gUTxkOSboC&pg=PA578}}.</ref>
इन दो परिभाषाओं के मध्य भ्रम से बचने के लिए, {{harvtxt|ग्रॉस |येलेन|2005}} दिए गए ग्राफ के समान घटकों (अर्थात, अधिकतम फारेस्ट) के साथ स्पैनिंग फारेस्ट के लिए पूर्ण स्पैनिंग फारेस्ट शब्द का विचार दें रहे है, जबकि {{harvtxt|बॉन्डी |मूर्ति |2008}} इसके अतिरिक्त इस प्रकार के फारेस्ट को अधिकतम स्पैनिंग फारेस्ट कहा जाता है (जो अनावश्यक है, क्योंकि अधिकतम फारेस्ट में आवश्यक रूप से प्रत्येक शीर्ष सम्मिलित होता है)।<ref>{{citation |title=Graph Theory and Its Applications |edition=2nd |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |publisher=CRC Press |year=2005 |isbn=978-1-58488-505-4 |page=168 |url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA168}}; {{citation |title=Graph Theory |volume=244 |series=Graduate Texts in Mathematics |first1=J. A. |last1=Bondy |first2=U. S. R. |last2=Murty |publisher=Springer |year=2008 |isbn=978-1-84628-970-5 |page=578 |url=https://books.google.com/books?id=V0gUTxkOSboC&pg=PA578}}.</ref>
 


==फैले हुए पेड़ों की गिनती==
== स्पैनिंग ट्री की गिनती ==
[[File:Cayley's formula 2-4.svg|thumb|केली का सूत्र एक पूर्ण ग्राफ़ पर फैले पेड़ों की संख्या की गणना करता है। वहाँ हैं <math>2^{2-2}=1</math> में पेड़ <math>K_2</math>,
[[File:Cayley's formula 2-4.svg|thumb|केली का सूत्र पूर्ण ग्राफ़ पर स्पैनिंग ट्री की संख्या की गणना करता है। वहाँ हैं <math>2^{2-2}=1</math> में ट्री <math>K_2</math>, <math>3^{3-2}=3</math> में ट्री <math>K_3</math>, और <math>4^{4-2}=16</math> में ट्री <math>K_4</math>]]किसी कनेक्टेड ग्राफ़ के स्पैनिंग ट्री की संख्या t(G) उत्तम रूप से अध्ययन किया गया [[अपरिवर्तनीय (गणित)]] है।
<math>3^{3-2}=3</math> में पेड़ <math>K_3</math>, और <math>4^{4-2}=16</math>
में पेड़ <math>K_4</math>.]]किसी कनेक्टेड ग्राफ़ के फैले हुए पेड़ों की संख्या t(G) एक अच्छी तरह से अध्ययन किया गया [[अपरिवर्तनीय (गणित)]] है।


===विशिष्ट ग्राफ़ में===
===विशिष्ट ग्राफ़ में===
कुछ मामलों में, सीधे t(G) की गणना करना आसान है:
कुछ स्थितियों में, सीधे t(G) की गणना करना सरल है:
* यदि G स्वयं एक वृक्ष है, तो {{math|1=''t''(''G'')&nbsp;=&nbsp;1}}.
* यदि G स्वयं ट्री है, तो {{math|1=''t''(''G'')&nbsp;=&nbsp;1}} है।
* जब G [[चक्र ग्राफ]]़ C है<sub>n</sub>n शीर्षों के साथ, फिर {{math|1=''t''(''G'')&nbsp;=&nbsp;''n''}}.
* जब G, n शीर्षों वाला [[चक्र ग्राफ]] C<sub>n</sub> है, तो {{math|1=''t''(''G'')&nbsp;=&nbsp;''n''}} है।
* n शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र<ref>{{citation
* शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र<ref>{{citation
  | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
  | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
  | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
  | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
Line 61: Line 47:
  | publisher = [[Springer-Verlag]]
  | publisher = [[Springer-Verlag]]
  | title = Proofs from THE BOOK
  | title = Proofs from THE BOOK
  | year = 1998| title-link = Proofs from THE BOOK }}.</ref> फैले हुए पेड़ों की संख्या इस प्रकार देता है {{math|1=''n''<sup>''n''&nbsp;−&nbsp;2</sup>}}.
  | year = 1998| title-link = Proofs from THE BOOK }}.</ref> स्पैनिंग ट्री की संख्या {{math|1=''n''<sup>''n''&nbsp;−&nbsp;2</sup>}} इस प्रकार देता है।
* यदि G [[पूर्ण द्विदलीय ग्राफ]] है <math>K_{p,q}</math>,तब <math>t(G)=p^{q-1}q^{p-1}</math>.<ref name="pearls" />* एन-डायमेंशनल [[हाइपरक्यूब ग्राफ]]़ के लिए <math>Q_n</math>,<ref>{{citation
* यदि G [[पूर्ण द्विदलीय ग्राफ]] है <math>K_{p,q}</math>, तब <math>t(G)=p^{q-1}q^{p-1}</math>है।<ref name="pearls" />
*एन-आयामी [[हाइपरक्यूब ग्राफ]] के लिए <math>Q_n</math>,<ref>{{citation
  | last1 = Harary | first1 = Frank | author1-link = Frank Harary
  | last1 = Harary | first1 = Frank | author1-link = Frank Harary
  | last2 = Hayes | first2 = John P.
  | last2 = Hayes | first2 = John P.
Line 75: Line 62:
  | year = 1988| hdl = 2027.42/27522
  | year = 1988| hdl = 2027.42/27522
  | hdl-access = free
  | hdl-access = free
  }}.</ref> फैले हुए वृक्षों की संख्या है <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>.
  }}.</ref> स्पैनिंग ट्री की संख्या <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math> है।
 
=== आरबिटरेरी ग्राफ़ में ===
{{main|किरचॉफ का प्रमेय}}


===मनमाने ग्राफ़ में===
अधिक सामान्यतः, किसी भी ग्राफ़ G के लिए, संख्या t(G) की गणना किरचॉफ के [[मैट्रिक्स (गणित)|आव्यूह]]-ट्री प्रमेय का उपयोग करके, ग्राफ से प्राप्त आव्यूह के निर्धारक के रूप में बहुपद समय में की जा सकती है।
{{main|Kirchhoff's theorem}}


अधिक सामान्यतः, किसी भी ग्राफ़ G के लिए, संख्या t(G) की गणना ग्राफ़ से प्राप्त [[मैट्रिक्स (गणित)]] के निर्धारक के रूप में बहुपद समय में की जा सकती है,
<ref>{{citation |title=Graphs, Algorithms, and Optimization |series=Discrete Mathematics and Its Applications |first1=William |last1=Kocay |first2=Donald L. |last2=Kreher |publisher=CRC Press |year=2004 |isbn=978-0-203-48905-5 |pages=111–116 |contribution=5.8 The matrix-tree theorem |url=https://books.google.com/books?id=zxSmHAoMiRUC&pg=PA111}}.</ref>विशेष रूप से, t(G) की गणना करने के लिए, ग्राफ़ के [[लाप्लासियन मैट्रिक्स|लाप्लासियन]] आव्यूह का निर्माण किया जाता है, वर्ग आव्यूह जिसमें पंक्तियाँ और स्तंभ दोनों G के शीर्षों द्वारा अनुक्रमित होते हैं। पंक्ति i और स्तंभ j में प्रविष्टि तीन मानों में से है:
किरचॉफ प्रमेय का उपयोग करना|किरचॉफ मैट्रिक्स-वृक्ष प्रमेय।<ref>{{citation |title=Graphs, Algorithms, and Optimization |series=Discrete Mathematics and Its Applications |first1=William |last1=Kocay |first2=Donald L. |last2=Kreher |publisher=CRC Press |year=2004 |isbn=978-0-203-48905-5 |pages=111–116 |contribution=5.8 The matrix-tree theorem |url=https://books.google.com/books?id=zxSmHAoMiRUC&pg=PA111}}.</ref>
* शीर्ष की डिग्री i, यदि i=j है।
विशेष रूप से, t(G) की गणना करने के लिए, ग्राफ़ के [[लाप्लासियन मैट्रिक्स]] का निर्माण किया जाता है, एक वर्ग मैट्रिक्स जिसमें पंक्तियाँ और स्तंभ दोनों G के शीर्षों द्वारा अनुक्रमित होते हैं। पंक्ति i और स्तंभ j में प्रविष्टि तीन मानों में से एक है:
* शीर्ष की डिग्री i, यदि i=j,
* −1, यदि शीर्ष i और j आसन्न हैं, या
* −1, यदि शीर्ष i और j आसन्न हैं, या
* 0, यदि शीर्ष i और j एक दूसरे से भिन्न हैं लेकिन आसन्न नहीं हैं।
* 0, यदि शीर्ष i और j एक दूसरे से भिन्न हैं किन्तु आसन्न नहीं हैं।
परिणामी मैट्रिक्स [[एकवचन मैट्रिक्स]] है, इसलिए इसका सारणिक शून्य है। हालाँकि, मनमाने ढंग से चुने गए शीर्ष के लिए पंक्ति और स्तंभ को हटाने से एक छोटा मैट्रिक्स बनता है जिसका निर्धारक बिल्कुल t(G) है।
परिणामी आव्यूह [[एकवचन मैट्रिक्स|एकवचन]] है, इसलिए इसका सारणिक शून्य है। चूँकि, आरबिटरेरी रूप से चयन किये गए शीर्ष के लिए पंक्ति और स्तंभ को विस्थापित करने से छोटा आव्यूह बनता है जिसका निर्धारक t(G) है।


===विलोपन-संकुचन===
===विलोपन-संकुचन===
यदि G एक ग्राफ़ या [[मल्टीग्राफ]] है और e, G का एक मनमाना किनारा है, तो G के फैले हुए पेड़ों की संख्या t(G) विलोपन-संकुचन पुनरावृत्ति को संतुष्ट करती है
यदि G ग्राफ़ या [[मल्टीग्राफ]] है और e, G का किनारा है, तो G के स्पैनिंग ट्री की संख्या t(G) विलोपन-संकुचन पुनरावृत्ति t(G) = t(G − e) + t(G/e) को संतुष्ट करती है जहां G − e, e को विस्थापित करके प्राप्त किया गया मल्टीग्राफ है और G/e, G द्वारा e का किनारा संकुचन है।<ref>{{harvtxt|Kocay|Kreher|2004}}, p.&nbsp;109.</ref> इस सूत्र में शब्द t(G − e) G के स्पैनिंग ट्री की गणना करता है जो किनारे e का उपयोग नहीं करते हैं, और शब्द t(G/e) G के स्पैनिंग ट्री की गिनती करता है जो e का उपयोग करते हैं।
t(G) = t(G − e) + t(G/e), जहां G − e, e को हटाकर प्राप्त किया गया मल्टीग्राफ है
और G/e, G द्वारा e का किनारा संकुचन है।<ref>{{harvtxt|Kocay|Kreher|2004}}, p.&nbsp;109.</ref> इस सूत्र में शब्द t(G − e) G के फैले हुए पेड़ों की गणना करता है जो किनारे e का उपयोग नहीं करते हैं, और शब्द t(G/e) G के फैले हुए पेड़ों की गिनती करता है जो e का उपयोग करते हैं।


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


===सभी बहुपद===
===टुटे बहुपद===
{{main|Tutte polynomial}}
{{main|टुटे बहुपद }}


ग्राफ़ के टुटे बहुपद को ग्राफ़ के फैले हुए पेड़ों पर, पेड़ की आंतरिक गतिविधि और बाहरी गतिविधि से गणना की गई शर्तों के योग के रूप में परिभाषित किया जा सकता है। तर्कों (1,1) पर इसका मान फैले हुए पेड़ों की संख्या है या, एक डिस्कनेक्ट किए गए ग्राफ़ में, अधिकतम फैले हुए जंगलों की संख्या है।<ref>{{harvtxt|Bollobás|1998}}, p. 351.</ref>
ग्राफ़ के टुटे बहुपद को ग्राफ़ के स्पैनिंग ट्री पर, ट्री की आंतरिक गतिविधि और बाहरी गतिविधि से गणना की गई नियम के योग के रूप में परिभाषित किया जा सकता है। तर्कों (1,1) पर इसका मान स्पैनिंग ट्री की संख्या है या, डिस्कनेक्ट किए गए ग्राफ़ में, अधिकतम स्पैनिंग फारेस्टों की संख्या है।<ref>{{harvtxt|Bollobás|1998}}, p. 351.</ref>
टुटे बहुपद की गणना विलोपन-संकुचन पुनरावृत्ति का उपयोग करके भी की जा सकती है, लेकिन इसका [[कम्प्यूटेशनल जटिलता सिद्धांत]] उच्च है: इसके तर्कों के कई मूल्यों के लिए, इसकी सटीक गणना करना शार्प-पी-पूर्ण|#पी-पूर्ण है, और यह भी कठिन है एक गारंटीशुदा [[सन्निकटन अनुपात]] के साथ अनुमानित। बिंदु (1,1), जिस पर किरचॉफ के प्रमेय का उपयोग करके इसका मूल्यांकन किया जा सकता है, कुछ अपवादों में से एक है।<ref>{{Citation
 
टुटे बहुपद की गणना विलोपन-संकुचन पुनरावृत्ति का उपयोग करके भी की जा सकती है, किन्तु इसका [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समिष्टता सिद्धांत]] उच्च है: इसके तर्कों के कई मानों के लिए, इसकी त्रुटिहीन गणना P-पूर्ण है, और यह भी कठिन है। बिंदु (1,1) जिस पर किरचॉफ के प्रमेय का उपयोग करके इसका मूल्यांकन किया जा सकता है, कुछ अपवादों में से है।<ref>{{Citation
|last1=Goldberg | first1= L.A. | author1-link = Leslie Ann Goldberg
|last1=Goldberg | first1= L.A. | author1-link = Leslie Ann Goldberg
|last2=Jerrum | first2=  M.
|last2=Jerrum | first2=  M.
Line 123: Line 108:
}}.</ref>
}}.</ref>


 
== एल्गोरिदम ==
==एल्गोरिदम==


===निर्माण===
===निर्माण===
ग्राफ़ का एक एकल फैला हुआ पेड़ [[रैखिक समय]] में या तो [[गहराई-पहली खोज]] या चौड़ाई-पहली खोज द्वारा पाया जा सकता है। ये दोनों एल्गोरिदम दिए गए ग्राफ़ का पता लगाते हैं, एक मनमाना शीर्ष v से शुरू करते हुए, उनके द्वारा खोजे गए शीर्षों के पड़ोसियों के माध्यम से लूपिंग करके और प्रत्येक अज्ञात पड़ोसी को बाद में खोजे जाने वाले डेटा संरचना में जोड़ते हैं। वे इस बात में भिन्न हैं कि क्या यह डेटा संरचना एक स्टैक (अमूर्त डेटा प्रकार) (गहराई-पहली खोज के मामले में) या एक [[कतार (सार डेटा प्रकार)]] (चौड़ाई-पहली खोज के मामले में) है। किसी भी मामले में, कोई व्यक्ति मूल शीर्ष v के अलावा प्रत्येक शीर्ष को उस शीर्ष से जोड़कर एक फैला हुआ पेड़ बना सकता है जहां से इसकी खोज की गई थी। इसके निर्माण के लिए उपयोग किए गए ग्राफ़ अन्वेषण एल्गोरिदम के अनुसार इस पेड़ को गहराई-प्रथम खोज वृक्ष या चौड़ाई-प्रथम खोज वृक्ष के रूप में जाना जाता है।<ref>{{citation |title=The Design and Analysis of Algorithms|series=Monographs in Computer Science |first=Dexter |last=Kozen |author-link=Dexter Kozen |publisher=Springer |year=1992 |isbn=978-0-387-97687-7 |page=19 |url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA19}}.</ref> गहराई-प्रथम खोज वृक्ष ट्रेमॉक्स वृक्ष नामक फैले हुए वृक्षों के एक वर्ग का एक विशेष मामला है, जिसका नाम 19वीं शताब्दी में गहराई-प्रथम खोज के खोजकर्ता के नाम पर रखा गया है।<ref>{{citation
ग्राफ़ का एकल स्पैनिंग ट्री [[रैखिक समय]] में या तो [[गहराई-पहली खोज|गहराई-प्रथम शोध]] या चौड़ाई-प्रथम शोध द्वारा पाया जा सकता है। ये दोनों एल्गोरिदम दिए गए ग्राफ़ को ज्ञात करते हैं, शीर्ष v से प्रारंभ करते हुए, उनके द्वारा शोध किये गए शीर्षों के निकटम के माध्यम से लूपिंग करके और प्रत्येक अज्ञात निकटम को पश्चात में शोध किये जाने वाले डेटा संरचना में जोड़ते हैं। वे इस विचार में भिन्न हैं कि क्या यह डेटा संरचना स्टैक (अमूर्त डेटा प्रकार) (गहराई-प्रथम शोध की स्तिथि में) या [[कतार (सार डेटा प्रकार)|लाइन (सार डेटा प्रकार)]] (चौड़ाई-प्रथम शोध की स्तिथि में) है। किसी भी स्तिथि में, कोई व्यक्ति मूल शीर्ष v के अतिरिक्त प्रत्येक शीर्ष को उस शीर्ष से जोड़कर स्पैनिंग ट्री बना सकता है जहां से इसका शोध किया गया था। इसके निर्माण के लिए उपयोग किए गए ग्राफ़ अन्वेषण एल्गोरिदम के अनुसार इस ट्री को गहराई-प्रथम शोध ट्री या चौड़ाई-प्रथम शोध ट्री के रूप में जाना जाता है।<ref>{{citation |title=The Design and Analysis of Algorithms|series=Monographs in Computer Science |first=Dexter |last=Kozen |author-link=Dexter Kozen |publisher=Springer |year=1992 |isbn=978-0-387-97687-7 |page=19 |url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA19}}.</ref> गहराई-प्रथम शोध ट्री ट्रेमॉक्स ट्री नामक स्पैनिंग ट्री के वर्ग की विशेष स्तिथि है, जिसका नाम 19वीं दशक में गहराई-प्रथम शोध के शोध कर्ता के नाम पर रखा गया है।<ref>{{citation
  | last1 = de Fraysseix | first1 = Hubert
  | last1 = de Fraysseix | first1 = Hubert
  | last2 = Rosenstiehl | first2 = Pierre | author2-link = Pierre Rosenstiehl
  | last2 = Rosenstiehl | first2 = Pierre | author2-link = Pierre Rosenstiehl
Line 139: Line 123:
  | volume = 13
  | volume = 13
  | year = 1982}}.</ref>
  | year = 1982}}.</ref>
प्रोसेसर के एक सेट के बीच संचार बनाए रखने के एक तरीके के रूप में, पेड़ों को फैलाना समानांतर और वितरित कंप्यूटिंग में महत्वपूर्ण है; उदाहरण के लिए [[सूचना श्रंखला तल]] उपकरणों द्वारा उपयोग किए जाने वाले स्पैनिंग ट्री प्रोटोकॉल या वितरित कंप्यूटिंग के लिए शाउट (प्रोटोकॉल) देखें। हालाँकि, अनुक्रमिक कंप्यूटरों पर फैले हुए पेड़ों के निर्माण के लिए गहराई-प्रथम और चौड़ाई-प्रथम विधियाँ समानांतर और वितरित कंप्यूटरों के लिए उपयुक्त नहीं हैं।<ref>{{citation
 
प्रोसेसर के समुच्चय के मध्य संचार बनाए रखने के विधि के रूप में, ट्री को स्पैनिंग समानांतर और वितरित कंप्यूटिंग में महत्वपूर्ण है; उदाहरण के लिए [[सूचना श्रंखला तल]] उपकरणों द्वारा उपयोग किए जाने वाले स्पैनिंग ट्री प्रोटोकॉल या वितरित कंप्यूटिंग के लिए शाउट (प्रोटोकॉल) देखें। चूँकि, अनुक्रमिक कंप्यूटरों पर स्पैनिंग ट्री के निर्माण के लिए गहराई-प्रथम और चौड़ाई-प्रथम विधियाँ समानांतर और वितरित कंप्यूटरों के लिए उपयुक्त नहीं हैं।<ref>{{citation
  | last = Reif | first = John H. | author-link = John Reif
  | last = Reif | first = John H. | author-link = John Reif
  | doi = 10.1016/0020-0190(85)90024-9
  | doi = 10.1016/0020-0190(85)90024-9
Line 148: Line 133:
  | title = Depth-first search is inherently sequential
  | title = Depth-first search is inherently sequential
  | volume = 20
  | volume = 20
  | year = 1985}}.</ref> इसके बजाय, शोधकर्ताओं ने गणना के इन मॉडलों में फैले हुए पेड़ों को खोजने के लिए कई और विशिष्ट एल्गोरिदम तैयार किए हैं।<ref>{{citation
  | year = 1985}}.</ref> इसके अतिरिक्त, शोधकर्ताओं ने गणना के इन मॉडलों में स्पैनिंग ट्री के शोध के लिए कई और विशिष्ट एल्गोरिदम तैयार किए हैं।<ref>{{citation
  | last1 = Gallager | first1 = R. G.
  | last1 = Gallager | first1 = R. G.
  | last2 = Humblet | first2 = P. A.
  | last2 = Humblet | first2 = P. A.
Line 179: Line 164:
  | year = 2005}}.</ref>
  | year = 2005}}.</ref>


'''अनुकूलन'''


===अनुकूलन===
ग्राफ़ सिद्धांत के कुछ क्षेत्रों में [[भारित ग्राफ]] का न्यूनतम स्पैनिंग ट्री का शोध करना प्रायः उपयोगी होता है। स्पैनिंग ट्री पर अन्य अनुकूलन समस्याओं का भी अध्ययन किया गया है, जिसमें अधिकतम स्पैनिंग ट्री, न्यूनतम ट्री जो कम से कम k शिखर तक स्पैनिंग है, प्रति शीर्ष सबसे कम किनारों वाला स्पैनिंग ट्री, सबसे अधिक लीफ वाला स्पैनिंग ट्री  सम्मिलित हैं। सबसे [[अधिकतम पत्ती फैलाने वाला वृक्ष|न्यूनतम लीफ वाला ट्री]], ([[हैमिल्टनियन पथ समस्या]] से निकटता से संबंधित), में स्पैनिंग न्यूनतम व्यास, और ट्री में स्पैनिंग न्यूनतम स्पैनिंग।) है।<ref name="sts">{{citation |last=Eppstein |first=David |author-link=David Eppstein |contribution=Spanning trees and spanners |title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link=Jorge Urrutia Galicia |publisher=Elsevier |year=1999 |pages=425–461 |contribution-url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}.</ref><ref>{{citation |last1=Wu |first1=Bang Ye |last2=Chao |first2=Kun-Mao |title=Spanning Trees and Optimization Problems |year=2004 |publisher=CRC Press |isbn=1-58488-436-3}}.</ref>
ग्राफ़ सिद्धांत के कुछ क्षेत्रों में [[भारित ग्राफ]]़ का न्यूनतम फैले हुए पेड़ को ढूंढना अक्सर उपयोगी होता है। स्पैनिंग पेड़ों पर अन्य अनुकूलन समस्याओं का भी अध्ययन किया गया है, जिसमें अधिकतम स्पैनिंग वृक्ष, न्यूनतम वृक्ष जो कम से कम k शिखर तक फैला है, न्यूनतम डिग्री स्पैनिंग वृक्ष, [[अधिकतम पत्ती फैलाने वाला वृक्ष]], सबसे कम पत्तियों वाला स्पैनिंग वृक्ष (निकटता से संबंधित) शामिल हैं। [[हैमिल्टनियन पथ समस्या]]), न्यूनतम व्यास फैला हुआ पेड़, और न्यूनतम फैलाव फैला हुआ पेड़।<ref name="sts">{{citation |last=Eppstein |first=David |author-link=David Eppstein |contribution=Spanning trees and spanners |title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link=Jorge Urrutia Galicia |publisher=Elsevier |year=1999 |pages=425–461 |contribution-url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf}}.</ref><ref>{{citation |last1=Wu |first1=Bang Ye |last2=Chao |first2=Kun-Mao |title=Spanning Trees and Optimization Problems |year=2004 |publisher=CRC Press |isbn=1-58488-436-3}}.</ref>
[[यूक्लिडियन विमान]] जैसे ज्यामितीय स्थान में बिंदुओं के परिमित सेट के लिए इष्टतम फैले हुए पेड़ की समस्याओं का भी अध्ययन किया गया है। ऐसे इनपुट के लिए, एक फैला हुआ पेड़ फिर से एक पेड़ होता है जिसके शीर्ष पर दिए गए बिंदु होते हैं। पेड़ की गुणवत्ता को ग्राफ़ की तरह ही मापा जाता है, प्रत्येक किनारे के वजन के रूप में बिंदुओं के जोड़े के बीच यूक्लिडियन दूरी का उपयोग किया जाता है। इस प्रकार, उदाहरण के लिए, एक [[यूक्लिडियन न्यूनतम फैलाव वाला पेड़]], यूक्लिडियन एज वेट के साथ एक पूर्ण ग्राफ में ग्राफ न्यूनतम स्पैनिंग ट्री के समान है। हालाँकि, अनुकूलन समस्या को हल करने के लिए इस ग्राफ़ का निर्माण करना आवश्यक नहीं है; उदाहरण के लिए, यूक्लिडियन न्यूनतम स्पैनिंग ट्री समस्या को [[डेलाउने त्रिकोणासन]] का निर्माण करके और फिर परिणामी ट्राइएंग्यूलेशन पर एक रैखिक समय [[ समतलीय ग्राफ ]] न्यूनतम स्पैनिंग ट्री एल्गोरिदम लागू करके ओ (एन लॉग एन) समय में अधिक कुशलता से हल किया जा सकता है।<ref name="sts" />


[[यूक्लिडियन विमान]] जैसे ज्यामितीय समिष्ट में बिंदुओं के परिमित समुच्चय के लिए इष्टतम स्पैनिंग ट्री की समस्याओं का भी अध्ययन किया गया है। ऐसे इनपुट के लिए, स्पैनिंग ट्री फिर से ट्री होता है जिसके शीर्ष पर दिए गए बिंदु होते हैं। ट्री की गुणवत्ता को ग्राफ़ के जैसे ही मापा जाता है, प्रत्येक किनारे के भार के रूप में बिंदुओं के जोड़े के मध्य यूक्लिडियन दूरी का उपयोग किया जाता है। इस प्रकार, उदाहरण के लिए, [[यूक्लिडियन न्यूनतम फैलाव वाला पेड़|यूक्लिडियन न्यूनतम स्पैनिंग वाला ट्री]], यूक्लिडियन एज वेट के साथ पूर्ण ग्राफ में ग्राफ न्यूनतम स्पैनिंग ट्री के समान है। चूँकि, अनुकूलन समस्या को समाधान करने के लिए इस ग्राफ़ का निर्माण करना आवश्यक नहीं है; उदाहरण के लिए, यूक्लिडियन न्यूनतम स्पैनिंग ट्री समस्या को [[डेलाउने त्रिकोणासन]] का निर्माण करके और फिर परिणामी ट्राइएंग्यूलेशन पर  रैखिक समय [[ समतलीय ग्राफ |समतलीय ग्राफ]] न्यूनतम स्पैनिंग ट्री एल्गोरिदम प्रारंभ करके ''O''(''n'' log ''n'') समय में अधिक कुशलता से समाधान किया जा सकता है।<ref name="sts" />


===यादृच्छिकरण===
'''यादृच्छिकरण'''
समान संभावना वाले सभी फैले हुए पेड़ों में से यादृच्छिक रूप से चुने गए फैले हुए पेड़ को एकसमान फैले हुए पेड़ कहा जाता है। विल्सन के एल्गोरिदम का उपयोग दिए गए ग्राफ़ पर यादृच्छिक वॉक लेने और इस वॉक द्वारा बनाए गए चक्रों को मिटाने की प्रक्रिया द्वारा बहुपद समय में समान फैले हुए पेड़ों को उत्पन्न करने के लिए किया जा सकता है।<ref>{{citation
 
समान संभावना वाले सभी स्पैनिंग ट्री में से यादृच्छिक रूप से चयन किये गए स्पैनिंग ट्री को समान स्पैनिंग ट्री कहा जाता है। विल्सन के एल्गोरिदम का उपयोग दिए गए ग्राफ़ पर यादृच्छिक वॉक लेने और इस वॉक द्वारा बनाए गए चक्रों को विस्थापित्त करने की प्रक्रिया द्वारा बहुपद समय में समान स्पैनिंग ट्री को उत्पन्न करने के लिए किया जा सकता है।<ref>{{citation
  | last = Wilson | first = David Bruce
  | last = Wilson | first = David Bruce
  | contribution = Generating random spanning trees more quickly than the cover time
  | contribution = Generating random spanning trees more quickly than the cover time
Line 195: Line 181:
  | year = 1996| title-link = Symposium on Theory of Computing
  | year = 1996| title-link = Symposium on Theory of Computing
  }}.</ref>
  }}.</ref>
यादृच्छिक रूप से लेकिन समान रूप से नहीं फैले हुए पेड़ों को उत्पन्न करने के लिए एक वैकल्पिक मॉडल [[यादृच्छिक न्यूनतम फैले हुए पेड़]] है। इस मॉडल में, ग्राफ़ के किनारों को यादृच्छिक भार दिया जाता है और फिर भारित ग्राफ़ का न्यूनतम स्पैनिंग ट्री बनाया जाता है।<ref>{{citation
 
यादृच्छिक रूप से किन्तु समान रूप से नहीं स्पैनिंग ट्री को उत्पन्न करने के लिए वैकल्पिक मॉडल [[यादृच्छिक न्यूनतम फैले हुए पेड़|यादृच्छिक न्यूनतम स्पैनिंग ट्री]] है। इस मॉडल में, ग्राफ़ के किनारों को यादृच्छिक भार दिया जाता है और फिर भारित ग्राफ़ का न्यूनतम स्पैनिंग ट्री बनाया जाता है।<ref>{{citation
  | last1 = McDiarmid | first1 = Colin
  | last1 = McDiarmid | first1 = Colin
  | last2 = Johnson | first2 = Theodore
  | last2 = Johnson | first2 = Theodore
Line 209: Line 196:
  | year = 1997}}.</ref>
  | year = 1997}}.</ref>


'''गणना'''


===गणना===
क्योंकि ग्राफ़ में तीव्रता से स्पैनिंग कई ट्री हो सकते हैं, उन सभी को बहुपद समय में सूचीबद्ध करना संभव नहीं है। चूँकि, एल्गोरिदम सभी स्पैनिंग ट्री को प्रति ट्री बहुपद समय में सूचीबद्ध करने के लिए जाने जाते हैं।<ref>{{citation
क्योंकि एक ग्राफ़ में तेजी से फैले हुए कई पेड़ हो सकते हैं, उन सभी को बहुपद समय में सूचीबद्ध करना संभव नहीं है। हालाँकि, एल्गोरिदम सभी फैले हुए पेड़ों को प्रति पेड़ बहुपद समय में सूचीबद्ध करने के लिए जाने जाते हैं।<ref>{{citation
  | last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow
  | last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow
  | last2 = Myers | first2 = Eugene W. | author2-link = Eugene Myers
  | last2 = Myers | first2 = Eugene W. | author2-link = Eugene Myers
Line 223: Line 210:
  | year = 1978}}</ref>
  | year = 1978}}</ref>


== अनंत ग्राफ़ में ==
प्रत्येक परिमित जुड़े ग्राफ़ में स्पैनिंग ट्री होता है। चूँकि, अनंत जुड़े ग्राफ़ के लिए, स्पैनिंग ट्री का अस्तित्व रूचि के सिद्धांत के समान है। अनंत ग्राफ जुड़ा हुआ है यदि इसके शीर्षों की प्रत्येक जोड़ी  परिमित पथ के समापन बिंदुओं की जोड़ी बनाती है। परिमित ग्राफ़ के जैसे, ट्री जुड़ा हुआ ग्राफ़ होता है जिसमें कोई परिमित चक्र नहीं होता है, और स्पैनिंग ट्री को या तो किनारों के अधिकतम चक्रीय समुच्चय के रूप में या ट्री के रूप में परिभाषित किया जा सकता है जिसमें प्रत्येक शीर्ष सम्मिलित होता है।<ref name="serre" />


==अनंत ग्राफ़ में==
ग्राफ़ के भीतर ट्री को आंशिक रूप से उनके उप-ग्राफ संबंध द्वारा क्रमबद्ध किया जा सकता है, और इस आंशिक क्रम में किसी भी अनंत श्रृंखला में ऊपरी सीमा होती है (श्रृंखला में ट्री का संघ)। ज़ोर्न की लेम्मा, रूचि के सिद्धांत के कई समकक्ष वर्णन के लिए आवश्यक है कि आंशिक क्रम जिसमें सभी श्रृंखलाएं ऊपरी सीमा पर हों, उनमें अधिकतम तत्व हो; ग्राफ़ के ट्री पर आंशिक क्रम में, यह अधिकतम तत्व स्पैनिंग ट्री होना चाहिए। इसलिए, यदि ज़ोर्न की लेम्मा मान ली जाए, तो प्रत्येक अनंत जुड़े ग्राफ में स्पैनिंग ट्री होता है।<ref name="serre">{{citation|title=Trees|first=Jean-Pierre|last=Serre|author-link=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}.</ref>
प्रत्येक परिमित जुड़े ग्राफ़ में एक फैला हुआ वृक्ष होता है। हालाँकि, अनंत जुड़े ग्राफ़ के लिए, फैले हुए पेड़ों का अस्तित्व पसंद के सिद्धांत के बराबर है। एक अनंत ग्राफ जुड़ा हुआ है यदि इसके शीर्षों की प्रत्येक जोड़ी एक परिमित पथ के समापन बिंदुओं की जोड़ी बनाती है। परिमित ग्राफ़ की तरह, एक पेड़ एक जुड़ा हुआ ग्राफ़ होता है जिसमें कोई परिमित चक्र नहीं होता है, और एक फैले हुए पेड़ को या तो किनारों के अधिकतम चक्रीय सेट के रूप में या एक पेड़ के रूप में परिभाषित किया जा सकता है जिसमें प्रत्येक शीर्ष शामिल होता है।<ref name="serre" />


एक ग्राफ़ के भीतर पेड़ों को आंशिक रूप से उनके सबग्राफ संबंध द्वारा क्रमबद्ध किया जा सकता है, और इस आंशिक क्रम में किसी भी अनंत श्रृंखला में एक ऊपरी सीमा होती है (श्रृंखला में पेड़ों का संघ)। ज़ोर्न की लेम्मा, पसंद के सिद्धांत के कई समकक्ष बयानों में से एक, के लिए आवश्यक है कि एक आंशिक क्रम जिसमें सभी श्रृंखलाएं ऊपरी सीमा पर हों, उनमें अधिकतम तत्व हो; ग्राफ़ के पेड़ों पर आंशिक क्रम में, यह अधिकतम तत्व एक फैला हुआ पेड़ होना चाहिए। इसलिए, यदि ज़ोर्न की लेम्मा मान ली जाए, तो प्रत्येक अनंत जुड़े ग्राफ में एक फैला हुआ पेड़ होता है।<ref name="serre">{{citation|title=Trees|first=Jean-Pierre|last=Serre|author-link=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}.</ref>
दूसरी दिशा में समुच्चयों के सदस्य को देखते हुए, अनंत ग्राफ़ का निर्माण करना संभव है, जिससे ग्राफ़ का प्रत्येक स्पैनिंग ट्री समुच्चयों के सदस्य के लोकप्रिय फलन से युग्मित होता है। इसलिए, यदि प्रत्येक अनंत जुड़े ग्राफ़ में स्पैनिंग ट्री है, तो लोकप्रिय का सिद्धांत सत्य है।<ref>{{citation
दूसरी दिशा में, सेटों के परिवार को देखते हुए, एक अनंत ग्राफ़ का निर्माण करना संभव है, ताकि ग्राफ़ का प्रत्येक फैला हुआ पेड़ सेटों के परिवार के एक पसंदीदा फ़ंक्शन से मेल खाए। इसलिए,
यदि प्रत्येक अनंत जुड़े ग्राफ़ में एक फैला हुआ पेड़ है, तो पसंद का सिद्धांत सत्य है।<ref>{{citation
  | last = Soukup | first = Lajos
  | last = Soukup | first = Lajos
  | contribution = Infinite combinatorics: from finite to infinite
  | contribution = Infinite combinatorics: from finite to infinite
Line 242: Line 228:
  | year = 2008}}. See in particular Theorem 2.1, [https://books.google.com/books?id=kIKW18ENfUMC&pg=PA192 pp.&nbsp;192–193].</ref>
  | year = 2008}}. See in particular Theorem 2.1, [https://books.google.com/books?id=kIKW18ENfUMC&pg=PA192 pp.&nbsp;192–193].</ref>


 
== निर्देशित मल्टीग्राफ में ==
==निर्देशित मल्टीग्राफ में==
स्पैनिंग ट्री के विचार को निर्देशित मल्टीग्राफ के लिए सामान्यीकृत किया जा सकता है।<ref name="Levine09">{{cite journal
फैले हुए पेड़ के विचार को निर्देशित मल्टीग्राफ के लिए सामान्यीकृत किया जा सकता है।<ref name="Levine09">{{cite journal
  | title = Sandpile groups and spanning trees of directed line graphs
  | title = Sandpile groups and spanning trees of directed line graphs
  | journal = Journal of Combinatorial Theory, Series A
  | journal = Journal of Combinatorial Theory, Series A
Line 255: Line 240:
  | first = Lionel | last = Levine
  | first = Lionel | last = Levine
| arxiv = 0906.2809
| arxiv = 0906.2809
  }}</ref> एक निर्देशित मल्टीग्राफ G पर एक शीर्ष v दिया गया है, v पर निहित एक ओरिएंटेड स्पैनिंग ट्री T, G का एक चक्रीय उपसमूह है जिसमें v के अलावा प्रत्येक शीर्ष पर आउटडिग्री 1 है। यह परिभाषा केवल तभी संतुष्ट होती है जब T की शाखाएं v की ओर इंगित करती हैं।
  }}</ref> निर्देशित मल्टीग्राफ G पर शीर्ष v दिया गया है, v पर निहित ओरिएंटेड स्पैनिंग ट्री T, G का चक्रीय उप-समूह है जिसमें v के अतिरिक्त प्रत्येक शीर्ष पर आउटडिग्री 1 है। यह परिभाषा केवल तभी संतुष्ट होती है जब T की शाखाएं v की ओर प्रदर्शित करती हैं।


==यह भी देखें==
==यह भी देखें==
* [[बाढ़ एल्गोरिथ्म]]
* [[बाढ़ एल्गोरिथ्म|फ्लूडिंग एल्गोरिथ्म]]
* अच्छा स्पैनिंग ट्री - एम्बेडेड प्लेनर ग्राफ के [[अच्छा फैला हुआ पेड़]]
* उत्तम स्पैनिंग ट्री - एम्बेडेड प्लेनर ग्राफ के [[अच्छा फैला हुआ पेड़|उत्तम स्पैनिंग ट्री]]


==संदर्भ==
==संदर्भ==
Line 265: Line 250:


{{Authority control}}
{{Authority control}}
[[Category: फैला हुआ पेड़| फैला हुआ पेड़]] [[Category: पसंद का सिद्धांत]] [[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 09/07/2023]]
[[Category:Created On 09/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
[[Category:पसंद का सिद्धांत]]
[[Category:फैला हुआ पेड़| फैला हुआ पेड़]]

Latest revision as of 10:10, 2 August 2023

For नेटवर्क प्रोटोकॉल, see स्पेनिंग ट्री प्रोटोकॉल. For अन्य उपयोग, see स्पेनिंग ट्री (disambiguation).
ग्रिड ग्राफ का स्पेनिंग ट्री (नीले भारी किनारे)।

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

अनुप्रयोग

डिज्क्स्ट्रा के एल्गोरिदम और A* सर्च एल्गोरिदम सहित कई पाथफाइंडिंग एल्गोरिदम, समस्या को समाधान करने में मध्यवर्ती चरण के रूप में आंतरिक रूप से स्पैनिंग ट्री का निर्माण करते हैं।

विद्युत् नेटवर्क, वायरिंग कनेक्शन, पाइपिंग, स्वचालित वाक् पहचान आदि के व्यय को कम करने के लिए, लोग प्रायः एल्गोरिदम का उपयोग करते हैं जो न्यूनतम स्पैनिंग ट्री शोध की प्रक्रिया में मध्यवर्ती चरणों के रूप में धीरे-धीरे स्पैनिंग ट्री (या ऐसे कई ट्री) बनाते हैं।[2]

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

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

परिभाषाएँ

ट्री जुड़ा हुआ अप्रत्यक्ष ग्राफ है जिसमें कोई चक्र नहीं है (ग्राफ सिद्धांत)। यह ग्राफ G का स्पैनिंग ट्री है यदि यह G तक स्पैनिंग है (अर्थात, इसमें G का प्रत्येक शीर्ष सम्मिलित है) और यह G का उप-समूह है (ट्री का प्रत्येक किनारा G का है)। कनेक्टेड ग्राफ G के स्पैनिंग ट्री को G के किनारों के अधिकतम समुच्चय के रूप में भी परिभाषित किया जा सकता है जिसमें कोई चक्र नहीं है, या किनारों के न्यूनतम समुच्चय के रूप में जो सभी शीर्षों को जोड़ता है।

मौलिक चक्र

स्पैनिंग ट्री में सिर्फ किनारा जोड़ने से चक्र बन जाएगा; ऐसे चक्र को उस ट्री के संबंध में मौलिक चक्र कहा जाता है। स्पैनिंग ट्री में नहीं अन्यथा प्रत्येक किनारे के लिए भिन्न मौलिक चक्र होता है; इस प्रकार, मूलभूत चक्रों और किनारों के मध्य पत्राचार होता है जो स्पैनिंग ट्री में नहीं होता है। V शीर्षों के साथ जुड़े ग्राफ़ के लिए, किसी भी स्पैनिंग ट्री में V - 1 किनारे होंगे, और इस प्रकार, E किनारों के ग्राफ़ और उसके स्पैनिंग ट्री में से E - V + 1 मौलिक चक्र (स्पैनिंग ट्री में सम्मिलित किनारों की संख्या से घटाए गए किनारों की संख्या; स्पैनिंग ट्री में सम्मिलित नहीं किए गए किनारों की संख्या) है। किसी भी स्पैनिंग ट्री के लिए सभी E − V + 1 मौलिक चक्रों का समुच्चय चक्र आधार बनाता है, अर्थात, चक्र समिष्ट के लिए आधार है।[3]

मौलिक कटसेट्स

मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए स्पैनिंग ट्री के संबंध में मौलिक कटसेट्स की धारणा भी दोहरी है। स्पैनिंग ट्री के केवल किनारे को विस्थापित करके, शीर्षों को दो असंयुक्त समुच्चयों में विभाजित किया गया है। मौलिक कटसेट्स को किनारों के समुच्चय के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूर्ण करने के लिए ग्राफ़ G से विस्थापित किया जाना चाहिए। इस प्रकार, प्रत्येक स्पैनिंग ट्री V के समुच्चय को परिभाषित करता है- 1 मौलिक कटसेट्स, स्पैनिंग ट्री के प्रत्येक किनारे के लिए है।[4]

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

स्पैनिंग फारेस्ट

ग्राफ़ में स्पैनिंग फारेस्ट उप-ग्राफ़ है जो अतिरिक्त आवश्यकता वाला फारेस्ट है। उपयोग में दो असंगत आवश्यकताएँ हैं, जिनमें से अपेक्षाकृत दुर्लभ है।

  • लगभग सभी ग्राफ़ सिद्धांत पुस्तकें और लेख स्पैनिंग फारेस्ट को ऐसे फारेस्ट के रूप में परिभाषित करते हैं जो सभी शीर्षों तक स्पैनिंग है, जिसका अर्थ केवल यह है कि ग्राफ़ का प्रत्येक शीर्ष फारेस्ट में शीर्ष है। कनेक्टेड ग्राफ़ में भिन्न स्पैनिंग फारेस्ट हो सकता है, जैसे कि बिना किनारों वाला फारेस्ट, जिसमें प्रत्येक शीर्ष एकल-शीर्ष ट्री बनाता है।[6][7]
  • कुछ ग्राफ़ सिद्धांत लेखक स्पैनिंग फारेस्ट को दिए गए ग्राफ़ का अधिकतम एसाइक्लिक उप-ग्राफ, या समकक्ष रूप से ग्राफ़ के प्रत्येक कनेक्टेड घटक (ग्राफ सिद्धांत) में स्पैनिंग ट्री से युक्त उप-ग्राफ के रूप में परिभाषित करते हैं।[8]

इन दो परिभाषाओं के मध्य भ्रम से बचने के लिए, ग्रॉस & येलेन (2005) दिए गए ग्राफ के समान घटकों (अर्थात, अधिकतम फारेस्ट) के साथ स्पैनिंग फारेस्ट के लिए पूर्ण स्पैनिंग फारेस्ट शब्द का विचार दें रहे है, जबकि बॉन्डी & मूर्ति (2008) इसके अतिरिक्त इस प्रकार के फारेस्ट को अधिकतम स्पैनिंग फारेस्ट कहा जाता है (जो अनावश्यक है, क्योंकि अधिकतम फारेस्ट में आवश्यक रूप से प्रत्येक शीर्ष सम्मिलित होता है)।[9]

स्पैनिंग ट्री की गिनती

केली का सूत्र पूर्ण ग्राफ़ पर स्पैनिंग ट्री की संख्या की गणना करता है। वहाँ हैं में ट्री , में ट्री , और में ट्री

किसी कनेक्टेड ग्राफ़ के स्पैनिंग ट्री की संख्या t(G) उत्तम रूप से अध्ययन किया गया अपरिवर्तनीय (गणित) है।

विशिष्ट ग्राफ़ में

कुछ स्थितियों में, सीधे t(G) की गणना करना सरल है:

  • यदि G स्वयं ट्री है, तो t(G) = 1 है।
  • जब G, n शीर्षों वाला चक्र ग्राफ Cn है, तो t(G) = n है।
  • शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र[10] स्पैनिंग ट्री की संख्या nn − 2 इस प्रकार देता है।
  • यदि G पूर्ण द्विदलीय ग्राफ है , तब है।[6]
  • एन-आयामी हाइपरक्यूब ग्राफ के लिए ,[11] स्पैनिंग ट्री की संख्या है।

आरबिटरेरी ग्राफ़ में

Main article: किरचॉफ का प्रमेय

अधिक सामान्यतः, किसी भी ग्राफ़ G के लिए, संख्या t(G) की गणना किरचॉफ के आव्यूह-ट्री प्रमेय का उपयोग करके, ग्राफ से प्राप्त आव्यूह के निर्धारक के रूप में बहुपद समय में की जा सकती है।

[12]विशेष रूप से, t(G) की गणना करने के लिए, ग्राफ़ के लाप्लासियन आव्यूह का निर्माण किया जाता है, वर्ग आव्यूह जिसमें पंक्तियाँ और स्तंभ दोनों G के शीर्षों द्वारा अनुक्रमित होते हैं। पंक्ति i और स्तंभ j में प्रविष्टि तीन मानों में से है:

  • शीर्ष की डिग्री i, यदि i=j है।
  • −1, यदि शीर्ष i और j आसन्न हैं, या
  • 0, यदि शीर्ष i और j एक दूसरे से भिन्न हैं किन्तु आसन्न नहीं हैं।

परिणामी आव्यूह एकवचन है, इसलिए इसका सारणिक शून्य है। चूँकि, आरबिटरेरी रूप से चयन किये गए शीर्ष के लिए पंक्ति और स्तंभ को विस्थापित करने से छोटा आव्यूह बनता है जिसका निर्धारक t(G) है।

विलोपन-संकुचन

यदि G ग्राफ़ या मल्टीग्राफ है और e, G का किनारा है, तो G के स्पैनिंग ट्री की संख्या t(G) विलोपन-संकुचन पुनरावृत्ति t(G) = t(G − e) + t(G/e) को संतुष्ट करती है जहां G − e, e को विस्थापित करके प्राप्त किया गया मल्टीग्राफ है और G/e, G द्वारा e का किनारा संकुचन है।[13] इस सूत्र में शब्द t(G − e) G के स्पैनिंग ट्री की गणना करता है जो किनारे e का उपयोग नहीं करते हैं, और शब्द t(G/e) G के स्पैनिंग ट्री की गिनती करता है जो e का उपयोग करते हैं।

इस सूत्र में, यदि दिया गया ग्राफ G मल्टीग्राफ है, या यदि संकुचन के कारण दो शीर्ष एक दूसरे से कई किनारों से जुड़े होते हैं, तो अनावश्यक किनारों को नहीं विस्थापित किया जाना चाहिए, क्योंकि इससे त्रुटिपूर्ण कुल हो जाएगा। उदाहरण के लिए, k किनारों द्वारा दो शीर्षों को जोड़ने वाले बांड ग्राफ में k भिन्न-भिन्न स्पैनिंग ट्री होते हैं, जिनमें से प्रत्येक में इन किनारों में से ही होता है।

टुटे बहुपद

Main article: टुटे बहुपद

ग्राफ़ के टुटे बहुपद को ग्राफ़ के स्पैनिंग ट्री पर, ट्री की आंतरिक गतिविधि और बाहरी गतिविधि से गणना की गई नियम के योग के रूप में परिभाषित किया जा सकता है। तर्कों (1,1) पर इसका मान स्पैनिंग ट्री की संख्या है या, डिस्कनेक्ट किए गए ग्राफ़ में, अधिकतम स्पैनिंग फारेस्टों की संख्या है।[14]

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

एल्गोरिदम

निर्माण

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

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

अनुकूलन

ग्राफ़ सिद्धांत के कुछ क्षेत्रों में भारित ग्राफ का न्यूनतम स्पैनिंग ट्री का शोध करना प्रायः उपयोगी होता है। स्पैनिंग ट्री पर अन्य अनुकूलन समस्याओं का भी अध्ययन किया गया है, जिसमें अधिकतम स्पैनिंग ट्री, न्यूनतम ट्री जो कम से कम k शिखर तक स्पैनिंग है, प्रति शीर्ष सबसे कम किनारों वाला स्पैनिंग ट्री, सबसे अधिक लीफ वाला स्पैनिंग ट्री सम्मिलित हैं। सबसे न्यूनतम लीफ वाला ट्री, (हैमिल्टनियन पथ समस्या से निकटता से संबंधित), में स्पैनिंग न्यूनतम व्यास, और ट्री में स्पैनिंग न्यूनतम स्पैनिंग।) है।[20][21]

यूक्लिडियन विमान जैसे ज्यामितीय समिष्ट में बिंदुओं के परिमित समुच्चय के लिए इष्टतम स्पैनिंग ट्री की समस्याओं का भी अध्ययन किया गया है। ऐसे इनपुट के लिए, स्पैनिंग ट्री फिर से ट्री होता है जिसके शीर्ष पर दिए गए बिंदु होते हैं। ट्री की गुणवत्ता को ग्राफ़ के जैसे ही मापा जाता है, प्रत्येक किनारे के भार के रूप में बिंदुओं के जोड़े के मध्य यूक्लिडियन दूरी का उपयोग किया जाता है। इस प्रकार, उदाहरण के लिए, यूक्लिडियन न्यूनतम स्पैनिंग वाला ट्री, यूक्लिडियन एज वेट के साथ पूर्ण ग्राफ में ग्राफ न्यूनतम स्पैनिंग ट्री के समान है। चूँकि, अनुकूलन समस्या को समाधान करने के लिए इस ग्राफ़ का निर्माण करना आवश्यक नहीं है; उदाहरण के लिए, यूक्लिडियन न्यूनतम स्पैनिंग ट्री समस्या को डेलाउने त्रिकोणासन का निर्माण करके और फिर परिणामी ट्राइएंग्यूलेशन पर रैखिक समय समतलीय ग्राफ न्यूनतम स्पैनिंग ट्री एल्गोरिदम प्रारंभ करके O(n log n) समय में अधिक कुशलता से समाधान किया जा सकता है।[20]

यादृच्छिकरण

समान संभावना वाले सभी स्पैनिंग ट्री में से यादृच्छिक रूप से चयन किये गए स्पैनिंग ट्री को समान स्पैनिंग ट्री कहा जाता है। विल्सन के एल्गोरिदम का उपयोग दिए गए ग्राफ़ पर यादृच्छिक वॉक लेने और इस वॉक द्वारा बनाए गए चक्रों को विस्थापित्त करने की प्रक्रिया द्वारा बहुपद समय में समान स्पैनिंग ट्री को उत्पन्न करने के लिए किया जा सकता है।[22]

यादृच्छिक रूप से किन्तु समान रूप से नहीं स्पैनिंग ट्री को उत्पन्न करने के लिए वैकल्पिक मॉडल यादृच्छिक न्यूनतम स्पैनिंग ट्री है। इस मॉडल में, ग्राफ़ के किनारों को यादृच्छिक भार दिया जाता है और फिर भारित ग्राफ़ का न्यूनतम स्पैनिंग ट्री बनाया जाता है।[23]

गणना

क्योंकि ग्राफ़ में तीव्रता से स्पैनिंग कई ट्री हो सकते हैं, उन सभी को बहुपद समय में सूचीबद्ध करना संभव नहीं है। चूँकि, एल्गोरिदम सभी स्पैनिंग ट्री को प्रति ट्री बहुपद समय में सूचीबद्ध करने के लिए जाने जाते हैं।[24]

अनंत ग्राफ़ में

प्रत्येक परिमित जुड़े ग्राफ़ में स्पैनिंग ट्री होता है। चूँकि, अनंत जुड़े ग्राफ़ के लिए, स्पैनिंग ट्री का अस्तित्व रूचि के सिद्धांत के समान है। अनंत ग्राफ जुड़ा हुआ है यदि इसके शीर्षों की प्रत्येक जोड़ी परिमित पथ के समापन बिंदुओं की जोड़ी बनाती है। परिमित ग्राफ़ के जैसे, ट्री जुड़ा हुआ ग्राफ़ होता है जिसमें कोई परिमित चक्र नहीं होता है, और स्पैनिंग ट्री को या तो किनारों के अधिकतम चक्रीय समुच्चय के रूप में या ट्री के रूप में परिभाषित किया जा सकता है जिसमें प्रत्येक शीर्ष सम्मिलित होता है।[25]

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

दूसरी दिशा में समुच्चयों के सदस्य को देखते हुए, अनंत ग्राफ़ का निर्माण करना संभव है, जिससे ग्राफ़ का प्रत्येक स्पैनिंग ट्री समुच्चयों के सदस्य के लोकप्रिय फलन से युग्मित होता है। इसलिए, यदि प्रत्येक अनंत जुड़े ग्राफ़ में स्पैनिंग ट्री है, तो लोकप्रिय का सिद्धांत सत्य है।[26]

निर्देशित मल्टीग्राफ में

स्पैनिंग ट्री के विचार को निर्देशित मल्टीग्राफ के लिए सामान्यीकृत किया जा सकता है।[27] निर्देशित मल्टीग्राफ G पर शीर्ष v दिया गया है, v पर निहित ओरिएंटेड स्पैनिंग ट्री T, G का चक्रीय उप-समूह है जिसमें v के अतिरिक्त प्रत्येक शीर्ष पर आउटडिग्री 1 है। यह परिभाषा केवल तभी संतुष्ट होती है जब T की शाखाएं v की ओर प्रदर्शित करती हैं।

यह भी देखें

संदर्भ

  1. ↑ "पेड़". NetworkX 2.6.2 documentation. Retrieved 2021-12-10. For trees and arborescence, the adjective "spanning" may be added to designate that the graph, when considered as a forest/branching, consists of a single tree/arborescence that includes all nodes in the graph.
  2. ↑ Graham, R. L.; Hell, Pavol (1985). "न्यूनतम स्पैनिंग वृक्ष समस्या के इतिहास पर" (PDF).
  3. ↑ Kocay & Kreher (2004), pp. 65–67.
  4. ↑ Kocay & Kreher (2004), pp. 67–69.
  5. ↑ Oxley, J. G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, p. 141, ISBN 978-0-19-920250-8.
  6. ↑ 6.0 6.1 Hartsfield, Nora; Ringel, Gerhard (2003), Pearls in Graph Theory: A Comprehensive Introduction, Courier Dover Publications, p. 100, ISBN 978-0-486-43232-8.
  7. ↑ Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, p. 163, ISBN 978-0-521-45761-3.
  8. ↑ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer, p. 350, ISBN 978-0-387-98488-9; Mehlhorn, Kurt (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, p. 260, ISBN 978-0-521-56329-1.
  9. ↑ Gross, Jonathan L.; Yellen, Jay (2005), Graph Theory and Its Applications (2nd ed.), CRC Press, p. 168, ISBN 978-1-58488-505-4; Bondy, J. A.; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 578, ISBN 978-1-84628-970-5.
  10. ↑ Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pp. 141–146.
  11. ↑ Harary, Frank; Hayes, John P.; Wu, Horng-Jyh (1988), "A survey of the theory of hypercube graphs", Computers & Mathematics with Applications, 15 (4): 277–289, doi:10.1016/0898-1221(88)90213-1, hdl:2027.42/27522, MR 0949280.
  12. ↑ Kocay, William; Kreher, Donald L. (2004), "5.8 The matrix-tree theorem", Graphs, Algorithms, and Optimization, Discrete Mathematics and Its Applications, CRC Press, pp. 111–116, ISBN 978-0-203-48905-5.
  13. ↑ Kocay & Kreher (2004), p. 109.
  14. ↑ Bollobás (1998), p. 351.
  15. ↑ Goldberg, L.A.; Jerrum, M. (2008), "Inapproximability of the Tutte polynomial", Information and Computation, 206 (7): 908–929, arXiv:cs/0605140, doi:10.1016/j.ic.2008.04.003; Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), "On the computational complexity of the Jones and Tutte polynomials", Mathematical Proceedings of the Cambridge Philosophical Society, 108: 35–53, doi:10.1017/S0305004100068936.
  16. ↑ Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer, p. 19, ISBN 978-0-387-97687-7.
  17. ↑ de Fraysseix, Hubert; Rosenstiehl, Pierre (1982), "A depth-first-search characterization of planarity", Graph theory (Cambridge, 1981), Ann. Discrete Math., vol. 13, Amsterdam: North-Holland, pp. 75–80, MR 0671906.
  18. ↑ Reif, John H. (1985), "Depth-first search is inherently sequential", Information Processing Letters, 20 (5): 229–234, doi:10.1016/0020-0190(85)90024-9, MR 0801987.
  19. ↑ Gallager, R. G.; Humblet, P. A.; Spira, P. M. (1983), "A distributed algorithm for minimum-weight spanning trees", ACM Transactions on Programming Languages and Systems, 5 (1): 66–77, doi:10.1145/357195.357200; Gazit, Hillel (1991), "An optimal randomized parallel algorithm for finding connected components in a graph", SIAM Journal on Computing, 20 (6): 1046–1067, doi:10.1137/0220066, MR 1135748; Bader, David A.; Cong, Guojing (2005), "A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)" (PDF), Journal of Parallel and Distributed Computing, 65 (9): 994–1006, doi:10.1016/j.jpdc.2005.03.011.
  20. ↑ 20.0 20.1 Eppstein, David (1999), "Spanning trees and spanners" (PDF), in Sack, J.-R.; Urrutia, J. (eds.), Handbook of Computational Geometry, Elsevier, pp. 425–461.
  21. ↑ Wu, Bang Ye; Chao, Kun-Mao (2004), Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3.
  22. ↑ Wilson, David Bruce (1996), "Generating random spanning trees more quickly than the cover time", Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996), pp. 296–303, doi:10.1145/237814.237880, MR 1427525.
  23. ↑ McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997), "On finding a minimum spanning tree in a network with random weights" (PDF), Random Structures & Algorithms, 10 (1–2): 187–204, doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y, MR 1611522.
  24. ↑ Gabow, Harold N.; Myers, Eugene W. (1978), "Finding all spanning trees of directed and undirected graphs", SIAM Journal on Computing, 7 (3): 280–287, doi:10.1137/0207024, MR 0495152
  25. ↑ 25.0 25.1 Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.
  26. ↑ Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of combinatorics, Bolyai Soc. Math. Stud., vol. 17, Berlin: Springer, pp. 189–213, doi:10.1007/978-3-540-77200-2_10, MR 2432534. See in particular Theorem 2.1, pp. 192–193.
  27. ↑ Levine, Lionel (2011). "Sandpile groups and spanning trees of directed line graphs". Journal of Combinatorial Theory, Series A. 118 (2): 350–364. arXiv:0906.2809. doi:10.1016/j.jcta.2010.04.001. ISSN 0097-3165.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्पेनिंग_ट्री&oldid=232974’