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

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 4 users not shown)
Line 2: Line 2:
{{About||नेटवर्क प्रोटोकॉल|स्पेनिंग ट्री प्रोटोकॉल|अन्य उपयोग|}}
{{About||नेटवर्क प्रोटोकॉल|स्पेनिंग ट्री प्रोटोकॉल|अन्य उपयोग|}}


[[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 के समान है (अर्थात, ट्री में अद्वितीय स्पेनिंग ट्री होता है और वह स्वयं होता है)।
[[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 के समान है (अर्थात, ट्री में अद्वितीय स्पेनिंग ट्री होता है और वह स्वयं होता है)।


==अनुप्रयोग==
==अनुप्रयोग==
Line 12: Line 12:


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


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


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


'''मौलिक कटसेट्स'''
'''मौलिक कटसेट्स'''
Line 35: Line 23:
मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए स्पैनिंग ट्री के संबंध में मौलिक कटसेट्स की धारणा भी दोहरी है। स्पैनिंग ट्री के केवल किनारे को विस्थापित करके, शीर्षों को दो असंयुक्त समुच्चयों में विभाजित किया गया है। मौलिक कटसेट्स को किनारों के समुच्चय के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूर्ण करने के लिए ग्राफ़ ''G'' से विस्थापित किया जाना चाहिए। इस प्रकार, प्रत्येक स्पैनिंग ट्री ''V'' के समुच्चय को परिभाषित करता है- 1 मौलिक कटसेट्स, स्पैनिंग ट्री के प्रत्येक किनारे के लिए है।<ref>{{harvtxt|Kocay|Kreher|2004}}, pp.&nbsp;67–69.</ref>
मौलिक चक्र की धारणा के साथ-साथ किसी दिए गए स्पैनिंग ट्री के संबंध में मौलिक कटसेट्स की धारणा भी दोहरी है। स्पैनिंग ट्री के केवल किनारे को विस्थापित करके, शीर्षों को दो असंयुक्त समुच्चयों में विभाजित किया गया है। मौलिक कटसेट्स को किनारों के समुच्चय के रूप में परिभाषित किया गया है जिसे समान विभाजन को पूर्ण करने के लिए ग्राफ़ ''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>


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


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


* लगभग सभी ग्राफ़ सिद्धांत पुस्तकें और लेख स्पैनिंग फारेस्ट को ऐसे फारेस्ट के रूप में परिभाषित करते हैं जो सभी शीर्षों तक स्पैनिंग है, जिसका अर्थ केवल यह है कि ग्राफ़ का प्रत्येक शीर्ष फारेस्ट में शीर्ष है। कनेक्टेड ग्राफ़ में भिन्न स्पैनिंग फारेस्ट हो सकता है, जैसे कि बिना किनारों वाला फारेस्ट, जिसमें प्रत्येक शीर्ष एकल-शीर्ष ट्री बनाता है।<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
Line 47: Line 35:


== स्पैनिंग ट्री की गिनती ==
== स्पैनिंग ट्री की गिनती ==
[[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, n शीर्षों वाला [[चक्र ग्राफ]] C<sub>n</sub> है, तो {{math|1=''t''(''G'')&nbsp;=&nbsp;''n''}} है।
* जब G, n शीर्षों वाला [[चक्र ग्राफ]] C<sub>n</sub> है, तो {{math|1=''t''(''G'')&nbsp;=&nbsp;''n''}} है।
* शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र<ref>{{citation
* शीर्षों के साथ पूर्ण ग्राफ़ के लिए, केली का सूत्र<ref>{{citation
  | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
  | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
Line 79: Line 65:


=== आरबिटरेरी ग्राफ़ में ===
=== आरबिटरेरी ग्राफ़ में ===
{{main|Kirchhoff's theorem}}
{{main|किरचॉफ का प्रमेय}}


अधिक सामान्यतः, किसी भी ग्राफ़ G के लिए, संख्या t(G) की गणना किरचॉफ के [[मैट्रिक्स (गणित)|आव्यूह]]-ट्री प्रमेय का उपयोग करके, ग्राफ से प्राप्त मैट्रिक्स के निर्धारक के रूप में बहुपद समय में की जा सकती है।
अधिक सामान्यतः, किसी भी ग्राफ़ 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>विशेष रूप से, t(G) की गणना करने के लिए, ग्राफ़ के [[लाप्लासियन मैट्रिक्स|लाप्लासियन]] आव्यूह का निर्माण किया जाता है, वर्ग आव्यूह जिसमें पंक्तियाँ और स्तंभ दोनों G के शीर्षों द्वारा अनुक्रमित होते हैं। पंक्ति i और स्तंभ j में प्रविष्टि तीन मानों में से है:
Line 90: Line 76:


===विलोपन-संकुचन===
===विलोपन-संकुचन===
यदि 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 का उपयोग करते हैं।
यदि 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 का उपयोग करते हैं।


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


टुटे बहुपद की गणना विलोपन-संकुचन पुनरावृत्ति का उपयोग करके भी की जा सकती है, किन्तु इसका [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समिष्टता सिद्धांत]] उच्च है: इसके तर्कों के कई मानों के लिए, इसकी त्रुटिहीन गणना -P-पूर्ण है, और यह भी कठिन है। बिंदु (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 125: Line 111:


===निर्माण===
===निर्माण===
ग्राफ़ का ल फैला हुआ ट्री [[रैखिक समय]] में या तो [[गहराई-पहली खोज|गहराई-पसमाधानी खोज]] या चौड़ाई-पसमाधानी खोज द्वारा पाया जा सकता है। ये दोनों एल्गोरिदम दिए गए ग्राफ़ का पता लगाते हैं, मनमाना शीर्ष 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 137: 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 146: 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 166:
'''अनुकूलन'''
'''अनुकूलन'''


ग्राफ़ सिद्धांत के कुछ क्षेत्रों में [[भारित ग्राफ]]़ का न्यूनतम फैले हुए ट्री को ढूंढना प्रायः उपयोगी होता है। स्पैनिंग ट्रीों पर अन्य अनुकूलन समस्याओं का भी अध्ययन किया गया है, जिसमें अधिकतम स्पैनिंग ट्री, न्यूनतम ट्री जो कम से कम 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 193: 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 198:
'''गणना'''
'''गणना'''


क्योंकि ग्राफ़ में तेजी से फैले हुए कई ट्री हो सकते हैं, उन सभी को बहुपद समय में सूचीबद्ध करना संभव नहीं है। चूँकि, एल्गोरिदम सभी फैले हुए ट्रीों को प्रति ट्री बहुपद समय में सूचीबद्ध करने के लिए जाने जाते हैं।<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 222: Line 211:


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


== निर्देशित मल्टीग्राफ में ==
== निर्देशित मल्टीग्राफ में ==
फैले हुए ट्री के विचार को निर्देशित मल्टीग्राफ के लिए सामान्यीकृत किया जा सकता है।<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 251: 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 261: 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’