स्पेनिंग ट्री

From Vigyanwiki
Revision as of 03:59, 9 July 2023 by alpha>Indicwiki (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|[...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
For the network protocol, see Spanning Tree Protocol. For other uses, see स्पेनिंग ट्री (disambiguation).
ग्रिड ग्राफ़ का एक फैला हुआ पेड़ (नीले भारी किनारे)।

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

अनुप्रयोग

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

बिजली नेटवर्क, वायरिंग कनेक्शन, पाइपिंग, स्वचालित वाक् पहचान आदि की लागत को कम करने के लिए, लोग अक्सर एल्गोरिदम का उपयोग करते हैं जो न्यूनतम फैलाव वाला पेड़ खोजने की प्रक्रिया में मध्यवर्ती चरणों के रूप में धीरे-धीरे एक स्पैनिंग ट्री (या ऐसे कई पेड़) बनाते हैं। .[2] इंटरनेट और कई अन्य दूरसंचार नेटवर्क में ट्रांसमिशन लिंक होते हैं जो नोड्स को एक जाल टोपोलॉजी में एक साथ जोड़ते हैं जिसमें कुछ लूप शामिल होते हैं। ब्रिज लूप और रूटिंग लूप से बचने के लिए, ऐसे नेटवर्क के लिए डिज़ाइन किए गए कई रूटिंग प्रोटोकॉल - जिनमें स्पेनिंग ट्री प्रोटोकॉल , पहले सबसे छोटा रास्ता खोलो, लिंक-स्टेट रूटिंग प्रोटोकॉल, संवर्धित वृक्ष-आधारित रूटिंग आदि शामिल हैं - प्रत्येक राउटर को याद रखने की आवश्यकता होती है। फैला हुआ पेड़।<रेफ नाम= https://en.wikipedia.org/w/index.php?title=Spanning_tree&action=edit# >Borg, Anita. "नेटवर्क प्रोटोकॉल डिज़ाइन की लोककथाएँ". YouTube. Microsoft Research. Retrieved 13 May 2022.</ref>

अधिकतम जीनस (गणित) के साथ ग्राफ एम्बेडिंग खोजने के लिए टोपोलॉजिकल ग्राफ सिद्धांत में एक विशेष प्रकार के फैले हुए पेड़, ज़ुओंग पेड़ का उपयोग किया जाता है। ज़ुओंग पेड़ एक फैला हुआ पेड़ है, जैसे कि, शेष ग्राफ़ में, विषम संख्या में किनारों के साथ जुड़े घटकों की संख्या यथासंभव छोटी होती है। एक ज़ुओंग पेड़ और एक संबद्ध अधिकतम-जीनस एम्बेडिंग बहुपद समय में पाया जा सकता है। रेफरी>Beineke, Lowell W.; Wilson, Robin J. (2009), Topics in topological graph theory, Encyclopedia of Mathematics and its Applications, vol. 128, Cambridge University Press, Cambridge, p. 36, doi:10.1017/CBO9781139087223, ISBN 978-0-521-80230-7, MR 2581536</ref>

परिभाषाएँ

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

मौलिक चक्र

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


मौलिक कटसेट

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


विस्तारित वन

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

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

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


फैले हुए पेड़ों की गिनती

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

किसी कनेक्टेड ग्राफ़ के फैले हुए पेड़ों की संख्या t(G) एक अच्छी तरह से अध्ययन किया गया अपरिवर्तनीय (गणित) है।

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

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

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

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

Main article: Kirchhoff's theorem

अधिक सामान्यतः, किसी भी ग्राफ़ 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: Tutte polynomial

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


एल्गोरिदम

निर्माण

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


अनुकूलन

ग्राफ़ सिद्धांत के कुछ क्षेत्रों में भारित ग्राफ़ का न्यूनतम फैले हुए पेड़ को ढूंढना अक्सर उपयोगी होता है। स्पैनिंग पेड़ों पर अन्य अनुकूलन समस्याओं का भी अध्ययन किया गया है, जिसमें अधिकतम स्पैनिंग वृक्ष, न्यूनतम वृक्ष जो कम से कम k शिखर तक फैला है, न्यूनतम डिग्री स्पैनिंग वृक्ष, अधिकतम पत्ती फैलाने वाला वृक्ष, सबसे कम पत्तियों वाला स्पैनिंग वृक्ष (निकटता से संबंधित) शामिल हैं। हैमिल्टनियन पथ समस्या), न्यूनतम व्यास फैला हुआ पेड़, और न्यूनतम फैलाव फैला हुआ पेड़।[20][21] यूक्लिडियन विमान जैसे ज्यामितीय स्थान में बिंदुओं के परिमित सेट के लिए इष्टतम फैले हुए पेड़ की समस्याओं का भी अध्ययन किया गया है। ऐसे इनपुट के लिए, एक फैला हुआ पेड़ फिर से एक पेड़ होता है जिसके शीर्ष पर दिए गए बिंदु होते हैं। पेड़ की गुणवत्ता को ग्राफ़ की तरह ही मापा जाता है, प्रत्येक किनारे के वजन के रूप में बिंदुओं के जोड़े के बीच यूक्लिडियन दूरी का उपयोग किया जाता है। इस प्रकार, उदाहरण के लिए, एक यूक्लिडियन न्यूनतम फैलाव वाला पेड़, यूक्लिडियन एज वेट के साथ एक पूर्ण ग्राफ में ग्राफ न्यूनतम स्पैनिंग ट्री के समान है। हालाँकि, अनुकूलन समस्या को हल करने के लिए इस ग्राफ़ का निर्माण करना आवश्यक नहीं है; उदाहरण के लिए, यूक्लिडियन न्यूनतम स्पैनिंग ट्री समस्या को डेलाउने त्रिकोणासन का निर्माण करके और फिर परिणामी ट्राइएंग्यूलेशन पर एक रैखिक समय समतलीय ग्राफ न्यूनतम स्पैनिंग ट्री एल्गोरिदम लागू करके ओ (एन लॉग एन) समय में अधिक कुशलता से हल किया जा सकता है।[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=223626’