न्यूनतम स्पैनिंग ट्री (एमएसटी): Difference between revisions
No edit summary |
No edit summary |
||
(5 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Least-weight tree connecting graph vertices}} | {{Short description|Least-weight tree connecting graph vertices}} | ||
[[File:Minimum spanning tree.svg|thumb|300px|right|एक [[समतलीय ग्राफ]] और उसका न्यूनतम स्पैनिंग ट्री। प्रत्येक किनारे को उसके वजन के साथ लेबल किया गया है, जो यहां लगभग उसकी लंबाई के समानुपाती है।]]'''न्यूनतम स्पैनिंग ट्री (एमएसटी)''' या '''न्यूनतम वेट स्पैनिंग ट्री''' [[ जुड़ा हुआ ग्राफ | संयोजित ग्राफ]] के किनारों का उपसमूह है, किनारे-भारित अप्रत्यक्ष ग्राफ जो बिना किसी [[चक्र (ग्राफ सिद्धांत)]] के सभी वर्टेक्स (ग्राफ सिद्धांत) को साथ जोड़ता है। <ref>{{cite web | title=scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 मैनुअल| website=Numpy and Scipy Documentation — Numpy and Scipy documentation | url=https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html | access-date=2021-12-10 | quote=न्यूनतम स्पैनिंग ट्री एक ग्राफ है जिसमें किनारों का सबसेट होता है जो किनारों पर वजन के कुल योग को कम करते हुए सभी जुड़े हुए नोड्स को एक साथ जोड़ता है।}}</ref> अर्थात, यह फैला हुआ ट्री है जिसके किनारे के भार का योग यथासंभव छोटा है। <ref>{{cite web | title=नेटवर्कx.algorithms.tree.mst.minimum_spanning_edges| website=NetworkX 2.6.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_edges.html | access-date=2021-12-13 | quote=एक न्यूनतम स्पैनिंग ट्री ग्राफ़ का एक सबग्राफ (एक ट्री) है जिसमें किनारे के भार का न्यूनतम योग होता है। एक फैला हुआ जंगल ग्राफ़ के प्रत्येक जुड़े घटक के लिए फैले हुए पेड़ों का एक संघ है।}}</ref> अधिक सामान्यतः, किसी भी किनारे-भारित अप्रत्यक्ष ग्राफ (आवश्यक रूप से जुड़ा नहीं) में न्यूनतम | [[File:Minimum spanning tree.svg|thumb|300px|right|एक [[समतलीय ग्राफ]] और उसका न्यूनतम स्पैनिंग ट्री। प्रत्येक किनारे को उसके वजन के साथ लेबल किया गया है, जो यहां लगभग उसकी लंबाई के समानुपाती है।]]'''न्यूनतम स्पैनिंग ट्री (एमएसटी)''' या '''न्यूनतम वेट स्पैनिंग ट्री''' [[ जुड़ा हुआ ग्राफ | संयोजित ग्राफ]] के किनारों का उपसमूह है, किनारे-भारित अप्रत्यक्ष ग्राफ जो बिना किसी [[चक्र (ग्राफ सिद्धांत)]] के सभी वर्टेक्स (ग्राफ सिद्धांत) को साथ जोड़ता है। <ref>{{cite web | title=scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 मैनुअल| website=Numpy and Scipy Documentation — Numpy and Scipy documentation | url=https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html | access-date=2021-12-10 | quote=न्यूनतम स्पैनिंग ट्री एक ग्राफ है जिसमें किनारों का सबसेट होता है जो किनारों पर वजन के कुल योग को कम करते हुए सभी जुड़े हुए नोड्स को एक साथ जोड़ता है।}}</ref> अर्थात, यह फैला हुआ ट्री है जिसके किनारे के भार का योग यथासंभव छोटा है। <ref>{{cite web | title=नेटवर्कx.algorithms.tree.mst.minimum_spanning_edges| website=NetworkX 2.6.2 documentation | url=https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tree.mst.minimum_spanning_edges.html | access-date=2021-12-13 | quote=एक न्यूनतम स्पैनिंग ट्री ग्राफ़ का एक सबग्राफ (एक ट्री) है जिसमें किनारे के भार का न्यूनतम योग होता है। एक फैला हुआ जंगल ग्राफ़ के प्रत्येक जुड़े घटक के लिए फैले हुए पेड़ों का एक संघ है।}}</ref> अधिक सामान्यतः, किसी भी किनारे-भारित अप्रत्यक्ष ग्राफ (आवश्यक रूप से जुड़ा नहीं) में न्यूनतम स्पैनिंग जंगल होते हैं, जो इसके जुड़े घटक (ग्राफ सिद्धांत) के लिए न्यूनतम स्पैनिंग ट्री का संघ है। | ||
न्यूनतम स्पैनिंग ट्री के लिए कई उपयोग के स्थिति हैं। उदाहरण दूरसंचार कंपनी है जो नए पड़ोस में केबल बिछाने की प्रयास कर रही है। यदि केबल को केवल कुछ निश्चित रास्तों (जैसे सड़कों) के किनारे गाड़ने के लिए बाध्य किया जाता है, जिससे उन रास्तों से जुड़े बिंदुओं (जैसे घरों) को सम्मिलित करने वाला ग्राफ होता है। कुछ रास्ते अधिक महंगे हो सकते हैं, क्योंकि वे लंबे हैं, या केबल को अधिक गहराई तक गाड़ने की आवश्यकता होती है; इन पथों को बड़े भार वाले किनारों द्वारा दर्शाया जाता है। मुद्रा किनारे के वजन के लिए स्वीकार्य इकाई है त्रिकोण असमानता जैसे ज्यामिति के सामान्य नियमों का पालन करने के लिए किनारे की लंबाई की कोई आवश्यकता नहीं है। उस ग्राफ़ के लिए '' | न्यूनतम स्पैनिंग ट्री के लिए कई उपयोग के स्थिति हैं। उदाहरण दूरसंचार कंपनी है जो नए पड़ोस में केबल बिछाने की प्रयास कर रही है। यदि केबल को केवल कुछ निश्चित रास्तों (जैसे सड़कों) के किनारे गाड़ने के लिए बाध्य किया जाता है, जिससे उन रास्तों से जुड़े बिंदुओं (जैसे घरों) को सम्मिलित करने वाला ग्राफ होता है। कुछ रास्ते अधिक महंगे हो सकते हैं, क्योंकि वे लंबे हैं, या केबल को अधिक गहराई तक गाड़ने की आवश्यकता होती है; इन पथों को बड़े भार वाले किनारों द्वारा दर्शाया जाता है। मुद्रा किनारे के वजन के लिए स्वीकार्य इकाई है त्रिकोण असमानता जैसे ज्यामिति के सामान्य नियमों का पालन करने के लिए किनारे की लंबाई की कोई आवश्यकता नहीं है। उस ग्राफ़ के लिए ''स्पैनिंग ट्री'' उन रास्तों का उपसमूह होगा जिनमें कोई चक्र नहीं है किन्तु फिर भी वे हर घर को जोड़ते हैं; वहाँ अनेक स्पैनिंग ट्री संभव हो सकते हैं। ''न्यूनतम स्पैनिंग ट्री'' सबसे कम कुल निवेश वाला होगा, जो केबल बिछाने के लिए सबसे कम खर्चीले पथ का प्रतिनिधित्व करता है। | ||
==गुण== | ''', जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के''' | ||
==गुण == | |||
===संभावित बहुलता=== | ===संभावित बहुलता=== | ||
यदि | यदि ग्राफ़ में {{mvar|n}} शीर्ष हैं तो प्रत्येक स्पैनिंग ट्री में {{math|''n'' − 1}} किनारे हैं। | ||
[[File:Multiple minimum spanning trees.svg|thumb|यह आंकड़ा दर्शाता है कि ग्राफ़ में से अधिक न्यूनतम | [[File:Multiple minimum spanning trees.svg|thumb|यह आंकड़ा दर्शाता है कि ग्राफ़ में से अधिक न्यूनतम स्पैनिंग ट्री हो सकते हैं। चित्र में, ग्राफ़ के नीचे के दो ट्री दिए गए ग्राफ़ के न्यूनतम स्पैनिंग ट्री की दो संभावनाएँ हैं।]]एक ही वजन के कई न्यूनतम स्पैनिंग ट्री हो सकते हैं; विशेष रूप से, यदि किसी दिए गए ग्राफ़ के सभी किनारों का भार समान है, जिससे उस ग्राफ़ का प्रत्येक फैला हुआ ट्री न्यूनतम है। | ||
===अद्वितीयता=== | ===अद्वितीयता=== | ||
यदि प्रत्येक किनारे का अलग वजन है | यदि प्रत्येक किनारे का अलग वजन है जिससे केवल एक, अद्वितीय न्यूनतम स्पैनिंग ट्री होता है। यह कई यथार्थवादी स्थितियों में सही है, जैसे कि ऊपर दूरसंचार कंपनी का उदाहरण, जहां यह संभव नहीं है कि किन्हीं दो रास्तों की निवेश पूर्ण रूप से समान होता है। यह विस्तृत वनों का भी सामान्यीकरण करता है। | ||
प्रमाण: | |||
#विरोधाभास से प्रमाण, कि दो | #विरोधाभास से प्रमाण, कि दो {{mvar|A}} और {{mvar|B}} अलग-अलग एमएसटी हैं. | ||
# | #चूंकि {{mvar|A}} और {{mvar|B}} समान नोड्स होने के अतिरिक्त भिन्न हैं, इसलिए कम से कम एक किनारा ऐसा है जो एक का है किन्तु दूसरे का नहीं। ऐसे किनारों के बीच मान लीजिए कि {{math|''e''{{sub|1}}}} सबसे कम वजन वाला है, यह विकल्प अद्वितीय है क्योंकि सभी किनारों का वजन अलग-अलग है। व्यापकता की हानि के बिना मान लें कि {{math|''e''{{sub|1}}}}, {{mvar|A}} में है। | ||
# | #चूँकि {{mvar|B}} एक एमएसटी है {{math|{''e''{{sub|1}}} ∪ ''B''}} में {{math|''e''{{sub|1}}}} के साथ एक चक्र {{mvar|C}} होना चाहिए। | ||
#चूंकि ट्री A में कोई चक्र नहीं है इसलिए {{mvar|C}} का एक किनारा {{math|''e''{{sub|2}}}} होना चाहिए जो {{mvar|A}} में नहीं है। | |||
# | #चूँकि {{math|''e''{{sub|1}}}} को {{mvar|A}} और {{mvar|B}} में से किसी एक से संबंधित अद्वितीय सबसे कम वजन वाले किनारे के रूप में चुना गया था, इसलिए {{math|''e''{{sub|2}}}} का वजन {{math|''e''{{sub|1}}}} के वजन से अधिक होना चाहिए। | ||
# | #चूँकि {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} चक्र {{mvar|C}} का भाग हैं, इसलिए {{mvar|B}} में {{math|''e''{{sub|2}}}} को {{math|''e''{{sub|1}}}} से बदलने पर कम वजन वाला एक स्पैनिंग ट्री प्राप्त होता है। | ||
# यह इस धारणा का खंडन करता है कि {{mvar|B}} एमएसटी है. | # यह इस धारणा का खंडन करता है कि {{mvar|B}} एमएसटी है. | ||
अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं | अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं जिससे न्यूनतम स्पैनिंग ट्री में वजन का केवल बहु सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम स्पैनिंग ट्री के लिए समान है।<ref>{{cite web|url=https://cs.stackexchange.com/q/2204 |title=Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?|website=cs.stackexchange.com|access-date=4 April 2018}}</ref> | ||
===न्यूनतम-निवेश उपग्राफ=== | ===न्यूनतम-निवेश उपग्राफ=== | ||
यदि भार सकारात्मक हैं, | यदि भार सकारात्मक हैं, जिससे न्यूनतम स्पैनिंग ट्री, वास्तव में, ग्राफ सिद्धांत की न्यूनतम-निवेश शब्दावली है सभी शीर्षों को जोड़ने वाले सबग्राफ, क्योंकि यदि सबग्राफ में [[पथ (ग्राफ सिद्धांत)]] होता है, तो उस चक्र के साथ किसी भी किनारे को हटाने से कमी आएगी इसकी निवेश और कनेक्टिविटी को सुरक्षित रखें। | ||
===साइकिल | ===साइकिल प्रोपर्टी=== | ||
किसी भी चक्र के लिए {{mvar|C}} | ग्राफ़ में किसी भी चक्र {{mvar|C}} के लिए यदि {{mvar|C}} के किनारे {{mvar|e}} का वजन {{mvar|C}} के अन्य सभी किनारों के किसी भी व्यक्तिगत वजन से बड़ा है तो यह किनारा एमएसटी से संबंधित नहीं हो सकता है। | ||
प्रमाण: | प्रमाण: इसके विपरीत मान लें कि {{mvar|e}} एक एमएसटी {{math|''T''{{sub|1}}}} से संबंधित है। फिर {{mvar|e}} को हटाने से {{math|''T''{{sub|1}}}} दो सबट्री में टूट जाएगा और {{mvar|e}} के दोनों सिरे अलग-अलग सबट्री में होंगे। {{mvar|C}} का शेष भाग सबट्री को फिर से जोड़ता है इसलिए C का एक किनारा {{mvar|f}} होता है जिसके सिरे अलग-अलग सबट्री में होते हैं अर्थात यह सबट्री को {{math|''T''{{sub|1}}}} के भार से कम भार वाले {{math|''T''{{sub|2}}}} वृक्ष में पुनः जोड़ता है क्योंकि f का भार {{mvar|e}} के भार से कम है। | ||
=== | ===प्रोपर्टी कट=== | ||
[[File:Msp-the-cut-correct.svg|thumb|400px|यह आंकड़ा एमएसटी की कटी हुई | [[File:Msp-the-cut-correct.svg|thumb|400px|यह आंकड़ा एमएसटी की कटी हुई प्रोपर्टी को दर्शाता है। {{mvar|T}} दिए गए ग्राफ़ का एकमात्र एमएसटी है। यदि {{math|1=''S'' = {''A'',''B'',''D'',''E''},}} इस प्रकार {{math|1=''V'' – ''S'' = {''C'',''F''},}} तो कट के पार किनारे की 3 संभावनाएँ हैं {{math|(''S'', ''V'' – ''S'')}}, वे किनारे हैं {{mvar|BC}}, {{mvar|EC}}, {{mvar|EF}} मूल ग्राफ़ का। फिर, ई कट के लिए न्यूनतम-वजन-किनारे में से है {{math|''S'' ∪ {''e''} }} एमएसटी का भाग है {{mvar|T}}.]]किसी भी कट के लिए (ग्राफ सिद्धांत) {{mvar|C}} ग्राफ़ का, यदि किनारे का भार {{mvar|e}} के कट-सेट में {{mvar|C}} कट-सेट के अन्य सभी किनारों के वजन से पूर्ण रूप से छोटा है {{mvar|C}}, तो यह किनारा ग्राफ़ के सभी एमएसटी से संबंधित है। | ||
प्रमाण: यह कहना | प्रमाण: यह कहना व्यर्थ है कि एमएसटी {{mvar|T}} है जिसमें सम्मिलित {{mvar|e}} नहीं है . जोड़ा जा रहा है {{mvar|e}} को {{mvar|T}} चक्र का उत्पादन करेगा, जो एक ही बार में कट को पार कर जाएगा {{mvar|e}} और दूसरे किनारे पर वापस चला जाता है {{mvar|e'}}. हटाया जा रहा है {{mvar|e'}} हमें फैला हुआ ट्री मिलता है {{math|''T''∖{''e' ''} ∪ {''e''} }} की तुलना में सख्ती से कम वजन का {{mvar|T}}. यह इस धारणा का खंडन करता है कि {{mvar|T}} एमएसटी था. | ||
इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम | इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम स्पैनिंग ट्री में समाहित होता है। | ||
===न्यूनतम-निवेश बढ़त=== | ===न्यूनतम-निवेश बढ़त=== | ||
यदि न्यूनतम निवेश बढ़त e किसी ग्राफ़ का अद्वितीय है, जिससे यह किनारा किसी भी एमएसटी में सम्मिलित है। | |||
प्रमाण: यदि {{mvar|e}} को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त | प्रमाण: यदि {{mvar|e}} को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होता है। | ||
===संकुचन=== | ===संकुचन=== | ||
यदि {{mvar|T}} एमएसटी किनारों का ट्री है, तो हम अनुबंध कर सकते हैं {{mvar|T}} अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर {{mvar|T}} संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।<ref name=PettieRamachandran2002/> | यदि {{mvar|T}} एमएसटी किनारों का ट्री है, तो हम अनुबंध कर सकते हैं {{mvar|T}} अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर {{mvar|T}} संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।<ref name=PettieRamachandran2002/> | ||
==एल्गोरिदम == | |||
==एल्गोरिदम== | |||
नीचे दिए गए सभी एल्गोरिदम में, {{mvar|m}} ग्राफ़ में किनारों की संख्या है और {{mvar|n}} शीर्षों की संख्या है. | नीचे दिए गए सभी एल्गोरिदम में, {{mvar|m}} ग्राफ़ में किनारों की संख्या है और {{mvar|n}} शीर्षों की संख्या है. | ||
=== क्लासिक एल्गोरिदम === | === क्लासिक एल्गोरिदम === | ||
न्यूनतम | न्यूनतम स्पैनिंग ट्री को खोजने के लिए पहला एल्गोरिदम 1926 में चेक वैज्ञानिक ओटाकर बोरोव्का द्वारा विकसित किया गया था (बोरोव्का का एल्गोरिदम देखें)। इसका उद्देश्य [[मोराविया]] का कुशल विद्युत कवरेज था। एल्गोरिदम चरणों के अनुक्रम में आगे बढ़ता है। प्रत्येक चरण में, जिसे बोरुव्का चरण कहा जाता है, यह जंगल की पहचान करता है {{mvar|F}} ग्राफ़ में प्रत्येक शीर्ष पर न्यूनतम-वजन वाली बढ़त की घटना सम्मिलित है {{mvar|G}}, फिर ग्राफ बनाता है {{math|1=''G''{{sub|1}} = ''G'' \ ''F''}} अगले चरण के इनपुट के रूप में। यहाँ {{math|''G'' \ ''F''}} से प्राप्त ग्राफ़ को दर्शाता है {{mvar|G}} किनारों को अंदर की ओर सिकोड़कर {{mvar|F}} (कट प्रोपर्टी के अनुसार, ये किनारे एमएसटी से संबंधित हैं)। प्रत्येक बोरुव्का चरण में रैखिक समय लगता है। चूँकि प्रत्येक चरण में शीर्षों की संख्या कम से कम आधी हो जाती है, बोरुव्का का एल्गोरिथ्म {{math|''O''(''m'' log ''n'')}} समय लेता है।<ref name=PettieRamachandran2002/> | ||
दूसरा एल्गोरिथम प्राइम का एल्गोरिथम है, जिसका आविष्कार 1930 में वोजटेक जार्निक द्वारा किया गया था और 1957 में रॉबर्ट सी. प्राइम और 1959 में एडस्गर डब्ल्यू. डिज्क्स्ट्रा द्वारा फिर से खोजा गया था। मूल रूप से, यह एमएसटी को बढ़ाता है ({{mvar|T}}) समय में | दूसरा एल्गोरिथम प्राइम का एल्गोरिथम है, जिसका आविष्कार 1930 में वोजटेक जार्निक द्वारा किया गया था और 1957 में रॉबर्ट सी. प्राइम और 1959 में एडस्गर डब्ल्यू. डिज्क्स्ट्रा द्वारा फिर से खोजा गया था। मूल रूप से, यह एमएसटी को बढ़ाता है ({{mvar|T}}) समय में किनारा प्रारंभ में, {{mvar|T}} में सही शीर्ष सम्मिलित है। प्रत्येक चरण में, {{mvar|T}} को कम से कम वजन वाले किनारे के साथ संवर्धित किया गया है {{math|(''x'',''y'')}} ऐसा है कि {{mvar|x}} में है {{mvar|T}} और {{mvar|y}} अभी तक अंदर नहीं है {{mvar|T}}. कट प्रॉपर्टी द्वारा, सभी किनारों को जोड़ा गया {{mvar|T}} एमएसटी में हैं। इसका रन-टाइम या तो है {{math|''O''(''m'' log ''n'')}} या {{math|''O''(''m'' + ''n'' log ''n'')}}, प्रयुक्त डेटा-संरचनाओं पर निर्भर करता है। | ||
सामान्यतः उपयोग में आने वाला तीसरा एल्गोरिदम क्रुस्कल का एल्गोरिदम है, जो {{math|''O''(''m'' log ''n'')}} समय भी लेता है । | |||
एक चौथा एल्गोरिदम, जो | एक चौथा एल्गोरिदम, जो सामान्यतः उपयोग नहीं किया जाता है, [[रिवर्स-डिलीट एल्गोरिदम]] है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है {{math|O(''m'' log ''n'' (log log ''n''){{sup|3}})}}. | ||
ये चारों [[लालची एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में | ये चारों [[लालची एल्गोरिदम|ग्रीडी एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं। | ||
=== तेज़ एल्गोरिदम === | === तेज़ एल्गोरिदम === | ||
कई शोधकर्ताओं ने अधिक कम्प्यूटेशनल रूप से कुशल एल्गोरिदम खोजने का प्रयास किया है। | कई शोधकर्ताओं ने अधिक कम्प्यूटेशनल रूप से कुशल एल्गोरिदम खोजने का प्रयास किया है। | ||
एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, {{harvtxt| | एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, {{harvtxt|कर्गेर|कलें|टार्जन|1995}} बोरोव्का के एल्गोरिदम और रिवर्स-डिलीट एल्गोरिदम के संयोजन के आधार पर [[अपेक्षित रैखिक समय एमएसटी एल्गोरिदम]] मिला था।<ref>{{citation | ||
| last1 = Karger | first1 = David R. | author1-link = David Karger | | last1 = Karger | first1 = David R. | author1-link = David Karger | ||
| last2 = Klein | first2 = Philip N. | | last2 = Klein | first2 = Philip N. | ||
Line 91: | Line 89: | ||
| year = 2002| isbn = 9780898715132 | | year = 2002| isbn = 9780898715132 | ||
}}.</ref> | }}.</ref> | ||
ज्ञात जटिलता के साथ सबसे तेज़ गैर-यादृच्छिक तुलना-आधारित एल्गोरिदम, [[बर्नार्ड चेज़ेल]] द्वारा, [[ मुलायम ढेर ]], अनुमानित प्राथमिकता कतार पर आधारित है।<ref name=Chazelle2000>{{citation | |||
ज्ञात जटिलता के साथ सबसे तेज़ गैर-यादृच्छिक तुलना-आधारित एल्गोरिदम, [[बर्नार्ड चेज़ेल]] द्वारा, [[ मुलायम ढेर | सॉफ्ट हीप]] , अनुमानित प्राथमिकता कतार पर आधारित है।<ref name="Chazelle2000">{{citation | |||
| last = Chazelle | first = Bernard | author-link = Bernard Chazelle | | last = Chazelle | first = Bernard | author-link = Bernard Chazelle | ||
| doi = 10.1145/355541.355562 | | doi = 10.1145/355541.355562 | ||
Line 110: | Line 109: | ||
| volume = 47 | | volume = 47 | ||
| year = 2000| s2cid = 12556140| doi-access = free | | year = 2000| s2cid = 12556140| doi-access = free | ||
}}.</ref> इसके चलने का समय है {{math|''[[Big O notation|O]]''(''m'' α(''m'',''n''))}}, | }}.</ref> इसके चलने का समय है {{math|''[[Big O notation|O]]''(''m'' α(''m'',''n''))}}, जहाँ {{math|α}} शास्त्रीय कार्यात्मक एकरमैन फ़ंक्शन इनवर्स है। प्रोग्राम {{math|α}} अत्यंत धीमी गति से बढ़ता है, जिससे सभी व्यावहारिक उद्देश्यों के लिए इसे 4 से अधिक नहीं स्थिरांक माना जा सके; इस प्रकार चेज़ेल का एल्गोरिदम रैखिक समय के बहुत निकट ले जाता है। | ||
=== विशेष | === विशेष स्थितियों में रैखिक-समय एल्गोरिदम === | ||
==== सघन रेखांकन ==== | ==== सघन रेखांकन ==== | ||
यदि ग्राफ सघन है (अर्थात्) {{math|''m''/''n'' ≥ log log log ''n'')}}, फिर फ्रेडमैन और टार्जन द्वारा नियतात्मक एल्गोरिदम समय | यदि ग्राफ सघन है (अर्थात्) {{math|''m''/''n'' ≥ log log log ''n'')}}, फिर फ्रेडमैन और टार्जन द्वारा नियतात्मक एल्गोरिदम समय {{math|O(''m'')}} में एमएसटी का पता लगाता है .<ref>{{Cite journal | doi = 10.1145/28869.28874| title = फाइबोनैचि हीप्स और बेहतर नेटवर्क अनुकूलन एल्गोरिदम में उनका उपयोग| journal = Journal of the ACM| volume = 34| issue = 3| pages = 596| year = 1987| last1 = Fredman | first1 = M. L. | last2 = Tarjan | first2 = R. E. | s2cid = 7904683}}</ref> एल्गोरिदम कई चरणों को क्रियान्वित करता है। प्रत्येक चरण प्राइम के एल्गोरिदम को कई बार निष्पादित करता है, प्रत्येक चरण सीमित संख्या में चरणों के लिए। प्रत्येक चरण का रन-टाइम {{math|O(''m'' + ''n'')}} है यदि चरण से पहले शीर्षों की संख्या {{mvar|n'}} है चरण के बाद शेष शीर्षों की संख्या <math>\tfrac{n'}{2^{m/n'}}</math> अधिकतम होती है . इसलिए, अधिक से अधिक {{math|log*''n''}} चरणों की आवश्यकता होती है, जो घने ग्राफ़ के लिए रैखिक रन-टाइम देता है।<ref name=PettieRamachandran2002/> | ||
ऐसे अन्य एल्गोरिदम हैं जो घने ग्राफ़ पर रैखिक समय में काम करते हैं।<ref name=Chazelle2000/><ref>{{Cite journal | doi = 10.1007/bf02579168| title = अप्रत्यक्ष और निर्देशित ग्राफ़ में न्यूनतम फैले हुए पेड़ों को खोजने के लिए कुशल एल्गोरिदम| journal = Combinatorica| volume = 6| issue = 2| pages = 109| year = 1986| last1 = Gabow | first1 = H. N. | author1-link = Harold N. Gabow | last2 = Galil | first2 = Z. | last3 = Spencer | first3 = T. | last4 = Tarjan | first4 = R. E. | s2cid = 35618095}}</ref> | ऐसे अन्य एल्गोरिदम हैं जो घने ग्राफ़ पर रैखिक समय में काम करते हैं।<ref name=Chazelle2000/><ref>{{Cite journal | doi = 10.1007/bf02579168| title = अप्रत्यक्ष और निर्देशित ग्राफ़ में न्यूनतम फैले हुए पेड़ों को खोजने के लिए कुशल एल्गोरिदम| journal = Combinatorica| volume = 6| issue = 2| pages = 109| year = 1986| last1 = Gabow | first1 = H. N. | author1-link = Harold N. Gabow | last2 = Galil | first2 = Z. | last3 = Spencer | first3 = T. | last4 = Tarjan | first4 = R. E. | s2cid = 35618095}}</ref> | ||
==== पूर्णांक भार ==== | ==== पूर्णांक भार ==== | ||
यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, | यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, जिससे नियतात्मक एल्गोरिदम ज्ञात होते हैं जो {{math|''O''(''m'' + ''n'')}} पूर्णांक संचालन समस्या को हल करते हैं ।<ref>{{citation | ||
| last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman | | last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman | ||
| last2 = Willard | first2 = D. E. | author2-link = Dan Willard | | last2 = Willard | first2 = D. E. | author2-link = Dan Willard | ||
Line 134: | Line 131: | ||
| volume = 48 | | volume = 48 | ||
| year = 1994| doi-access = free | | year = 1994| doi-access = free | ||
}}.</ref> | }}.</ref> क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है। | ||
क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है। | |||
=== निर्णय ट्री === | === निर्णय ट्री === | ||
दिया गया ग्राफ {{mvar|G}} जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी [[निर्णय वृक्ष|निर्णय ट्री]] (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है {{mvar|x}} और {{mvar|y}} बीच के किनारे के वजन से बड़ा {{mvar|w}} और {{mvar|z}}? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची | दिया गया ग्राफ {{mvar|G}} जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी [[निर्णय वृक्ष|निर्णय ट्री]] (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है {{mvar|x}} और {{mvar|y}} बीच के किनारे के वजन से बड़ा {{mvar|w}} और {{mvar|z}}? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची {{mvar|G}} होती है जो एमएसटी के अनुरूप है। डीटी की रनटाइम जटिलता एमएसटी को खोजने के लिए आवश्यक प्रश्नों की सबसे बड़ी संख्या है, जो डीटी की गहराई है। ग्राफ़ के लिए डीटी {{mvar|G}} को इष्टतम कहा जाता है यदि इसमें सभी सही डीटी {{mvar|G}} की तुलना में सबसे छोटी गहराई होटी है . | ||
प्रत्येक पूर्णांक के लिए {{mvar|r}}, सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री | प्रत्येक पूर्णांक के लिए {{mvar|r}}, सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री {{mvar|r}} खोज संभव है पाशविक-बल खोज द्वारा शिखर। यह खोज दो चरणों में आगे बढ़ती है. | ||
A. सभी संभावित डीटी उत्पन्न करना | A. सभी संभावित डीटी उत्पन्न करना | ||
* | *{{mvar|r}} शीर्षों पर <math>2^{r \choose 2}</math> अलग-अलग ग्राफ़ हैं। | ||
* प्रत्येक ग्राफ़ के लिए | *प्रत्येक ग्राफ़ के लिए एक एमएसटी सदैव {{math|''r''(''r'' – 1)}} तुलनाओं का उपयोग करके पाया जा सकता है जैसे प्राइम के एल्गोरिदम द्वारा। | ||
* इसलिए, | * इसलिए, {{math|''r''{{sup|2}}}} इष्टतम डीटी की गहराई से कम है . | ||
* इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या | * इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या <math>2^{r^2}</math> कम है . | ||
* प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या | * प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या {{math|''r''{{sup|2}}}} अधिकतम है इसलिए तुलनाओं की भिन्न संख्या अधिकतम {{math|''r''{{sup|4}}}} है . | ||
* इसलिए, संभावित डीटी की संख्या <p> | * इसलिए, संभावित डीटी की संख्या से कम है | ||
* <p> <math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.</math></p> | |||
बी. सही डीटी की पहचान करना | बी. सही डीटी की पहचान करना | ||
यह जांचने के लिए कि क्या डीटी सही है, इसे किनारे के वजन के सभी संभावित क्रमपरिवर्तनों पर जांचा जाना चाहिए। | यह जांचने के लिए कि क्या डीटी सही है, इसे किनारे के वजन के सभी संभावित क्रमपरिवर्तनों पर जांचा जाना चाहिए। | ||
*ऐसे क्रमपरिवर्तनों की संख्या | *ऐसे क्रमपरिवर्तनों की संख्या {{math|(''r''{{sup|2}})!}} अधिकतम है . | ||
* प्रत्येक क्रमपरिवर्तन के लिए, किसी भी | * प्रत्येक क्रमपरिवर्तन के लिए, किसी भी वर्तमान एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें। | ||
* किसी भी | * किसी भी एमएसटी एल्गोरिदम का रनिंग टाइम अधिकतम {{math|''r''{{sup|2}}}} होता है , इसलिए सभी क्रमपरिवर्तनों की जांच करने के लिए आवश्यक कुल समय {{math|(''r''{{sup|2}} + 1)!}} अधिकतम है . | ||
इसलिए, सभी ग्राफ़ के लिए इष्टतम डीटी खोजने के लिए आवश्यक कुल समय {{mvar|r}} शीर्ष है:<ref name=PettieRamachandran2002/>: | |||
<math>2^{r \choose 2} \cdot r^{2^{(r^2+2)}} \cdot (r^2+1)!,</math> | |||
जो कि कम है | जो कि कम है | ||
:<math>2^{2^{r^2+o(r)}}.</math> | :<math>2^{2^{r^2+o(r)}}.</math> | ||
{{See also| | {{See also|निर्णय ट्री मॉडल}} | ||
=== इष्टतम एल्गोरिदम === | === इष्टतम एल्गोरिदम === | ||
[[सेठ पेटी]] और [[विजय रामचन्द्रन]] ने पाया है {{not a typo| | [[सेठ पेटी]] और [[विजय रामचन्द्रन]] ने पाया है {{not a typo|सिद्धतः}} इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम है।<ref name=PettieRamachandran2002>{{citation | ||
| last1 = Pettie | first1 = Seth | | last1 = Pettie | first1 = Seth | ||
| last2 = Ramachandran | first2 = Vijaya | | last2 = Ramachandran | first2 = Vijaya | ||
Line 178: | Line 178: | ||
}}.</ref> निम्नलिखित एल्गोरिथम का सरलीकृत विवरण है। | }}.</ref> निम्नलिखित एल्गोरिथम का सरलीकृत विवरण है। | ||
# | # माना {{math|1=''r'' = log log log ''n''}}, जहाँ {{mvar|n}} शीर्षों की संख्या है. सभी इष्टतम निर्णय ट्री खोजें {{mvar|r}} शिखर. यह {{math|''O''(''n'')}} समय रहते किया जा सकता है (ऊपर निर्णय ट्री देखें)। | ||
# ग्राफ़ | # ग्राफ़ {{mvar|r}} को अधिकतम घटकों में विभाजित करें प्रत्येक घटक में शीर्ष यह विभाजन सॉफ्ट हीप का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है। | ||
# प्रत्येक घटक के | # प्रत्येक घटक के अन्दर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें। | ||
# एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को | # एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को प्रयुक्त करें जो समय में {{math|''O''(''m'')}} घने ग्राफ़ पर काम करता है अभ्रष्ट उपसमूह के संकुचन के लिए | ||
# परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें | # परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें जिससे सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और प्रारंभिक ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम प्रयुक्त करें। | ||
एल्गोरिथम | एल्गोरिथम {{math|''O''(''m'')}} में सभी चरणों का रनटाइम है , निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह सिद्ध हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से उत्तम नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है {{not a typo|सिद्धतः}} इष्टतम, चूँकि इसकी रनटाइम जटिलता अज्ञात है। | ||
=== समानांतर और वितरित एल्गोरिदम === | === समानांतर और वितरित एल्गोरिदम === | ||
{{further| | {{further|न्यूनतम स्पैनिंग ट्री के लिए समानांतर एल्गोरिदम}} | ||
अनुसंधान ने न्यूनतम | |||
प्रोसेसर की रैखिक संख्या | अनुसंधान ने न्यूनतम स्पैनिंग ट्री की समस्या के लिए [[समानांतर एल्गोरिदम]] पर भी विचार किया है। प्रोसेसर की रैखिक संख्या {{math|''O''(log ''n'')}} समय के साथ समस्या को हल करना संभव है।<ref>{{citation | ||
| last1 = Chong | first1 = Ka Wong | | last1 = Chong | first1 = Ka Wong | ||
| last2 = Han | first2 = Yijie | | last2 = Han | first2 = Yijie | ||
Line 212: | Line 212: | ||
| volume = 31 | | volume = 31 | ||
| year = 2002| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf | | year = 2002| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf | ||
}}.</ref> | }}.</ref> {{harvtxt|बदर|कांग|2006}} एल्गोरिदम प्रदर्शित करें जो अनुकूलित अनुक्रमिक एल्गोरिदम की तुलना में 8 प्रोसेसर पर 5 गुना तेजी से एमएसटी की गणना कर सकता है।<ref>{{citation | ||
{{harvtxt| | |||
| last1 = Bader | first1 = David A. | author1-link = David Bader (computer scientist) | | last1 = Bader | first1 = David A. | author1-link = David Bader (computer scientist) | ||
| last2 = Cong | first2 = Guojing | | last2 = Cong | first2 = Guojing | ||
Line 223: | Line 222: | ||
| volume = 66 | | volume = 66 | ||
| year = 2006| s2cid = 2004627 }}.</ref> | | year = 2006| s2cid = 2004627 }}.</ref> | ||
अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम | |||
अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम स्पैनिंग ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी संग्रहण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।<ref>{{citation | |||
| last1 = Dementiev | first1 = Roman | | last1 = Dementiev | first1 = Roman | ||
| last2 = Sanders | first2 = Peter | | last2 = Sanders | first2 = Peter | ||
Line 232: | Line 232: | ||
| title = Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) | | title = Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) | ||
| url = http://algo2.iti.kit.edu/dementiev/files/emst.pdf | | url = http://algo2.iti.kit.edu/dementiev/files/emst.pdf | ||
| year = 2004}}.</ref> लेखकों के | | year = 2004}}.</ref> लेखकों के प्रमाणों के अनुसार, यह पारंपरिक इन-मेमोरी एल्गोरिदम की तुलना में 2 से 5 गुना धीमी गति से काम कर सकता है। वे ग्राफ़ के आकार को कुशलतापूर्वक कम करने के लिए कुशल बाहरी सॉर्टिंग और ग्राफ़ संकुचन तकनीकों पर विश्वास करते हैं। | ||
समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के | समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, तब भी कोई वितरित न्यूनतम स्पैनिंग ट्री की गणना कर सकता है। | ||
==यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी== | ==यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी == | ||
एलन एम. फ़्रीज़ ने दिखाया कि n शीर्षों पर [[पूरा ग्राफ]] | एलन एम. फ़्रीज़ ने दिखाया कि n शीर्षों पर [[पूरा ग्राफ]] दिया गया है, किनारे के वजन के साथ जो वितरण फ़ंक्शन के साथ स्वतंत्र समान <math>F</math> रूप से वितरित यादृच्छिक चर हैं संतुष्टि देने वाला <math>F'(0) > 0</math>, फिर जैसे-जैसे n विस्तारित वास्तविक संख्या रेखा के निकट पहुंचता है | <math>\zeta(3)/F'(0)</math> +∞ एमएसटी का अपेक्षित वजन निकट आता है , जहाँ <math>\zeta</math> [[रीमैन ज़ेटा फ़ंक्शन]] है (अधिक विशेष रूप से है)। <math>\zeta(3)</math> एपेरी का स्थिरांक)। फ़्रीज़ और जे. माइकल स्टील ने भी संभाव्यता में अभिसरण सिद्ध किया था। [[ स्वंते जानसन | स्वंते जानसन]] ने एमएसटी के वजन के लिए [[केंद्रीय सीमा प्रमेय]] सिद्ध किया था। | ||
एकसमान यादृच्छिक भार के लिए <math>[0,1]</math>, छोटे पूर्ण ग्राफ़ के लिए न्यूनतम | एकसमान यादृच्छिक भार के लिए <math>[0,1]</math>, छोटे पूर्ण ग्राफ़ के लिए न्यूनतम स्पैनिंग ट्री के सटीक अपेक्षित आकार की गणना की गई है।<ref>{{citation | ||
| last = Steele | first = J. Michael | author-link = J. Michael Steele | | last = Steele | first = J. Michael | author-link = J. Michael Steele | ||
| contribution = Minimal spanning trees for graphs with random edge lengths | | contribution = Minimal spanning trees for graphs with random edge lengths | ||
Line 252: | Line 252: | ||
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
! | !कार्यक्षेत्र | ||
! | !अपेक्षित आकार | ||
! | !अनुमानित अपेक्षित आकार | ||
|- | |- | ||
|2 | |2 | ||
Line 288: | Line 288: | ||
|1.0979027 | |1.0979027 | ||
|} | |} | ||
==अनुप्रयोग == | |||
==अनुप्रयोग== | |||
न्यूनतम स्पैनिंग ट्री का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें [[ संगणक संजाल ]], [[दूरसंचार नेटवर्क]], परिवहन नेटवर्क, [[जल आपूर्ति नेटवर्क]] और [[विद्युत ग्रिड]] सम्मिलित हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।<ref>{{citation | न्यूनतम स्पैनिंग ट्री का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें [[ संगणक संजाल ]], [[दूरसंचार नेटवर्क]], परिवहन नेटवर्क, [[जल आपूर्ति नेटवर्क]] और [[विद्युत ग्रिड]] सम्मिलित हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।<ref>{{citation | ||
| last1 = Graham | first1 = R. L. | author1-link = Ronald Graham | | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham | ||
Line 301: | Line 299: | ||
| title = On the history of the minimum spanning tree problem | | title = On the history of the minimum spanning tree problem | ||
| volume = 7 | | volume = 7 | ||
| year = 1985| s2cid = 10555375 }}</ref> उन्हें अन्य समस्याओं के लिए एल्गोरिदम में सबरूटीन के रूप में | | year = 1985| s2cid = 10555375 }}</ref> उन्हें अन्य समस्याओं के लिए एल्गोरिदम में सबरूटीन के रूप में प्रयुक्त किया जाता है, जिसमें [[ट्रैवलिंग सेल्समैन की समस्या]] का अनुमान लगाने के लिए [[क्रिस्टोफ़ाइड्स एल्गोरिथ्म]] भी सम्मिलित है,<ref>[[Nicos Christofides]], [https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf Worst-case analysis of a new heuristic for the travelling salesman problem], Report 388, Graduate School of Industrial Administration, CMU, 1976.</ref> बहु-टर्मिनल न्यूनतम कट समस्या का अनुमान लगाना (जो एकल-टर्मिनल स्थिति में [[अधिकतम प्रवाह समस्या]] के सामान्य है),<ref>{{cite journal | ||
|last1 = Dahlhaus | |last1 = Dahlhaus | ||
|first1 = E. | |first1 = E. | ||
Line 328: | Line 326: | ||
|archive-url = https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf | |archive-url = https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf | ||
|archive-date = 24 August 2004 | |archive-date = 24 August 2004 | ||
}}</ref> | }}</ref> और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाता है <ref>{{cite conference | ||
और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान | |||
| url = http://dl.acm.org/citation.cfm?id=804689 | | url = http://dl.acm.org/citation.cfm?id=804689 | ||
| title = Heuristics for weighted perfect matching | | title = Heuristics for weighted perfect matching | ||
Line 344: | Line 341: | ||
| pages =398–419 | | pages =398–419 | ||
| doi =10.1145/800141.804689 | | doi =10.1145/800141.804689 | ||
}}</ref> | }}</ref> | ||
न्यूनतम स्पैनिंग ट्री पर आधारित अन्य व्यावहारिक अनुप्रयोगों में सम्मिलित हैं: | न्यूनतम स्पैनिंग ट्री पर आधारित अन्य व्यावहारिक अनुप्रयोगों में सम्मिलित हैं: | ||
* [[वर्गीकरण (सामान्य)]]।<ref>{{cite journal|last=Sneath|first=P. H. A.|title=वर्गीकरण विज्ञान में कंप्यूटर का अनुप्रयोग|journal=Journal of General Microbiology|date=1 August 1957|volume=17|issue=1|pages=201–226|doi=10.1099/00221287-17-1-201|pmid=13475686|doi-access=free}}</ref> | * [[वर्गीकरण (सामान्य)]]।<ref>{{cite journal|last=Sneath|first=P. H. A.|title=वर्गीकरण विज्ञान में कंप्यूटर का अनुप्रयोग|journal=Journal of General Microbiology|date=1 August 1957|volume=17|issue=1|pages=201–226|doi=10.1099/00221287-17-1-201|pmid=13475686|doi-access=free}}</ref> | ||
* [[क्लस्टर विश्लेषण]]: समतल में क्लस्टरिंग बिंदु,<ref>{{cite conference|last1=Asano|first1=T.|author1-link=Tetsuo Asano|last2=Bhattacharya|first2=B.|last3=Keil|first3=M.|last4=Yao|first4=F.|author4-link=Frances Yao|title=न्यूनतम और अधिकतम फैले पेड़ों पर आधारित क्लस्टरिंग एल्गोरिदम|conference=Fourth Annual Symposium on Computational Geometry (SCG '88)|year=1988|volume=1|pages=252–257|doi=10.1145/73393.73419}}</ref> [[सिंगल-लिंकेज क्लस्टरिंग]] ([[पदानुक्रमित क्लस्टरिंग]] की विधि),<ref>{{cite journal|last1=Gower|first1=J. C.|last2=Ross|first2=G. J. S.|title=न्यूनतम फैले हुए पेड़ और एकल लिंकेज क्लस्टर विश्लेषण|journal=Journal of the Royal Statistical Society|year=1969|volume=18|series=C (Applied Statistics)|issue=1|pages=54–64|doi=10.2307/2346439|jstor=2346439}}</ref> ग्राफ़-सैद्धांतिक क्लस्टरिंग,<ref>{{cite journal|last=Päivinen|first=Niina|title=स्केल-मुक्त-जैसी संरचना के न्यूनतम फैले हुए पेड़ के साथ क्लस्टरिंग|journal=Pattern Recognition Letters|date=1 May 2005|volume=26|issue=7|pages=921–930|doi=10.1016/j.patrec.2004.09.039|bibcode=2005PaReL..26..921P }}</ref> और क्लस्टरिंग जीन अभिव्यक्ति डेटा।<ref>{{cite journal|last1=Xu|first1=Y.|last2=Olman|first2=V.|last3=Xu|first3=D.|title=Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees|journal=Bioinformatics|date=1 April 2002|volume=18|issue=4|pages=536–545|doi=10.1093/bioinformatics/18.4.536|pmid=12016051|doi-access=free}}</ref> | * [[क्लस्टर विश्लेषण]]: समतल में क्लस्टरिंग बिंदु,<ref>{{cite conference|last1=Asano|first1=T.|author1-link=Tetsuo Asano|last2=Bhattacharya|first2=B.|last3=Keil|first3=M.|last4=Yao|first4=F.|author4-link=Frances Yao|title=न्यूनतम और अधिकतम फैले पेड़ों पर आधारित क्लस्टरिंग एल्गोरिदम|conference=Fourth Annual Symposium on Computational Geometry (SCG '88)|year=1988|volume=1|pages=252–257|doi=10.1145/73393.73419}}</ref> [[सिंगल-लिंकेज क्लस्टरिंग]] ([[पदानुक्रमित क्लस्टरिंग]] की विधि),<ref>{{cite journal|last1=Gower|first1=J. C.|last2=Ross|first2=G. J. S.|title=न्यूनतम फैले हुए पेड़ और एकल लिंकेज क्लस्टर विश्लेषण|journal=Journal of the Royal Statistical Society|year=1969|volume=18|series=C (Applied Statistics)|issue=1|pages=54–64|doi=10.2307/2346439|jstor=2346439}}</ref> ग्राफ़-सैद्धांतिक क्लस्टरिंग,<ref>{{cite journal|last=Päivinen|first=Niina|title=स्केल-मुक्त-जैसी संरचना के न्यूनतम फैले हुए पेड़ के साथ क्लस्टरिंग|journal=Pattern Recognition Letters|date=1 May 2005|volume=26|issue=7|pages=921–930|doi=10.1016/j.patrec.2004.09.039|bibcode=2005PaReL..26..921P }}</ref> और क्लस्टरिंग जीन अभिव्यक्ति डेटा।<ref>{{cite journal|last1=Xu|first1=Y.|last2=Olman|first2=V.|last3=Xu|first3=D.|title=Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees|journal=Bioinformatics|date=1 April 2002|volume=18|issue=4|pages=536–545|doi=10.1093/bioinformatics/18.4.536|pmid=12016051|doi-access=free}}</ref> | ||
* कंप्यूटर नेटवर्क में [[प्रसारण (नेटवर्किंग)]] के लिए ट्री का निर्माण।<ref>{{cite journal|last1=Dalal|first1=Yogen K.|last2=Metcalfe|first2=Robert M.|title=प्रसारण पैकेटों का रिवर्स पथ अग्रेषण|journal=Communications of the ACM|date=1 December 1978|volume=21|issue=12|pages=1040–1048|doi=10.1145/359657.359665|s2cid=5638057}}</ref> | * कंप्यूटर नेटवर्क में [[प्रसारण (नेटवर्किंग)]] के लिए ट्री का निर्माण।<ref>{{cite journal|last1=Dalal|first1=Yogen K.|last2=Metcalfe|first2=Robert M.|title=प्रसारण पैकेटों का रिवर्स पथ अग्रेषण|journal=Communications of the ACM|date=1 December 1978|volume=21|issue=12|pages=1040–1048|doi=10.1145/359657.359665|s2cid=5638057}}</ref> | ||
* [[छवि पंजीकरण]]<ref>{{cite conference|last1=Ma|first1=B.|last2=Hero|first2=A.|last3=Gorman|first3=J.|last4=Michel|first4=O.|title=न्यूनतम स्पैनिंग ट्री एल्गोरिदम के साथ छवि पंजीकरण|conference=International Conference on Image Processing|year=2000|volume=1|pages=481–484|doi=10.1109/ICIP.2000.901000|url=http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |archive-date=2022-10-09 |url-status=live}}</ref> और [[छवि विभाजन]]<ref>P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)</ref> - [[न्यूनतम फैले हुए वृक्ष-आधारित विभाजन|न्यूनतम | * [[छवि पंजीकरण]] <ref>{{cite conference|last1=Ma|first1=B.|last2=Hero|first2=A.|last3=Gorman|first3=J.|last4=Michel|first4=O.|title=न्यूनतम स्पैनिंग ट्री एल्गोरिदम के साथ छवि पंजीकरण|conference=International Conference on Image Processing|year=2000|volume=1|pages=481–484|doi=10.1109/ICIP.2000.901000|url=http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://web.eecs.umich.edu/~hero/Preprints/MinimumSpanningTree.pdf |archive-date=2022-10-09 |url-status=live}}</ref> और [[छवि विभाजन]]<ref>P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)</ref> - [[न्यूनतम फैले हुए वृक्ष-आधारित विभाजन|न्यूनतम स्पैनिंग ट्री-आधारित विभाजन]] देखें। | ||
* [[कंप्यूटर दृष्टि]] में वक्ररेखीय सुविधा निष्कर्षण।<ref>{{cite journal|last1=Suk|first1=Minsoo|last2=Song|first2=Ohyoung|title=न्यूनतम फैले पेड़ों का उपयोग करके वक्ररेखीय सुविधा निष्कर्षण|journal=Computer Vision, Graphics, and Image Processing|date=1 June 1984|volume=26|issue=3|pages=400–411|doi=10.1016/0734-189X(84)90221-4}}</ref> | * [[कंप्यूटर दृष्टि]] में वक्ररेखीय सुविधा निष्कर्षण।<ref>{{cite journal|last1=Suk|first1=Minsoo|last2=Song|first2=Ohyoung|title=न्यूनतम फैले पेड़ों का उपयोग करके वक्ररेखीय सुविधा निष्कर्षण|journal=Computer Vision, Graphics, and Image Processing|date=1 June 1984|volume=26|issue=3|pages=400–411|doi=10.1016/0734-189X(84)90221-4}}</ref> | ||
* गणितीय अभिव्यक्तियों की लिखावट पहचान।<ref>{{cite book|last1=Tapia|first1=Ernesto|last2=Rojas|first2=Raúl|title=ग्राफ़िक्स पहचान. हाल की प्रगति और परिप्रेक्ष्य|series=Lecture Notes in Computer Science|volume=3088|year=2004|publisher=Springer-Verlag|chapter=Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance|location=Berlin Heidelberg|isbn=978-3540224785|pages=329–340|chapter-url=http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-date=2022-10-09 |url-status=live}}</ref> | * गणितीय अभिव्यक्तियों की लिखावट पहचान।<ref>{{cite book|last1=Tapia|first1=Ernesto|last2=Rojas|first2=Raúl|title=ग्राफ़िक्स पहचान. हाल की प्रगति और परिप्रेक्ष्य|series=Lecture Notes in Computer Science|volume=3088|year=2004|publisher=Springer-Verlag|chapter=Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance|location=Berlin Heidelberg|isbn=978-3540224785|pages=329–340|chapter-url=http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://page.mi.fu-berlin.de/rojas/2003/grec03.pdf |archive-date=2022-10-09 |url-status=live}}</ref> | ||
* [[सर्किट डिज़ाइन]]: कुशल एकाधिक निरंतर गुणन को कार्यान्वित करना, जैसा कि [[परिमित आवेग प्रतिक्रिया]] फ़िल्टर में उपयोग किया जाता है।<ref>{{cite conference|last1=Ohlsson|first1=H.|title=न्यूनतम स्पैनिंग ट्री का उपयोग करके कम जटिलता वाले एफआईआर फिल्टर का कार्यान्वयन|conference=12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004)|year=2004|volume=1|pages=261–264|doi=10.1109/MELCON.2004.1346826}}</ref> | * [[सर्किट डिज़ाइन]]: कुशल एकाधिक निरंतर गुणन को कार्यान्वित करना, जैसा कि [[परिमित आवेग प्रतिक्रिया]] फ़िल्टर में उपयोग किया जाता है।<ref>{{cite conference|last1=Ohlsson|first1=H.|title=न्यूनतम स्पैनिंग ट्री का उपयोग करके कम जटिलता वाले एफआईआर फिल्टर का कार्यान्वयन|conference=12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004)|year=2004|volume=1|pages=261–264|doi=10.1109/MELCON.2004.1346826}}</ref> | ||
* सामाजिक-भौगोलिक क्षेत्रों का क्षेत्रीयकरण, क्षेत्रों का सजातीय, सन्निहित क्षेत्रों में समूहीकरण।<ref>{{cite journal|last=Assunção|first=R. M.|author2=M. C. Neves |author3=G. Câmara |author4=C. Da Costa Freitas |title=Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees|journal=International Journal of Geographical Information Science|year=2006|volume=20|issue=7|pages=797–811|doi=10.1080/13658810600665111|s2cid=2530748|url=https://zenodo.org/record/3832352}}</ref> | * सामाजिक-भौगोलिक क्षेत्रों का क्षेत्रीयकरण, क्षेत्रों का सजातीय, सन्निहित क्षेत्रों में समूहीकरण।<ref>{{cite journal|last=Assunção|first=R. M.|author2=M. C. Neves |author3=G. Câmara |author4=C. Da Costa Freitas |title=Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees|journal=International Journal of Geographical Information Science|year=2006|volume=20|issue=7|pages=797–811|doi=10.1080/13658810600665111|s2cid=2530748|url=https://zenodo.org/record/3832352}}</ref> | ||
* [[ ईकोटोकसीकोलौजी ]] डेटा की तुलना करना।<ref>{{cite journal|last1=Devillers|first1=J.|last2=Dore|first2=J.C.|title=विष विज्ञान में न्यूनतम स्पैनिंग ट्री (एमएसटी) विधि की अनुमानी क्षमता|journal=Ecotoxicology and Environmental Safety|date=1 April 1989|volume=17|issue=2|pages=227–235|doi=10.1016/0147-6513(89)90042-0|pmid=2737116}}</ref> | * [[ ईकोटोकसीकोलौजी | ईकोटोकसीकोलौजी]] डेटा की तुलना करना।<ref>{{cite journal|last1=Devillers|first1=J.|last2=Dore|first2=J.C.|title=विष विज्ञान में न्यूनतम स्पैनिंग ट्री (एमएसटी) विधि की अनुमानी क्षमता|journal=Ecotoxicology and Environmental Safety|date=1 April 1989|volume=17|issue=2|pages=227–235|doi=10.1016/0147-6513(89)90042-0|pmid=2737116}}</ref> | ||
* विद्युत प्रणालियों में टोपोलॉजिकल अवलोकन।<ref>{{cite journal|last1=Mori|first1=H.|last2=Tsuzuki|first2=S.|title=न्यूनतम स्पैनिंग ट्री तकनीक का उपयोग करके टोपोलॉजिकल अवलोकन विश्लेषण के लिए एक तेज़ विधि|journal=IEEE Transactions on Power Systems|date=1 May 1991|volume=6|issue=2|pages=491–500|doi=10.1109/59.76691|bibcode=1991ITPSy...6..491M}}</ref> | * विद्युत प्रणालियों में टोपोलॉजिकल अवलोकन।<ref>{{cite journal|last1=Mori|first1=H.|last2=Tsuzuki|first2=S.|title=न्यूनतम स्पैनिंग ट्री तकनीक का उपयोग करके टोपोलॉजिकल अवलोकन विश्लेषण के लिए एक तेज़ विधि|journal=IEEE Transactions on Power Systems|date=1 May 1991|volume=6|issue=2|pages=491–500|doi=10.1109/59.76691|bibcode=1991ITPSy...6..491M}}</ref> | ||
* द्वि-आयामी सामग्रियों की एकरूपता को मापना।<ref>{{cite journal|last1=Filliben|first1=James J.|last2=Kafadar|first2=Karen|author2-link=Karen Kafadar|last3=Shier|first3=Douglas R.|title=द्वि-आयामी सतहों की एकरूपता के लिए परीक्षण|journal=Mathematical Modelling|date=1 January 1983|volume=4|issue=2|pages=167–189|doi=10.1016/0270-0255(83)90026-X|doi-access=free}}</ref> | * द्वि-आयामी सामग्रियों की एकरूपता को मापना।<ref>{{cite journal|last1=Filliben|first1=James J.|last2=Kafadar|first2=Karen|author2-link=Karen Kafadar|last3=Shier|first3=Douglas R.|title=द्वि-आयामी सतहों की एकरूपता के लिए परीक्षण|journal=Mathematical Modelling|date=1 January 1983|volume=4|issue=2|pages=167–189|doi=10.1016/0270-0255(83)90026-X|doi-access=free}}</ref> | ||
* मिनिमैक्स [[प्रक्रिया नियंत्रण]]।<ref>{{citation | last1 = Kalaba | first1 =Robert E. | title = Graph Theory and Automatic Control | url = http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf | archive-url = https://web.archive.org/web/20160221191747/http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf | url-status = dead | archive-date = February 21, 2016 | year = 1963}}</ref> | * मिनिमैक्स [[प्रक्रिया नियंत्रण]]।<ref>{{citation | last1 = Kalaba | first1 =Robert E. | title = Graph Theory and Automatic Control | url = http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf | archive-url = https://web.archive.org/web/20160221191747/http://www.dtic.mil/dtic/tr/fulltext/u2/297072.pdf | url-status = dead | archive-date = February 21, 2016 | year = 1963}}</ref> | ||
* वित्तीय बाज़ारों का वर्णन करने के लिए न्यूनतम स्पैनिंग ट्री का भी उपयोग किया जा सकता है।<ref>Mantegna, R. N. (1999). [https://arxiv.org/abs/cond-mat/9802256 Hierarchical structure in financial markets]. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.</ref><ref>Djauhari, M., & Gan, S. (2015). [https://www.researchgate.net/profile/Maman_Djauhari3/publication/277250327_Optimality_problem_of_network_topology_in_stocks_market_analysis/links/59ebdb7d4585151983cb7795/Optimality-problem-of-network-topology-in-stocks-market-analysis.pdf Optimality problem of network topology in stocks market analysis]. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.</ref> किन्हीं दो शेयरों के बीच सहसंबंध के गुणांक की गणना करके सहसंबंध मैट्रिक्स बनाया जा सकता है। इस मैट्रिक्स को टोपोलॉजिकल रूप से जटिल नेटवर्क के रूप में दर्शाया जा सकता है और | * वित्तीय बाज़ारों का वर्णन करने के लिए न्यूनतम स्पैनिंग ट्री का भी उपयोग किया जा सकता है।<ref>Mantegna, R. N. (1999). [https://arxiv.org/abs/cond-mat/9802256 Hierarchical structure in financial markets]. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.</ref><ref>Djauhari, M., & Gan, S. (2015). [https://www.researchgate.net/profile/Maman_Djauhari3/publication/277250327_Optimality_problem_of_network_topology_in_stocks_market_analysis/links/59ebdb7d4585151983cb7795/Optimality-problem-of-network-topology-in-stocks-market-analysis.pdf Optimality problem of network topology in stocks market analysis]. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.</ref> किन्हीं दो शेयरों के बीच सहसंबंध के गुणांक की गणना करके सहसंबंध मैट्रिक्स बनाया जा सकता है। इस मैट्रिक्स को टोपोलॉजिकल रूप से जटिल नेटवर्क के रूप में दर्शाया जा सकता है और संबंधो की कल्पना करने के लिए न्यूनतम स्पैनिंग ट्री का निर्माण किया जा सकता है। | ||
==संबंधित समस्याएँ== | ==संबंधित समस्याएँ== | ||
{{regular_polygon_minimum_spanning_tree.svg}} | {{regular_polygon_minimum_spanning_tree.svg}} | ||
शीर्षों के उपसमुच्चय के स्टीनर ट्री को खोजने की समस्या, अर्थात, दिए गए उपसमुच्चय को फैलाने वाला न्यूनतम ट्री, एनपी-पूर्ण के रूप में जाना जाता है।<ref>{{Garey-Johnson}}. ND12</ref> | शीर्षों के उपसमुच्चय के स्टीनर ट्री को खोजने की समस्या, अर्थात, दिए गए उपसमुच्चय को फैलाने वाला न्यूनतम ट्री, एनपी-पूर्ण के रूप में जाना जाता है।<ref>{{Garey-Johnson}}. ND12</ref> एक संबंधित समस्या k-न्यूनतम स्पैनिंग ट्री है | k-न्यूनतम स्पैनिंग ट्री (k-एमएसटी), जो कि वह ट्री है जो न्यूनतम वजन के साथ ग्राफ में k शीर्षों के कुछ सबसेट को फैलाता है। | ||
एक संबंधित समस्या k-न्यूनतम स्पैनिंग ट्री है|k-न्यूनतम स्पैनिंग ट्री (k- | |||
K-सबसे छोटे | K-सबसे छोटे स्पैनिंग ट्री का सेट k स्पैनिंग ट्री का उपसमूह है (सभी संभावित स्पैनिंग ट्री में से) जिससे उपसमूह के बाहर किसी भी स्पैनिंग ट्री का वजन कम नही होटी है।<ref>{{citation | ||
| last = Gabow | first = Harold N. | author-link = Harold N. Gabow | | last = Gabow | first = Harold N. | author-link = Harold N. Gabow | ||
| mr = 0441784 | | mr = 0441784 | ||
Line 399: | Line 396: | ||
[[ सरलरेखीय न्यूनतम फैलाव वाला वृक्ष | सरलरेखीय न्यूनतम स्पैनिंग ट्री]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं। | [[ सरलरेखीय न्यूनतम फैलाव वाला वृक्ष | सरलरेखीय न्यूनतम स्पैनिंग ट्री]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं। | ||
वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के | वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है किन्तु समाधान के लिए अलग-अलग दृष्टिकोण हैं। | ||
[[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष|क्षमतायुक्त न्यूनतम स्पैनिंग ट्री]] ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। | [[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष|क्षमतायुक्त न्यूनतम स्पैनिंग ट्री]] ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। C को ट्री क्षमता कहा जाता है। सीएमएसटी को इष्टतम विधि से हल करना [[ एनपी कठिन ]] है,<ref>{{citation | ||
| last1 = Jothi | first1 = Raja | | last1 = Jothi | first1 = Raja | ||
| last2 = Raghavachari | first2 = Balaji | | last2 = Raghavachari | first2 = Balaji | ||
Line 412: | Line 409: | ||
| doi=10.1145/1103963.1103967 | | doi=10.1145/1103963.1103967 | ||
| s2cid = 8302085 | | s2cid = 8302085 | ||
}}</ref> किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के | }}</ref> किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के निकट समाधान उत्पन्न करते हैं। | ||
डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या d के लिए d अन्य शीर्षों से अधिक नहीं जुड़ा होता है। | डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या d के लिए d अन्य शीर्षों से अधिक नहीं जुड़ा होता है। स्थिति d = 2 ट्रैवलिंग सेल्समैन समस्या का विशेष स्थिति है, इसलिए न्यूनतम स्पैनिंग ट्री की डिग्री सामान्य रूप से एनपी-हार्ड है। | ||
[[निर्देशित ग्राफ]] | [[निर्देशित ग्राफ]] के लिए, न्यूनतम स्पैनिंग ट्री की समस्या को आर्बोरेसेंस (ग्राफ़ सिद्धांत) समस्या कहा जाता है और इसे हल किया जा सकता है <math>O(E + V \log V)</math> चू-लियू/एडमंड्स एल्गोरिथम का उपयोग करते हुए समय होता है। | ||
अधिकतम | अधिकतम स्पैनिंग ट्री फैला हुआ ट्री होता है जिसका वजन हर दूसरे स्पैनिंग ट्री के वजन से अधिक या उसके सामान्य होता है। | ||
इस तरह के ट्री को किनारे के वजन को -1 से गुणा करने और हल करने के बाद प्राइम या क्रुस्कल जैसे एल्गोरिदम के साथ पाया जा सकता है | इस तरह के ट्री को किनारे के वजन को -1 से गुणा करने और हल करने के बाद प्राइम या क्रुस्कल जैसे एल्गोरिदम के साथ पाया जा सकता है नए ग्राफ़ पर एमएसटी समस्या अधिकतम स्पैनिंग ट्री में पथ अपने दो समापन बिंदुओं के बीच ग्राफ में सबसे व्यापक पथ समस्या है: सभी संभावित पथों के बीच, यह न्यूनतम-भार वाले किनारे के वजन को अधिकतम करता है।<ref>{{citation | ||
नए ग्राफ़ पर एमएसटी | |||
| last = Hu | first = T. C. | | last = Hu | first = T. C. | ||
| issue = 6 | | issue = 6 | ||
Line 431: | Line 427: | ||
| doi=10.1287/opre.9.6.898| doi-access = free | | doi=10.1287/opre.9.6.898| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
अधिकतम | |||
अधिकतम स्पैनिंग ट्री [[प्राकृतिक भाषा प्रसंस्करण]] के लिए [[ पदच्छेद | पदच्छेद]] एल्गोरिदम में अनुप्रयोग पाते हैं <ref>{{cite conference | |||
| last1 = McDonald | first1 = Ryan | | last1 = McDonald | first1 = Ryan | ||
| last2 = Pereira | first2 = Fernando | | last2 = Pereira | first2 = Fernando | ||
Line 439: | Line 436: | ||
| book-title = Proc. HLT/EMNLP | | book-title = Proc. HLT/EMNLP | ||
| year = 2005 | | year = 2005 | ||
| url = http://www.seas.upenn.edu/~strctlrn/bib/PDF/nonprojectiveHLT-EMNLP2005.pdf}}</ref> | | url = http://www.seas.upenn.edu/~strctlrn/bib/PDF/nonprojectiveHLT-EMNLP2005.pdf}}</ref> और [[सशर्त यादृच्छिक क्षेत्र]] के लिए प्रशिक्षण एल्गोरिदम है। | ||
और [[सशर्त यादृच्छिक क्षेत्र]] | |||
डायनेमिक एमएसटी समस्या मूल ग्राफ़ में किनारे के वजन में बदलाव या शीर्ष के सम्मिलन/हटाने के बाद पहले से गणना की गई एमएसटी के अद्यतन से संबंधित है।<ref>{{citation | डायनेमिक एमएसटी समस्या मूल ग्राफ़ में किनारे के वजन में बदलाव या शीर्ष के सम्मिलन/हटाने के बाद पहले से गणना की गई एमएसटी के अद्यतन से संबंधित है।<ref>{{citation | ||
Line 475: | Line 471: | ||
| year = 1978 | | year = 1978 | ||
| doi=10.1016/0022-0000(78)90022-3| doi-access = free | | doi=10.1016/0022-0000(78)90022-3| doi-access = free | ||
}}.</ref> | }}.</ref> न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को खोज है यदि ग्राफ़ में प्रत्येक किनारा वजन के अतिरिक्त परिमित लेबल सेट से लेबल से संयोजित है।<ref>{{citation | ||
न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को | |||
| last1 = Chang | first1 = R.S. | | last1 = Chang | first1 = R.S. | ||
| last2 = Leu | first2 = S.J. | | last2 = Leu | first2 = S.J. | ||
Line 485: | Line 480: | ||
| title = The minimum labeling spanning trees | | title = The minimum labeling spanning trees | ||
| year = 1997 | | year = 1997 | ||
| doi=10.1016/s0020-0190(97)00127-0}}.</ref> | | doi=10.1016/s0020-0190(97)00127-0}}.</ref> टोंटी किनारा स्पैनिंग ट्री में सबसे अधिक भार वाला किनारा होता है। स्पैनिंग ट्री न्यूनतम टोंटी स्पैनिंग ट्री (या एमबीएसटी) है यदि ग्राफ़ में छोटे टोंटी किनारे के वजन वाला स्पैनिंग ट्री नहीं है। एमएसटी आवश्यक रूप से एमबीएसटी है ({{not a typo|सिद्ध}} कट प्रॉपर्टी द्वारा), किन्तु एमबीएसटी आवश्यक रूप से एमएसटी नहीं है।<ref>{{cite web|url=http://flashing-thoughts.blogspot.ru/2010/06/everything-about-bottleneck-spanning.html|title=बॉटलनेक स्पैनिंग ट्री के बारे में सब कुछ|website=flashing-thoughts.blogspot.ru|date=5 June 2010 |access-date=4 April 2018}}</ref><ref>{{Cite web |url=http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf |title=संग्रहीत प्रति|access-date=2014-07-02 |archive-date=2013-06-12 |archive-url=https://web.archive.org/web/20130612080859/http://pages.cpsc.ucalgary.ca/~dcatalin/413/t4.pdf |url-status=dead }}</ref> | ||
टोंटी किनारा | ==संदर्भ == | ||
==संदर्भ== | |||
{{Reflist|30em}} | {{Reflist|30em}} | ||
==अग्रिम पठन== | ==अग्रिम पठन== | ||
* [http://citeseer.ist.psu.edu/nesetril00otakar.html Otakar Boruvka on Minimum Spanning Tree Problem (translation of both 1926 papers, | * [http://citeseer.ist.psu.edu/nesetril00otakar.html Otakar Boruvka on Minimum Spanning Tree Problem (translation of both 1926 papers, Comments, history) (2000)] [[Jaroslav Nešetřil]], Eva Milková, Helena Nesetrilová. (SeCtion 7 gives his algorithm, whiCh looks like a Cross between Prim's and Kruskal's.) | ||
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', | * [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms|IntroduCtion to Algorithms]]'', SeCond Edition. MIT Press and MCGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Chapter 23: Minimum Spanning Trees, pp. 561–579. | ||
* Eisner, Jason (1997). [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf State-of-the-art algorithms for minimum spanning trees: A tutorial | * Eisner, Jason (1997). [http://www.cs.jhu.edu/~jason/papers/eisner.mst-tutorial.pdf State-of-the-art algorithms for minimum spanning trees: A tutorial disCussion]. ManusCript, University of Pennsylvania, April. 78 pp. | ||
* Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, | * Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, RaCe and EthniC Relations, 17/e (2009 MCGraw Hill) (Using minimum spanning tree as method of demographiC analysis of ethniC diversity aCross the United States). | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
{{commons category|Minimum spanning trees}} | {{commons category|Minimum spanning trees}} | ||
* [http://www.boost.org/libs/graph/doc/table_of_contents.html Implemented in BGL, the Boost Graph Library] | * [http://www.boost.org/libs/graph/doc/table_of_contents.html Implemented in BGL, the Boost Graph Library] | ||
* [http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml The Stony Brook Algorithm Repository - Minimum Spanning Tree | * [http://www.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml The Stony Brook Algorithm Repository - Minimum Spanning Tree Codes] | ||
* [https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph Implemented in | * [https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph Implemented in QuiCkGraph for .Net] | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:Commons category link is locally defined]] | |||
[[Category:Created On 25/06/2023]] | [[Category:Created On 25/06/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:बहुपद-समय की समस्याएँ]] |
Latest revision as of 12:48, 14 July 2023
![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/langen-gb-300px-Minimum_spanning_tree.svg.png)
न्यूनतम स्पैनिंग ट्री (एमएसटी) या न्यूनतम वेट स्पैनिंग ट्री संयोजित ग्राफ के किनारों का उपसमूह है, किनारे-भारित अप्रत्यक्ष ग्राफ जो बिना किसी चक्र (ग्राफ सिद्धांत) के सभी वर्टेक्स (ग्राफ सिद्धांत) को साथ जोड़ता है। [1] अर्थात, यह फैला हुआ ट्री है जिसके किनारे के भार का योग यथासंभव छोटा है। [2] अधिक सामान्यतः, किसी भी किनारे-भारित अप्रत्यक्ष ग्राफ (आवश्यक रूप से जुड़ा नहीं) में न्यूनतम स्पैनिंग जंगल होते हैं, जो इसके जुड़े घटक (ग्राफ सिद्धांत) के लिए न्यूनतम स्पैनिंग ट्री का संघ है।
न्यूनतम स्पैनिंग ट्री के लिए कई उपयोग के स्थिति हैं। उदाहरण दूरसंचार कंपनी है जो नए पड़ोस में केबल बिछाने की प्रयास कर रही है। यदि केबल को केवल कुछ निश्चित रास्तों (जैसे सड़कों) के किनारे गाड़ने के लिए बाध्य किया जाता है, जिससे उन रास्तों से जुड़े बिंदुओं (जैसे घरों) को सम्मिलित करने वाला ग्राफ होता है। कुछ रास्ते अधिक महंगे हो सकते हैं, क्योंकि वे लंबे हैं, या केबल को अधिक गहराई तक गाड़ने की आवश्यकता होती है; इन पथों को बड़े भार वाले किनारों द्वारा दर्शाया जाता है। मुद्रा किनारे के वजन के लिए स्वीकार्य इकाई है त्रिकोण असमानता जैसे ज्यामिति के सामान्य नियमों का पालन करने के लिए किनारे की लंबाई की कोई आवश्यकता नहीं है। उस ग्राफ़ के लिए स्पैनिंग ट्री उन रास्तों का उपसमूह होगा जिनमें कोई चक्र नहीं है किन्तु फिर भी वे हर घर को जोड़ते हैं; वहाँ अनेक स्पैनिंग ट्री संभव हो सकते हैं। न्यूनतम स्पैनिंग ट्री सबसे कम कुल निवेश वाला होगा, जो केबल बिछाने के लिए सबसे कम खर्चीले पथ का प्रतिनिधित्व करता है।
, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के
गुण
संभावित बहुलता
यदि ग्राफ़ में n शीर्ष हैं तो प्रत्येक स्पैनिंग ट्री में n − 1 किनारे हैं।
एक ही वजन के कई न्यूनतम स्पैनिंग ट्री हो सकते हैं; विशेष रूप से, यदि किसी दिए गए ग्राफ़ के सभी किनारों का भार समान है, जिससे उस ग्राफ़ का प्रत्येक फैला हुआ ट्री न्यूनतम है।
अद्वितीयता
यदि प्रत्येक किनारे का अलग वजन है जिससे केवल एक, अद्वितीय न्यूनतम स्पैनिंग ट्री होता है। यह कई यथार्थवादी स्थितियों में सही है, जैसे कि ऊपर दूरसंचार कंपनी का उदाहरण, जहां यह संभव नहीं है कि किन्हीं दो रास्तों की निवेश पूर्ण रूप से समान होता है। यह विस्तृत वनों का भी सामान्यीकरण करता है।
प्रमाण:
- विरोधाभास से प्रमाण, कि दो A और B अलग-अलग एमएसटी हैं.
- चूंकि A और B समान नोड्स होने के अतिरिक्त भिन्न हैं, इसलिए कम से कम एक किनारा ऐसा है जो एक का है किन्तु दूसरे का नहीं। ऐसे किनारों के बीच मान लीजिए कि e1 सबसे कम वजन वाला है, यह विकल्प अद्वितीय है क्योंकि सभी किनारों का वजन अलग-अलग है। व्यापकता की हानि के बिना मान लें कि e1, A में है।
- चूँकि B एक एमएसटी है {e1} ∪ B में e1 के साथ एक चक्र C होना चाहिए।
- चूंकि ट्री A में कोई चक्र नहीं है इसलिए C का एक किनारा e2 होना चाहिए जो A में नहीं है।
- चूँकि e1 को A और B में से किसी एक से संबंधित अद्वितीय सबसे कम वजन वाले किनारे के रूप में चुना गया था, इसलिए e2 का वजन e1 के वजन से अधिक होना चाहिए।
- चूँकि e1 और e2 चक्र C का भाग हैं, इसलिए B में e2 को e1 से बदलने पर कम वजन वाला एक स्पैनिंग ट्री प्राप्त होता है।
- यह इस धारणा का खंडन करता है कि B एमएसटी है.
अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं जिससे न्यूनतम स्पैनिंग ट्री में वजन का केवल बहु सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम स्पैनिंग ट्री के लिए समान है।[3]
न्यूनतम-निवेश उपग्राफ
यदि भार सकारात्मक हैं, जिससे न्यूनतम स्पैनिंग ट्री, वास्तव में, ग्राफ सिद्धांत की न्यूनतम-निवेश शब्दावली है सभी शीर्षों को जोड़ने वाले सबग्राफ, क्योंकि यदि सबग्राफ में पथ (ग्राफ सिद्धांत) होता है, तो उस चक्र के साथ किसी भी किनारे को हटाने से कमी आएगी इसकी निवेश और कनेक्टिविटी को सुरक्षित रखें।
साइकिल प्रोपर्टी
ग्राफ़ में किसी भी चक्र C के लिए यदि C के किनारे e का वजन C के अन्य सभी किनारों के किसी भी व्यक्तिगत वजन से बड़ा है तो यह किनारा एमएसटी से संबंधित नहीं हो सकता है।
प्रमाण: इसके विपरीत मान लें कि e एक एमएसटी T1 से संबंधित है। फिर e को हटाने से T1 दो सबट्री में टूट जाएगा और e के दोनों सिरे अलग-अलग सबट्री में होंगे। C का शेष भाग सबट्री को फिर से जोड़ता है इसलिए C का एक किनारा f होता है जिसके सिरे अलग-अलग सबट्री में होते हैं अर्थात यह सबट्री को T1 के भार से कम भार वाले T2 वृक्ष में पुनः जोड़ता है क्योंकि f का भार e के भार से कम है।
प्रोपर्टी कट
किसी भी कट के लिए (ग्राफ सिद्धांत) C ग्राफ़ का, यदि किनारे का भार e के कट-सेट में C कट-सेट के अन्य सभी किनारों के वजन से पूर्ण रूप से छोटा है C, तो यह किनारा ग्राफ़ के सभी एमएसटी से संबंधित है।
प्रमाण: यह कहना व्यर्थ है कि एमएसटी T है जिसमें सम्मिलित e नहीं है . जोड़ा जा रहा है e को T चक्र का उत्पादन करेगा, जो एक ही बार में कट को पार कर जाएगा e और दूसरे किनारे पर वापस चला जाता है e'. हटाया जा रहा है e' हमें फैला हुआ ट्री मिलता है T∖{e' } ∪ {e} की तुलना में सख्ती से कम वजन का T. यह इस धारणा का खंडन करता है कि T एमएसटी था.
इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम स्पैनिंग ट्री में समाहित होता है।
न्यूनतम-निवेश बढ़त
यदि न्यूनतम निवेश बढ़त e किसी ग्राफ़ का अद्वितीय है, जिससे यह किनारा किसी भी एमएसटी में सम्मिलित है।
प्रमाण: यदि e को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था e एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होता है।
संकुचन
यदि T एमएसटी किनारों का ट्री है, तो हम अनुबंध कर सकते हैं T अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर T संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।[4]
एल्गोरिदम
नीचे दिए गए सभी एल्गोरिदम में, m ग्राफ़ में किनारों की संख्या है और n शीर्षों की संख्या है.
क्लासिक एल्गोरिदम
न्यूनतम स्पैनिंग ट्री को खोजने के लिए पहला एल्गोरिदम 1926 में चेक वैज्ञानिक ओटाकर बोरोव्का द्वारा विकसित किया गया था (बोरोव्का का एल्गोरिदम देखें)। इसका उद्देश्य मोराविया का कुशल विद्युत कवरेज था। एल्गोरिदम चरणों के अनुक्रम में आगे बढ़ता है। प्रत्येक चरण में, जिसे बोरुव्का चरण कहा जाता है, यह जंगल की पहचान करता है F ग्राफ़ में प्रत्येक शीर्ष पर न्यूनतम-वजन वाली बढ़त की घटना सम्मिलित है G, फिर ग्राफ बनाता है G1 = G \ F अगले चरण के इनपुट के रूप में। यहाँ G \ F से प्राप्त ग्राफ़ को दर्शाता है G किनारों को अंदर की ओर सिकोड़कर F (कट प्रोपर्टी के अनुसार, ये किनारे एमएसटी से संबंधित हैं)। प्रत्येक बोरुव्का चरण में रैखिक समय लगता है। चूँकि प्रत्येक चरण में शीर्षों की संख्या कम से कम आधी हो जाती है, बोरुव्का का एल्गोरिथ्म O(m log n) समय लेता है।[4]
दूसरा एल्गोरिथम प्राइम का एल्गोरिथम है, जिसका आविष्कार 1930 में वोजटेक जार्निक द्वारा किया गया था और 1957 में रॉबर्ट सी. प्राइम और 1959 में एडस्गर डब्ल्यू. डिज्क्स्ट्रा द्वारा फिर से खोजा गया था। मूल रूप से, यह एमएसटी को बढ़ाता है (T) समय में किनारा प्रारंभ में, T में सही शीर्ष सम्मिलित है। प्रत्येक चरण में, T को कम से कम वजन वाले किनारे के साथ संवर्धित किया गया है (x,y) ऐसा है कि x में है T और y अभी तक अंदर नहीं है T. कट प्रॉपर्टी द्वारा, सभी किनारों को जोड़ा गया T एमएसटी में हैं। इसका रन-टाइम या तो है O(m log n) या O(m + n log n), प्रयुक्त डेटा-संरचनाओं पर निर्भर करता है।
सामान्यतः उपयोग में आने वाला तीसरा एल्गोरिदम क्रुस्कल का एल्गोरिदम है, जो O(m log n) समय भी लेता है ।
एक चौथा एल्गोरिदम, जो सामान्यतः उपयोग नहीं किया जाता है, रिवर्स-डिलीट एल्गोरिदम है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है O(m log n (log log n)3).
ये चारों ग्रीडी एल्गोरिदम हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफपी (जटिलता) में है, और संबंधित निर्णय समस्याएं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं।
तेज़ एल्गोरिदम
कई शोधकर्ताओं ने अधिक कम्प्यूटेशनल रूप से कुशल एल्गोरिदम खोजने का प्रयास किया है।
एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, कर्गेर, कलें & टार्जन (1995) बोरोव्का के एल्गोरिदम और रिवर्स-डिलीट एल्गोरिदम के संयोजन के आधार पर अपेक्षित रैखिक समय एमएसटी एल्गोरिदम मिला था।[5][6]
ज्ञात जटिलता के साथ सबसे तेज़ गैर-यादृच्छिक तुलना-आधारित एल्गोरिदम, बर्नार्ड चेज़ेल द्वारा, सॉफ्ट हीप , अनुमानित प्राथमिकता कतार पर आधारित है।[7][8] इसके चलने का समय है O(m α(m,n)), जहाँ α शास्त्रीय कार्यात्मक एकरमैन फ़ंक्शन इनवर्स है। प्रोग्राम α अत्यंत धीमी गति से बढ़ता है, जिससे सभी व्यावहारिक उद्देश्यों के लिए इसे 4 से अधिक नहीं स्थिरांक माना जा सके; इस प्रकार चेज़ेल का एल्गोरिदम रैखिक समय के बहुत निकट ले जाता है।
विशेष स्थितियों में रैखिक-समय एल्गोरिदम
सघन रेखांकन
यदि ग्राफ सघन है (अर्थात्) m/n ≥ log log log n), फिर फ्रेडमैन और टार्जन द्वारा नियतात्मक एल्गोरिदम समय O(m) में एमएसटी का पता लगाता है .[9] एल्गोरिदम कई चरणों को क्रियान्वित करता है। प्रत्येक चरण प्राइम के एल्गोरिदम को कई बार निष्पादित करता है, प्रत्येक चरण सीमित संख्या में चरणों के लिए। प्रत्येक चरण का रन-टाइम O(m + n) है यदि चरण से पहले शीर्षों की संख्या n' है चरण के बाद शेष शीर्षों की संख्या अधिकतम होती है . इसलिए, अधिक से अधिक log*n चरणों की आवश्यकता होती है, जो घने ग्राफ़ के लिए रैखिक रन-टाइम देता है।[4]
ऐसे अन्य एल्गोरिदम हैं जो घने ग्राफ़ पर रैखिक समय में काम करते हैं।[7][10]
पूर्णांक भार
यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, जिससे नियतात्मक एल्गोरिदम ज्ञात होते हैं जो O(m + n) पूर्णांक संचालन समस्या को हल करते हैं ।[11] क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है।
निर्णय ट्री
दिया गया ग्राफ G जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी निर्णय ट्री (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है x और y बीच के किनारे के वजन से बड़ा w और z? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची G होती है जो एमएसटी के अनुरूप है। डीटी की रनटाइम जटिलता एमएसटी को खोजने के लिए आवश्यक प्रश्नों की सबसे बड़ी संख्या है, जो डीटी की गहराई है। ग्राफ़ के लिए डीटी G को इष्टतम कहा जाता है यदि इसमें सभी सही डीटी G की तुलना में सबसे छोटी गहराई होटी है .
प्रत्येक पूर्णांक के लिए r, सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री r खोज संभव है पाशविक-बल खोज द्वारा शिखर। यह खोज दो चरणों में आगे बढ़ती है.
A. सभी संभावित डीटी उत्पन्न करना
- r शीर्षों पर अलग-अलग ग्राफ़ हैं।
- प्रत्येक ग्राफ़ के लिए एक एमएसटी सदैव r(r – 1) तुलनाओं का उपयोग करके पाया जा सकता है जैसे प्राइम के एल्गोरिदम द्वारा।
- इसलिए, r2 इष्टतम डीटी की गहराई से कम है .
- इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या कम है .
- प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या r2 अधिकतम है इसलिए तुलनाओं की भिन्न संख्या अधिकतम r4 है .
- इसलिए, संभावित डीटी की संख्या से कम है
बी. सही डीटी की पहचान करना यह जांचने के लिए कि क्या डीटी सही है, इसे किनारे के वजन के सभी संभावित क्रमपरिवर्तनों पर जांचा जाना चाहिए।
- ऐसे क्रमपरिवर्तनों की संख्या (r2)! अधिकतम है .
- प्रत्येक क्रमपरिवर्तन के लिए, किसी भी वर्तमान एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें।
- किसी भी एमएसटी एल्गोरिदम का रनिंग टाइम अधिकतम r2 होता है , इसलिए सभी क्रमपरिवर्तनों की जांच करने के लिए आवश्यक कुल समय (r2 + 1)! अधिकतम है .
इसलिए, सभी ग्राफ़ के लिए इष्टतम डीटी खोजने के लिए आवश्यक कुल समय r शीर्ष है:[4]:
जो कि कम है
इष्टतम एल्गोरिदम
सेठ पेटी और विजय रामचन्द्रन ने पाया है सिद्धतः इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम है।[4] निम्नलिखित एल्गोरिथम का सरलीकृत विवरण है।
- माना r = log log log n, जहाँ n शीर्षों की संख्या है. सभी इष्टतम निर्णय ट्री खोजें r शिखर. यह O(n) समय रहते किया जा सकता है (ऊपर निर्णय ट्री देखें)।
- ग्राफ़ r को अधिकतम घटकों में विभाजित करें प्रत्येक घटक में शीर्ष यह विभाजन सॉफ्ट हीप का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है।
- प्रत्येक घटक के अन्दर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें।
- एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को प्रयुक्त करें जो समय में O(m) घने ग्राफ़ पर काम करता है अभ्रष्ट उपसमूह के संकुचन के लिए
- परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें जिससे सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और प्रारंभिक ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम प्रयुक्त करें।
एल्गोरिथम O(m) में सभी चरणों का रनटाइम है , निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह सिद्ध हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से उत्तम नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है सिद्धतः इष्टतम, चूँकि इसकी रनटाइम जटिलता अज्ञात है।
समानांतर और वितरित एल्गोरिदम
अनुसंधान ने न्यूनतम स्पैनिंग ट्री की समस्या के लिए समानांतर एल्गोरिदम पर भी विचार किया है। प्रोसेसर की रैखिक संख्या O(log n) समय के साथ समस्या को हल करना संभव है।[12][13] बदर & कांग (2006) एल्गोरिदम प्रदर्शित करें जो अनुकूलित अनुक्रमिक एल्गोरिदम की तुलना में 8 प्रोसेसर पर 5 गुना तेजी से एमएसटी की गणना कर सकता है।[14]
अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम स्पैनिंग ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी संग्रहण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।[15] लेखकों के प्रमाणों के अनुसार, यह पारंपरिक इन-मेमोरी एल्गोरिदम की तुलना में 2 से 5 गुना धीमी गति से काम कर सकता है। वे ग्राफ़ के आकार को कुशलतापूर्वक कम करने के लिए कुशल बाहरी सॉर्टिंग और ग्राफ़ संकुचन तकनीकों पर विश्वास करते हैं।
समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, तब भी कोई वितरित न्यूनतम स्पैनिंग ट्री की गणना कर सकता है।
यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी
एलन एम. फ़्रीज़ ने दिखाया कि n शीर्षों पर पूरा ग्राफ दिया गया है, किनारे के वजन के साथ जो वितरण फ़ंक्शन के साथ स्वतंत्र समान रूप से वितरित यादृच्छिक चर हैं संतुष्टि देने वाला , फिर जैसे-जैसे n विस्तारित वास्तविक संख्या रेखा के निकट पहुंचता है | +∞ एमएसटी का अपेक्षित वजन निकट आता है , जहाँ रीमैन ज़ेटा फ़ंक्शन है (अधिक विशेष रूप से है)। एपेरी का स्थिरांक)। फ़्रीज़ और जे. माइकल स्टील ने भी संभाव्यता में अभिसरण सिद्ध किया था। स्वंते जानसन ने एमएसटी के वजन के लिए केंद्रीय सीमा प्रमेय सिद्ध किया था।
एकसमान यादृच्छिक भार के लिए , छोटे पूर्ण ग्राफ़ के लिए न्यूनतम स्पैनिंग ट्री के सटीक अपेक्षित आकार की गणना की गई है।[16]
कार्यक्षेत्र | अपेक्षित आकार | अनुमानित अपेक्षित आकार |
---|---|---|
2 | 1/2
|
0.5 |
3 | 3/4
|
0.75 |
4 | 31/35
|
0.8857143 |
5 | 893/924
|
0.9664502 |
6 | 278/273
|
1.0183151 |
7 | 30739/29172
|
1.053716 |
8 | 199462271/184848378
|
1.0790588 |
9 | 126510063932/115228853025
|
1.0979027 |
अनुप्रयोग
न्यूनतम स्पैनिंग ट्री का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें संगणक संजाल , दूरसंचार नेटवर्क, परिवहन नेटवर्क, जल आपूर्ति नेटवर्क और विद्युत ग्रिड सम्मिलित हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।[17] उन्हें अन्य समस्याओं के लिए एल्गोरिदम में सबरूटीन के रूप में प्रयुक्त किया जाता है, जिसमें ट्रैवलिंग सेल्समैन की समस्या का अनुमान लगाने के लिए क्रिस्टोफ़ाइड्स एल्गोरिथ्म भी सम्मिलित है,[18] बहु-टर्मिनल न्यूनतम कट समस्या का अनुमान लगाना (जो एकल-टर्मिनल स्थिति में अधिकतम प्रवाह समस्या के सामान्य है),[19] और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाता है [20]
न्यूनतम स्पैनिंग ट्री पर आधारित अन्य व्यावहारिक अनुप्रयोगों में सम्मिलित हैं:
- वर्गीकरण (सामान्य)।[21]
- क्लस्टर विश्लेषण: समतल में क्लस्टरिंग बिंदु,[22] सिंगल-लिंकेज क्लस्टरिंग (पदानुक्रमित क्लस्टरिंग की विधि),[23] ग्राफ़-सैद्धांतिक क्लस्टरिंग,[24] और क्लस्टरिंग जीन अभिव्यक्ति डेटा।[25]
- कंप्यूटर नेटवर्क में प्रसारण (नेटवर्किंग) के लिए ट्री का निर्माण।[26]
- छवि पंजीकरण [27] और छवि विभाजन[28] - न्यूनतम स्पैनिंग ट्री-आधारित विभाजन देखें।
- कंप्यूटर दृष्टि में वक्ररेखीय सुविधा निष्कर्षण।[29]
- गणितीय अभिव्यक्तियों की लिखावट पहचान।[30]
- सर्किट डिज़ाइन: कुशल एकाधिक निरंतर गुणन को कार्यान्वित करना, जैसा कि परिमित आवेग प्रतिक्रिया फ़िल्टर में उपयोग किया जाता है।[31]
- सामाजिक-भौगोलिक क्षेत्रों का क्षेत्रीयकरण, क्षेत्रों का सजातीय, सन्निहित क्षेत्रों में समूहीकरण।[32]
- ईकोटोकसीकोलौजी डेटा की तुलना करना।[33]
- विद्युत प्रणालियों में टोपोलॉजिकल अवलोकन।[34]
- द्वि-आयामी सामग्रियों की एकरूपता को मापना।[35]
- मिनिमैक्स प्रक्रिया नियंत्रण।[36]
- वित्तीय बाज़ारों का वर्णन करने के लिए न्यूनतम स्पैनिंग ट्री का भी उपयोग किया जा सकता है।[37][38] किन्हीं दो शेयरों के बीच सहसंबंध के गुणांक की गणना करके सहसंबंध मैट्रिक्स बनाया जा सकता है। इस मैट्रिक्स को टोपोलॉजिकल रूप से जटिल नेटवर्क के रूप में दर्शाया जा सकता है और संबंधो की कल्पना करने के लिए न्यूनतम स्पैनिंग ट्री का निर्माण किया जा सकता है।
संबंधित समस्याएँ
शीर्षों के उपसमुच्चय के स्टीनर ट्री को खोजने की समस्या, अर्थात, दिए गए उपसमुच्चय को फैलाने वाला न्यूनतम ट्री, एनपी-पूर्ण के रूप में जाना जाता है।[39] एक संबंधित समस्या k-न्यूनतम स्पैनिंग ट्री है | k-न्यूनतम स्पैनिंग ट्री (k-एमएसटी), जो कि वह ट्री है जो न्यूनतम वजन के साथ ग्राफ में k शीर्षों के कुछ सबसेट को फैलाता है।
K-सबसे छोटे स्पैनिंग ट्री का सेट k स्पैनिंग ट्री का उपसमूह है (सभी संभावित स्पैनिंग ट्री में से) जिससे उपसमूह के बाहर किसी भी स्पैनिंग ट्री का वजन कम नही होटी है।[40][41][42] (ध्यान दें कि यह समस्या k-न्यूनतम स्पैनिंग ट्री से असंबंधित है।)
यूक्लिडियन न्यूनतम स्पैनिंग ट्री ग्राफ का स्पैनिंग ट्री है, जिसके किनारों का भार शीर्षों के बीच यूक्लिडियन दूरी के अनुरूप होता है, जो समतल (या स्थान) में बिंदु होते हैं।
सरलरेखीय न्यूनतम स्पैनिंग ट्री ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं।
वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है किन्तु समाधान के लिए अलग-अलग दृष्टिकोण हैं।
क्षमतायुक्त न्यूनतम स्पैनिंग ट्री ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। C को ट्री क्षमता कहा जाता है। सीएमएसटी को इष्टतम विधि से हल करना एनपी कठिन है,[43] किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के निकट समाधान उत्पन्न करते हैं।
डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या d के लिए d अन्य शीर्षों से अधिक नहीं जुड़ा होता है। स्थिति d = 2 ट्रैवलिंग सेल्समैन समस्या का विशेष स्थिति है, इसलिए न्यूनतम स्पैनिंग ट्री की डिग्री सामान्य रूप से एनपी-हार्ड है।
निर्देशित ग्राफ के लिए, न्यूनतम स्पैनिंग ट्री की समस्या को आर्बोरेसेंस (ग्राफ़ सिद्धांत) समस्या कहा जाता है और इसे हल किया जा सकता है चू-लियू/एडमंड्स एल्गोरिथम का उपयोग करते हुए समय होता है।
अधिकतम स्पैनिंग ट्री फैला हुआ ट्री होता है जिसका वजन हर दूसरे स्पैनिंग ट्री के वजन से अधिक या उसके सामान्य होता है। इस तरह के ट्री को किनारे के वजन को -1 से गुणा करने और हल करने के बाद प्राइम या क्रुस्कल जैसे एल्गोरिदम के साथ पाया जा सकता है नए ग्राफ़ पर एमएसटी समस्या अधिकतम स्पैनिंग ट्री में पथ अपने दो समापन बिंदुओं के बीच ग्राफ में सबसे व्यापक पथ समस्या है: सभी संभावित पथों के बीच, यह न्यूनतम-भार वाले किनारे के वजन को अधिकतम करता है।[44]
अधिकतम स्पैनिंग ट्री प्राकृतिक भाषा प्रसंस्करण के लिए पदच्छेद एल्गोरिदम में अनुप्रयोग पाते हैं [45] और सशर्त यादृच्छिक क्षेत्र के लिए प्रशिक्षण एल्गोरिदम है।
डायनेमिक एमएसटी समस्या मूल ग्राफ़ में किनारे के वजन में बदलाव या शीर्ष के सम्मिलन/हटाने के बाद पहले से गणना की गई एमएसटी के अद्यतन से संबंधित है।[46][47][48] न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को खोज है यदि ग्राफ़ में प्रत्येक किनारा वजन के अतिरिक्त परिमित लेबल सेट से लेबल से संयोजित है।[49] टोंटी किनारा स्पैनिंग ट्री में सबसे अधिक भार वाला किनारा होता है। स्पैनिंग ट्री न्यूनतम टोंटी स्पैनिंग ट्री (या एमबीएसटी) है यदि ग्राफ़ में छोटे टोंटी किनारे के वजन वाला स्पैनिंग ट्री नहीं है। एमएसटी आवश्यक रूप से एमबीएसटी है (सिद्ध कट प्रॉपर्टी द्वारा), किन्तु एमबीएसटी आवश्यक रूप से एमएसटी नहीं है।[50][51]
संदर्भ
- ↑ "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 मैनुअल". Numpy and Scipy Documentation — Numpy and Scipy documentation. Retrieved 2021-12-10.
न्यूनतम स्पैनिंग ट्री एक ग्राफ है जिसमें किनारों का सबसेट होता है जो किनारों पर वजन के कुल योग को कम करते हुए सभी जुड़े हुए नोड्स को एक साथ जोड़ता है।
- ↑ "नेटवर्कx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 documentation. Retrieved 2021-12-13.
एक न्यूनतम स्पैनिंग ट्री ग्राफ़ का एक सबग्राफ (एक ट्री) है जिसमें किनारे के भार का न्यूनतम योग होता है। एक फैला हुआ जंगल ग्राफ़ के प्रत्येक जुड़े घटक के लिए फैले हुए पेड़ों का एक संघ है।
- ↑ "Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?". cs.stackexchange.com. Retrieved 4 April 2018.
- ↑ 4.0 4.1 4.2 4.3 4.4 Pettie, Seth; Ramachandran, Vijaya (2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the Association for Computing Machinery, 49 (1): 16–34, doi:10.1145/505241.505243, MR 2148431, S2CID 5362916.
- ↑ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995), "A randomized linear-time algorithm to find minimum spanning trees", Journal of the Association for Computing Machinery, 42 (2): 321–328, doi:10.1145/201019.201022, MR 1409738, S2CID 832583
- ↑ Pettie, Seth; Ramachandran, Vijaya (2002), "Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms", Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California, pp. 713–722, ISBN 9780898715132
{{citation}}
: CS1 maint: location missing publisher (link). - ↑ 7.0 7.1 Chazelle, Bernard (2000), "A minimum spanning tree algorithm with inverse-Ackermann type complexity", Journal of the Association for Computing Machinery, 47 (6): 1028–1047, doi:10.1145/355541.355562, MR 1866456, S2CID 6276962.
- ↑ Chazelle, Bernard (2000), "The soft heap: an approximate priority queue with optimal error rate", Journal of the Association for Computing Machinery, 47 (6): 1012–1027, doi:10.1145/355541.355554, MR 1866455, S2CID 12556140.
- ↑ Fredman, M. L.; Tarjan, R. E. (1987). "फाइबोनैचि हीप्स और बेहतर नेटवर्क अनुकूलन एल्गोरिदम में उनका उपयोग". Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. S2CID 7904683.
- ↑ Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). "अप्रत्यक्ष और निर्देशित ग्राफ़ में न्यूनतम फैले हुए पेड़ों को खोजने के लिए कुशल एल्गोरिदम". Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. S2CID 35618095.
- ↑ Fredman, M. L.; Willard, D. E. (1994), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
- ↑ Chong, Ka Wong; Han, Yijie; Lam, Tak Wah (2001), "Concurrent threads and optimal parallel minimum spanning trees algorithm", Journal of the Association for Computing Machinery, 48 (2): 297–323, doi:10.1145/375827.375847, MR 1868718, S2CID 1778676.
- ↑ Pettie, Seth; Ramachandran, Vijaya (2002), "A randomized time-work optimal parallel algorithm for finding a minimum spanning forest" (PDF), SIAM Journal on Computing, 31 (6): 1879–1895, doi:10.1137/S0097539700371065, MR 1954882.
- ↑ Bader, David A.; Cong, Guojing (2006), "Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs", Journal of Parallel and Distributed Computing, 66 (11): 1366–1378, doi:10.1016/j.jpdc.2006.06.001, S2CID 2004627.
- ↑ Dementiev, Roman; Sanders, Peter; Schultes, Dominik; Sibeyn, Jop F. (2004), "Engineering an external memory minimum spanning tree algorithm", Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004) (PDF), pp. 195–208.
- ↑ Steele, J. Michael (2002), "Minimal spanning trees for graphs with random edge lengths", Mathematics and computer science, II (Versailles, 2002), Trends Math., Basel: Birkhäuser, pp. 223–245, MR 1940139
- ↑ Graham, R. L.; Hell, Pavol (1985), "On the history of the minimum spanning tree problem", Annals of the History of Computing, 7 (1): 43–57, doi:10.1109/MAHC.1985.10011, MR 0783327, S2CID 10555375
- ↑ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
- ↑ Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (August 1994). "The complexity of multiterminal cuts" (PDF). SIAM Journal on Computing. 23 (4): 864–894. doi:10.1137/S0097539792225297. Archived from the original (PDF) on 24 August 2004. Retrieved 17 December 2012.
- ↑ Supowit, Kenneth J.; Plaisted, David A.; Reingold, Edward M. (1980). Heuristics for weighted perfect matching. 12th Annual ACM Symposium on Theory of Computing (STOC '80). New York, NY, USA: ACM. pp. 398–419. doi:10.1145/800141.804689.
- ↑ Sneath, P. H. A. (1 August 1957). "वर्गीकरण विज्ञान में कंप्यूटर का अनुप्रयोग". Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686.
- ↑ Asano, T.; Bhattacharya, B.; Keil, M.; Yao, F. (1988). न्यूनतम और अधिकतम फैले पेड़ों पर आधारित क्लस्टरिंग एल्गोरिदम. Fourth Annual Symposium on Computational Geometry (SCG '88). Vol. 1. pp. 252–257. doi:10.1145/73393.73419.
- ↑ Gower, J. C.; Ross, G. J. S. (1969). "न्यूनतम फैले हुए पेड़ और एकल लिंकेज क्लस्टर विश्लेषण". Journal of the Royal Statistical Society. C (Applied Statistics). 18 (1): 54–64. doi:10.2307/2346439. JSTOR 2346439.
- ↑ Päivinen, Niina (1 May 2005). "स्केल-मुक्त-जैसी संरचना के न्यूनतम फैले हुए पेड़ के साथ क्लस्टरिंग". Pattern Recognition Letters. 26 (7): 921–930. Bibcode:2005PaReL..26..921P. doi:10.1016/j.patrec.2004.09.039.
- ↑ Xu, Y.; Olman, V.; Xu, D. (1 April 2002). "Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees". Bioinformatics. 18 (4): 536–545. doi:10.1093/bioinformatics/18.4.536. PMID 12016051.
- ↑ Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "प्रसारण पैकेटों का रिवर्स पथ अग्रेषण". Communications of the ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. S2CID 5638057.
- ↑ Ma, B.; Hero, A.; Gorman, J.; Michel, O. (2000). न्यूनतम स्पैनिंग ट्री एल्गोरिदम के साथ छवि पंजीकरण (PDF). International Conference on Image Processing. Vol. 1. pp. 481–484. doi:10.1109/ICIP.2000.901000. Archived (PDF) from the original on 2022-10-09.
- ↑ P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)
- ↑ Suk, Minsoo; Song, Ohyoung (1 June 1984). "न्यूनतम फैले पेड़ों का उपयोग करके वक्ररेखीय सुविधा निष्कर्षण". Computer Vision, Graphics, and Image Processing. 26 (3): 400–411. doi:10.1016/0734-189X(84)90221-4.
- ↑ Tapia, Ernesto; Rojas, Raúl (2004). "Recognition of On-line Handwritten Mathematical Expressions Using a Minimum Spanning Tree Construction and Symbol Dominance" (PDF). ग्राफ़िक्स पहचान. हाल की प्रगति और परिप्रेक्ष्य. Lecture Notes in Computer Science. Vol. 3088. Berlin Heidelberg: Springer-Verlag. pp. 329–340. ISBN 978-3540224785. Archived (PDF) from the original on 2022-10-09.
- ↑ Ohlsson, H. (2004). न्यूनतम स्पैनिंग ट्री का उपयोग करके कम जटिलता वाले एफआईआर फिल्टर का कार्यान्वयन. 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). Vol. 1. pp. 261–264. doi:10.1109/MELCON.2004.1346826.
- ↑ Assunção, R. M.; M. C. Neves; G. Câmara; C. Da Costa Freitas (2006). "Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees". International Journal of Geographical Information Science. 20 (7): 797–811. doi:10.1080/13658810600665111. S2CID 2530748.
- ↑ Devillers, J.; Dore, J.C. (1 April 1989). "विष विज्ञान में न्यूनतम स्पैनिंग ट्री (एमएसटी) विधि की अनुमानी क्षमता". Ecotoxicology and Environmental Safety. 17 (2): 227–235. doi:10.1016/0147-6513(89)90042-0. PMID 2737116.
- ↑ Mori, H.; Tsuzuki, S. (1 May 1991). "न्यूनतम स्पैनिंग ट्री तकनीक का उपयोग करके टोपोलॉजिकल अवलोकन विश्लेषण के लिए एक तेज़ विधि". IEEE Transactions on Power Systems. 6 (2): 491–500. Bibcode:1991ITPSy...6..491M. doi:10.1109/59.76691.
- ↑ Filliben, James J.; Kafadar, Karen; Shier, Douglas R. (1 January 1983). "द्वि-आयामी सतहों की एकरूपता के लिए परीक्षण". Mathematical Modelling. 4 (2): 167–189. doi:10.1016/0270-0255(83)90026-X.
- ↑ Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF), archived from the original (PDF) on February 21, 2016
- ↑ Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.
- ↑ Djauhari, M., & Gan, S. (2015). Optimality problem of network topology in stocks market analysis. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.
- ↑ Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5. ND12
- ↑ Gabow, Harold N. (1977), "Two algorithms for generating weighted spanning trees in order", SIAM Journal on Computing, 6 (1): 139–150, doi:10.1137/0206011, MR 0441784.
- ↑ Eppstein, David (1992), "Finding the k smallest spanning trees", BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188, S2CID 121160520.
- ↑ Frederickson, Greg N. (1997), "Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees", SIAM Journal on Computing, 26 (2): 484–538, doi:10.1137/S0097539792226825, MR 1438526.
- ↑ Jothi, Raja; Raghavachari, Balaji (2005), "Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design", ACM Trans. Algorithms, 1 (2): 265–282, doi:10.1145/1103963.1103967, S2CID 8302085
- ↑ Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055.
- ↑ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF). Proc. HLT/EMNLP.
- ↑ Spira, P. M.; Pan, A. (1975), "On finding and updating spanning trees and shortest paths" (PDF), SIAM Journal on Computing, 4 (3): 375–380, doi:10.1137/0204032, MR 0378466.
- ↑ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel (2001), "Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity", Journal of the Association for Computing Machinery, 48 (4): 723–760, doi:10.1145/502090.502095, MR 2144928, S2CID 7273552.
- ↑ Chin, F.; Houck, D. (1978), "Algorithms for updating minimal spanning trees", Journal of Computer and System Sciences, 16 (3): 333–344, doi:10.1016/0022-0000(78)90022-3.
- ↑ Chang, R.S.; Leu, S.J. (1997), "The minimum labeling spanning trees", Information Processing Letters, 63 (5): 277–282, doi:10.1016/s0020-0190(97)00127-0.
- ↑ "बॉटलनेक स्पैनिंग ट्री के बारे में सब कुछ". flashing-thoughts.blogspot.ru. 5 June 2010. Retrieved 4 April 2018.
- ↑ "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2013-06-12. Retrieved 2014-07-02.
अग्रिम पठन
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of both 1926 papers, Comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (SeCtion 7 gives his algorithm, whiCh looks like a Cross between Prim's and Kruskal's.)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. IntroduCtion to Algorithms, SeCond Edition. MIT Press and MCGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp. 561–579.
- Eisner, Jason (1997). State-of-the-art algorithms for minimum spanning trees: A tutorial disCussion. ManusCript, University of Pennsylvania, April. 78 pp.
- Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, RaCe and EthniC Relations, 17/e (2009 MCGraw Hill) (Using minimum spanning tree as method of demographiC analysis of ethniC diversity aCross the United States).
बाहरी संबंध
![](https://upload.wikimedia.org/wikipedia/commons/thumb/4/4a/Commons-logo.svg/langen-gb-30px-Commons-logo.svg.png)