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

Latest revision as of 10:10, 2 August 2023

ग्रिड ग्राफ का स्पेनिंग ट्री (नीले भारी किनारे)।

ग्राफ सिद्धांत के गणित क्षेत्र में, अप्रत्यक्ष ग्राफ 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]

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

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

2^{2-2}=1

में ट्री

K_{2}

,

3^{3-2}=3

में ट्री

K_{3}

, और

4^{4-2}=16

में ट्री

K_{4}

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

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

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

यदि G स्वयं ट्री है, तो $t (G) = 1$ है।
जब G, n शीर्षों वाला चक्र ग्राफ C_n है, तो $t (G) = n$ है।
शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र^[10] स्पैनिंग ट्री की संख्या $n n - 2$ इस प्रकार देता है।
यदि G पूर्ण द्विदलीय ग्राफ है $K_{p,q}$ , तब $t(G)=p^{q-1}q^{p-1}$ है।^[6]
एन-आयामी हाइपरक्यूब ग्राफ के लिए $Q_{n}$ ,^[11] स्पैनिंग ट्री की संख्या $t(G)=2^{2^{n}-n-1}\prod _{k=2}^{n}k^{n \choose k}$ है।

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

अधिक सामान्यतः, किसी भी ग्राफ़ 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 भिन्न-भिन्न स्पैनिंग ट्री होते हैं, जिनमें से प्रत्येक में इन किनारों में से ही होता है।

टुटे बहुपद

ग्राफ़ के टुटे बहुपद को ग्राफ़ के स्पैनिंग ट्री पर, ट्री की आंतरिक गतिविधि और बाहरी गतिविधि से गणना की गई नियम के योग के रूप में परिभाषित किया जा सकता है। तर्कों (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 की ओर प्रदर्शित करती हैं।

यह भी देखें

फ्लूडिंग एल्गोरिथ्म
उत्तम स्पैनिंग ट्री - एम्बेडेड प्लेनर ग्राफ के उत्तम स्पैनिंग ट्री

संदर्भ

↑ "पेड़". 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.
↑ Graham, R. L.; Hell, Pavol (1985). "न्यूनतम स्पैनिंग वृक्ष समस्या के इतिहास पर" (PDF).
↑ Kocay & Kreher (2004), pp. 65–67.
↑ Kocay & Kreher (2004), pp. 67–69.
↑ 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.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.
↑ Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, p. 163, ISBN 978-0-521-45761-3.
↑ 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.
↑ 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.
↑ Aigner, Martin; Ziegler, Günter M. (1998), Proofs from THE BOOK, Springer-Verlag, pp. 141–146.
↑ 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.
↑ 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.
↑ Kocay & Kreher (2004), p. 109.
↑ Bollobás (1998), p. 351.
↑ 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.
↑ Kozen, Dexter (1992), The Design and Analysis of Algorithms, Monographs in Computer Science, Springer, p. 19, ISBN 978-0-387-97687-7.
↑ 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.
↑ 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.
↑ 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.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.
↑ Wu, Bang Ye; Chao, Kun-Mao (2004), Spanning Trees and Optimization Problems, CRC Press, ISBN 1-58488-436-3.
↑ 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.
↑ 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.
↑ 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.0 ^25.1 Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.
↑ 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.
↑ 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.

[NetworkX_2.6.2_documentation-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.

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

[sts-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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

@@ Line 11: / Line 11: @@
 इंटरनेट और कई अन्य [[दूरसंचार नेटवर्क]] में ट्रांसमिशन लिंक होते हैं जो नोड्स को [[जाल टोपोलॉजी|मेश टोपोलॉजी]] में साथ जोड़ते हैं जिसमें कुछ लूप सम्मिलित होते हैं। [[ब्रिज लूप]] और [[रूटिंग लूप]] से बचने के लिए, ऐसे नेटवर्क के लिए डिज़ाइन किए गए कई रूटिंग प्रोटोकॉल - जिनमें [[ स्पेनिंग ट्री प्रोटोकॉल |स्पेनिंग ट्री प्रोटोकॉल]], [[पहले सबसे छोटा रास्ता खोलो|विवृत शॉर्टेस्ट पाथ फर्स्ट]], [[लिंक-स्टेट रूटिंग प्रोटोकॉल]], [[संवर्धित वृक्ष-आधारित रूटिंग|ऑगमेंटेड ट्री-आधारित रूटिंग]] आदि सम्मिलित हैं- प्रत्येक राउटर को याद रखने की आवश्यकता होती है।
-अधिकतम [[जीनस (गणित)]] के साथ [[ग्राफ एम्बेडिंग]] शोध के लिए [[टोपोलॉजिकल ग्राफ सिद्धांत]] में विशेष प्रकार के स्पैनिंग ट्री, ज़ुओंग ट्री का उपयोग किया जाता है। ज़ुओंग ट्री स्पैनिंग ट्री है, जैसे कि, शेष ग्राफ़ में, विषम संख्या में किनारों के साथ जुड़े घटकों की संख्या यथासंभव छोटी होती है। ज़ुओंग ट्री और संबद्ध अधिकतम-जीनस एम्बेडिंग बहुपद समय में पाया जा सकता है।रेफरी>{{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}}<nowiki></ref></nowiki> <रेफ नाम= 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}}<nowiki></ref></nowiki>
 ==परिभाषाएँ==
@@ Line 34: / Line 23: @@
 मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए स्पैनिंग ट्री के संबंध में मौलिक कटसेट्स की धारणा भी दोहरी है। स्पैनिंग ट्री के केवल किनारे को विस्थापित करके, शीर्षों को दो असंयुक्त समुच्चयों में विभाजित किया गया है। मौलिक कटसेट्स को किनारों के समुच्चय के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूर्ण करने के लिए ग्राफ़ ''G'' से विस्थापित किया जाना चाहिए। इस प्रकार, प्रत्येक स्पैनिंग ट्री ''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>
 '''स्पैनिंग फारेस्ट'''
@@ Line 261: / Line 250: @@
 {{Authority control}}
-[[Category: फैला हुआ पेड़| फैला हुआ पेड़]] [[Category: पसंद का सिद्धांत]] [[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category: Machine Translated Page]]
 [[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:फैला हुआ पेड़| फैला हुआ पेड़]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 10:10, 2 August 2023

Contents

अनुप्रयोग