न्यूनतम स्पैनिंग ट्री (एमएसटी): Difference between revisions

Revision as of 10:47, 4 July 2023

एक समतलीय ग्राफ और उसका न्यूनतम स्पैनिंग ट्री। प्रत्येक किनारे को उसके वजन के साथ लेबल किया गया है, जो यहां लगभग उसकी लंबाई के समानुपाती है।

न्यूनतम स्पैनिंग ट्री (एमएसटी) या न्यूनतम वेट स्पैनिंग ट्री संयोजित ग्राफ के किनारों का उपसमूह है, किनारे-भारित अप्रत्यक्ष ग्राफ जो बिना किसी चक्र (ग्राफ सिद्धांत) के सभी वर्टेक्स (ग्राफ सिद्धांत) को साथ जोड़ता है। ^[1] अर्थात, यह फैला हुआ ट्री है जिसके किनारे के भार का योग यथासंभव छोटा है। ^[2] अधिक सामान्यतः, किसी भी किनारे-भारित अप्रत्यक्ष ग्राफ (आवश्यक रूप से जुड़ा नहीं) में न्यूनतम स्पैनिंग जंगल होते हैं, जो इसके जुड़े घटक (ग्राफ सिद्धांत) के लिए न्यूनतम स्पैनिंग ट्री का संघ है।

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

गुण

संभावित बहुलता

यदि ग्राफ़ में $n$ शीर्ष हैं तो प्रत्येक स्पैनिंग ट्री में $n - 1$ किनारे हैं।

यह आंकड़ा दर्शाता है कि ग्राफ़ में से अधिक न्यूनतम स्पैनिंग ट्री हो सकते हैं। चित्र में, ग्राफ़ के नीचे के दो ट्री दिए गए ग्राफ़ के न्यूनतम स्पैनिंग ट्री की दो संभावनाएँ हैं।

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

अद्वितीयता

यदि प्रत्येक किनारे का अलग वजन है जिससे केवल एक, अद्वितीय न्यूनतम स्पैनिंग ट्री होता है। यह कई यथार्थवादी स्थितियों में सही है, जैसे कि ऊपर दूरसंचार कंपनी का उदाहरण, जहां यह संभव नहीं है कि किन्हीं दो रास्तों की निवेश पूर्ण रूप से समान होता है। यह विस्तृत वनों का भी सामान्यीकरण करता है।

प्रमाण:

विरोधाभास से प्रमाण, कि दो $A$ और $B$ अलग-अलग एमएसटी हैं.
चूंकि $A$ और $B$ समान नोड्स होने के अतिरिक्त भिन्न हैं, इसलिए कम से कम एक किनारा ऐसा है जो एक का है किन्तु दूसरे का नहीं। ऐसे किनारों के बीच मान लीजिए कि $e 1$ सबसे कम वजन वाला है, यह विकल्प अद्वितीय है क्योंकि सभी किनारों का वजन अलग-अलग है। व्यापकता की हानि के बिना मान लें कि $e 1$ , $A$ में है।
चूँकि $B$ एक एमएसटी है ${e 1} \cup B$ में $e 1$ के साथ एक चक्र $C$ होना चाहिए।
चूंकि ट्री A में कोई चक्र नहीं है इसलिए $C$ का एक किनारा $e 2$ होना चाहिए जो $A$ में नहीं है।
चूँकि $e 1$ को $A$ और $B$ में से किसी एक से संबंधित अद्वितीय सबसे कम वजन वाले किनारे के रूप में चुना गया था, इसलिए $e 2$ का वजन $e 1$ के वजन से अधिक होना चाहिए।
चूँकि $e 1$ और $e 2$ चक्र $C$ का भाग हैं, इसलिए $B$ में $e 2$ को $e 1$ से बदलने पर कम वजन वाला एक स्पैनिंग ट्री प्राप्त होता है।
यह इस धारणा का खंडन करता है कि $B$ एमएसटी है.

अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं जिससे न्यूनतम स्पैनिंग ट्री में वजन का केवल बहु सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम स्पैनिंग ट्री के लिए समान है।^[3]

न्यूनतम-निवेश उपग्राफ

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

साइकिल प्रोपर्टी

ग्राफ़ में किसी भी चक्र $C$ के लिए यदि $C$ के किनारे $e$ का वजन $C$ के अन्य सभी किनारों के किसी भी व्यक्तिगत वजन से बड़ा है तो यह किनारा एमएसटी से संबंधित नहीं हो सकता है।

प्रमाण: इसके विपरीत मान लें कि $e$ एक एमएसटी $T 1$ से संबंधित है। फिर $e$ को हटाने से $T 1$ दो सबट्री में टूट जाएगा और $e$ के दोनों सिरे अलग-अलग सबट्री में होंगे। $C$ का शेष भाग सबट्री को फिर से जोड़ता है इसलिए C का एक किनारा $f$ होता है जिसके सिरे अलग-अलग सबट्री में होते हैं अर्थात यह सबट्री को $T 1$ के भार से कम भार वाले $T 2$ वृक्ष में पुनः जोड़ता है क्योंकि f का भार $e$ के भार से कम है।

प्रोपर्टी कट

यह आंकड़ा एमएसटी की कटी हुई प्रोपर्टी को दर्शाता है।

T

दिए गए ग्राफ़ का एकमात्र एमएसटी है। यदि

S = {A, B, D, E},

इस प्रकार

V - S = {C, F},

तो कट के पार किनारे की 3 संभावनाएँ हैं

(S, V - S)

, वे किनारे हैं

BC

,

EC

,

EF

मूल ग्राफ़ का। फिर, ई कट के लिए न्यूनतम-वजन-किनारे में से है

S \cup {e}

एमएसटी का भाग है

T

.

किसी भी कट के लिए (ग्राफ सिद्धांत) $C$ ग्राफ़ का, यदि किनारे का भार $e$ के कट-सेट में $C$ कट-सेट के अन्य सभी किनारों के वजन से पूर्ण रूप से छोटा है $C$ , तो यह किनारा ग्राफ़ के सभी एमएसटी से संबंधित है।

प्रमाण: यह कहना व्यर्थ है कि एमएसटी $T$ है जिसमें सम्मिलित $e$ नहीं है . जोड़ा जा रहा है $e$ को $T$ चक्र का उत्पादन करेगा, जो एक ही बार में कट को पार कर जाएगा $e$ और दूसरे किनारे पर वापस चला जाता है $e'$ . हटाया जा रहा है $e'$ हमें फैला हुआ ट्री मिलता है $T ∖{e'} \cup {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 \geq log log log n)$ , फिर फ्रेडमैन और टार्जन द्वारा नियतात्मक एल्गोरिदम समय $O(m)$ में एमएसटी का पता लगाता है .^[9] एल्गोरिदम कई चरणों को क्रियान्वित करता है। प्रत्येक चरण प्राइम के एल्गोरिदम को कई बार निष्पादित करता है, प्रत्येक चरण सीमित संख्या में चरणों के लिए। प्रत्येक चरण का रन-टाइम $O(m + n)$ है यदि चरण से पहले शीर्षों की संख्या $n'$ है चरण के बाद शेष शीर्षों की संख्या ${\tfrac {n'}{2^{m/n'}}}$ अधिकतम होती है . इसलिए, अधिक से अधिक $log* n$ चरणों की आवश्यकता होती है, जो घने ग्राफ़ के लिए रैखिक रन-टाइम देता है।^[4]

ऐसे अन्य एल्गोरिदम हैं जो घने ग्राफ़ पर रैखिक समय में काम करते हैं।^[7]^[10]

पूर्णांक भार

यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, जिससे नियतात्मक एल्गोरिदम ज्ञात होते हैं जो $O (m + n)$ पूर्णांक संचालन समस्या को हल करते हैं ।^[11] क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है।

निर्णय ट्री

दिया गया ग्राफ $G$ जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी निर्णय ट्री (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है $x$ और $y$ बीच के किनारे के वजन से बड़ा $w$ और $z$ ? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची $G$ होती है जो एमएसटी के अनुरूप है। डीटी की रनटाइम जटिलता एमएसटी को खोजने के लिए आवश्यक प्रश्नों की सबसे बड़ी संख्या है, जो डीटी की गहराई है। ग्राफ़ के लिए डीटी $G$ को इष्टतम कहा जाता है यदि इसमें सभी सही डीटी $G$ की तुलना में सबसे छोटी गहराई होटी है .

प्रत्येक पूर्णांक के लिए $r$ , सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री $r$ खोज संभव है पाशविक-बल खोज द्वारा शिखर। यह खोज दो चरणों में आगे बढ़ती है.

A. सभी संभावित डीटी उत्पन्न करना

$r$ शीर्षों पर $2^{r \choose 2}$ अलग-अलग ग्राफ़ हैं।
प्रत्येक ग्राफ़ के लिए एक एमएसटी सदैव $r (r - 1)$ तुलनाओं का उपयोग करके पाया जा सकता है जैसे प्राइम के एल्गोरिदम द्वारा।
इसलिए, $r 2$ इष्टतम डीटी की गहराई से कम है .
इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या $2^{r^{2}}$ कम है .
प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या $r 2$ अधिकतम है इसलिए तुलनाओं की भिन्न संख्या अधिकतम $r 4$ है .
इसलिए, संभावित डीटी की संख्या से कम है
${(r^{4})}^{(2^{r^{2}})}=r^{2^{(r^{2}+2)}}.$

बी. सही डीटी की पहचान करना यह जांचने के लिए कि क्या डीटी सही है, इसे किनारे के वजन के सभी संभावित क्रमपरिवर्तनों पर जांचा जाना चाहिए।

ऐसे क्रमपरिवर्तनों की संख्या $(r 2)!$ अधिकतम है .
प्रत्येक क्रमपरिवर्तन के लिए, किसी भी वर्तमान एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें।
किसी भी एमएसटी एल्गोरिदम का रनिंग टाइम अधिकतम $r 2$ होता है , इसलिए सभी क्रमपरिवर्तनों की जांच करने के लिए आवश्यक कुल समय $(r 2 + 1)!$ अधिकतम है .

इसलिए, सभी ग्राफ़ के लिए इष्टतम डीटी खोजने के लिए आवश्यक कुल समय $r$ शीर्ष है:^[4]:

$2^{r \choose 2}\cdot r^{2^{(r^{2}+2)}}\cdot (r^{2}+1)!,$

जो कि कम है

2^{2^{r^{2}+o(r)}}.

इष्टतम एल्गोरिदम

सेठ पेटी और विजय रामचन्द्रन ने पाया है सिद्धतः इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम है।^[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 शीर्षों पर पूरा ग्राफ दिया गया है, किनारे के वजन के साथ जो वितरण फ़ंक्शन के साथ स्वतंत्र समान $F$ रूप से वितरित यादृच्छिक चर हैं संतुष्टि देने वाला $F'(0)>0$ , फिर जैसे-जैसे n विस्तारित वास्तविक संख्या रेखा के निकट पहुंचता है | $\zeta (3)/F'(0)$ +∞ एमएसटी का अपेक्षित वजन निकट आता है , जहाँ $\zeta$ रीमैन ज़ेटा फ़ंक्शन है (अधिक विशेष रूप से है)। $\zeta (3)$ एपेरी का स्थिरांक)। फ़्रीज़ और जे. माइकल स्टील ने भी संभाव्यता में अभिसरण सिद्ध किया था। स्वंते जानसन ने एमएसटी के वजन के लिए केंद्रीय सीमा प्रमेय सिद्ध किया था।

एकसमान यादृच्छिक भार के लिए $[0,1]$ , छोटे पूर्ण ग्राफ़ के लिए न्यूनतम स्पैनिंग ट्री के सटीक अपेक्षित आकार की गणना की गई है।^[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] किन्हीं दो शेयरों के बीच सहसंबंध के गुणांक की गणना करके सहसंबंध मैट्रिक्स बनाया जा सकता है। इस मैट्रिक्स को टोपोलॉजिकल रूप से जटिल नेटवर्क के रूप में दर्शाया जा सकता है और संबंधो की कल्पना करने के लिए न्यूनतम स्पैनिंग ट्री का निर्माण किया जा सकता है।

संदर्भ

↑ "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).

बाहरी संबंध

[1] "scipy.sparse.csgraph.minimum_spanning_tree - SciPy v1.7.1 मैनुअल". Numpy and Scipy Documentation — Numpy and Scipy documentation. Retrieved 2021-12-10. न्यूनतम स्पैनिंग ट्री एक ग्राफ है जिसमें किनारों का सबसेट होता है जो किनारों पर वजन के कुल योग को कम करते हुए सभी जुड़े हुए नोड्स को एक साथ जोड़ता है।

[2] "नेटवर्कx.algorithms.tree.mst.minimum_spanning_edges". NetworkX 2.6.2 documentation. Retrieved 2021-12-13. एक न्यूनतम स्पैनिंग ट्री ग्राफ़ का एक सबग्राफ (एक ट्री) है जिसमें किनारे के भार का न्यूनतम योग होता है। एक फैला हुआ जंगल ग्राफ़ के प्रत्येक जुड़े घटक के लिए फैले हुए पेड़ों का एक संघ है।

[3] "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.

[PettieRamachandran2002-4] 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.

[5] 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

[6] 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).

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

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

[9] Fredman, M. L.; Tarjan, R. E. (1987). "फाइबोनैचि हीप्स और बेहतर नेटवर्क अनुकूलन एल्गोरिदम में उनका उपयोग". Journal of the ACM. 34 (3): 596. doi:10.1145/28869.28874. S2CID 7904683.

[10] Gabow, H. N.; Galil, Z.; Spencer, T.; Tarjan, R. E. (1986). "अप्रत्यक्ष और निर्देशित ग्राफ़ में न्यूनतम फैले हुए पेड़ों को खोजने के लिए कुशल एल्गोरिदम". Combinatorica. 6 (2): 109. doi:10.1007/bf02579168. S2CID 35618095.

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

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

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

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

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

[16] 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

[17] 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

[18] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

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

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

[21] Sneath, P. H. A. (1 August 1957). "वर्गीकरण विज्ञान में कंप्यूटर का अनुप्रयोग". Journal of General Microbiology. 17 (1): 201–226. doi:10.1099/00221287-17-1-201. PMID 13475686.

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

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

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

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

[26] Dalal, Yogen K.; Metcalfe, Robert M. (1 December 1978). "प्रसारण पैकेटों का रिवर्स पथ अग्रेषण". Communications of the ACM. 21 (12): 1040–1048. doi:10.1145/359657.359665. S2CID 5638057.

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

[28] P. Felzenszwalb, D. Huttenlocher: Efficient Graph-Based Image Segmentation. IJCV 59(2) (September 2004)

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

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

[31] Ohlsson, H. (2004). न्यूनतम स्पैनिंग ट्री का उपयोग करके कम जटिलता वाले एफआईआर फिल्टर का कार्यान्वयन. 12th IEEE Mediterranean Electrotechnical Conference (MELECON 2004). Vol. 1. pp. 261–264. doi:10.1109/MELCON.2004.1346826.

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

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

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

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

[36] Kalaba, Robert E. (1963), Graph Theory and Automatic Control (PDF), archived from the original (PDF) on February 21, 2016

[37] Mantegna, R. N. (1999). Hierarchical structure in financial markets. The European Physical Journal B-Condensed Matter and Complex Systems, 11(1), 193–197.

[38] Djauhari, M., & Gan, S. (2015). Optimality problem of network topology in stocks market analysis. Physica A: Statistical Mechanics and Its Applications, 419, 108–114.

[39] 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

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

[41] Eppstein, David (1992), "Finding the k smallest spanning trees", BIT, 32 (2): 237–248, doi:10.1007/BF01994879, MR 1172188, S2CID 121160520.

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

[43] 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

[44] Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055.

[45] McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). "Non-projective dependency parsing using spanning tree algorithms" (PDF). Proc. HLT/EMNLP.

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

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

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

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

[50] "बॉटलनेक स्पैनिंग ट्री के बारे में सब कुछ". flashing-thoughts.blogspot.ru. 5 June 2010. Retrieved 4 April 2018.

[51] "संग्रहीत प्रति" (PDF). Archived from the original (PDF) on 2013-06-12. Retrieved 2014-07-02.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

Anonymous

Search

न्यूनतम स्पैनिंग ट्री (एमएसटी): Difference between revisions

Namespaces

More

Page actions

Revision as of 10:47, 4 July 2023

Contents

गुण

संभावित बहुलता

अद्वितीयता

न्यूनतम-निवेश उपग्राफ

साइकिल प्रोपर्टी

प्रोपर्टी कट

न्यूनतम-निवेश बढ़त

संकुचन

एल्गोरिदम

क्लासिक एल्गोरिदम

तेज़ एल्गोरिदम

विशेष स्थितियों में रैखिक-समय एल्गोरिदम

सघन रेखांकन

पूर्णांक भार

निर्णय ट्री

इष्टतम एल्गोरिदम

समानांतर और वितरित एल्गोरिदम

यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी

अनुप्रयोग

संबंधित समस्याएँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{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}}किनारे.
+यदि ग्राफ़ में {{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}} अलग-अलग एमएसटी हैं.
-# तब से {{mvar|A}} और {{mvar|B}} समान नोड्स होने के बावजूद भिन्न, कम से कम किनारा है जो का है किन्तु दूसरे का नहीं। ऐसे किनारों के बीच, चलो {{math|''e''{{sub|1}}}} सबसे कम वजन वाला हो; यह विकल्प अद्वितीय है क्योंकि किनारों का भार अलग-अलग है। व्यापकता की हानि के बिना, मान लीजिए {{math|''e''{{sub|1}}}} में है {{mvar|A}}.
+#चूंकि {{mvar|A}} और {{mvar|B}} समान नोड्स होने के अतिरिक्त भिन्न हैं, इसलिए कम से कम एक किनारा ऐसा है जो एक का है किन्तु दूसरे का नहीं। ऐसे किनारों के बीच मान लीजिए कि {{math|''e''{{sub|1}}}} सबसे कम वजन वाला है, यह विकल्प अद्वितीय है क्योंकि सभी किनारों का वजन अलग-अलग है। व्यापकता की हानि के बिना मान लें कि {{math|''e''{{sub|1}}}}, {{mvar|A}} में है।
-# जैसा {{mvar|B}} एमएसटी है, {{math|{''e''{{sub|1}}} ∪ ''B''}} में चक्र होना चाहिए {{mvar|C}} साथ {{math|''e''{{sub|1}}}}.
+#चूँकि {{mvar|B}} एक एमएसटी है {{math|{''e''{{sub|1}}} ∪ ''B''}} में {{math|''e''{{sub|1}}}} के साथ एक चक्र {{mvar|C}} होना चाहिए।
-#<nowiki>एक ट्री के रूप में, {{mvar|A}इसलिए, } में कोई चक्र नहीं है </nowiki>{{mvar|C}} बढ़त होनी चाहिए {{math|''e''{{sub|2}}}} वह अंदर नहीं है {{mvar|A}}.
+#चूंकि ट्री 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}}}} को {{mvar|A}} और {{mvar|B}} में से किसी एक से संबंधित अद्वितीय सबसे कम वजन वाले किनारे के रूप में चुना गया था, इसलिए {{math|''e''{{sub|2}}}} का वजन {{math|''e''{{sub|1}}}} के वजन से अधिक होना चाहिए।
-# जैसा {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} चक्र का हिस्सा हैं {{mvar|C}}, प्रतिस्थापित करना {{math|''e''{{sub|2}}}} साथ {{math|''e''{{sub|1}}}} में {{mvar|B}} इसलिए कम वजन वाला फैला हुआ ट्री प्राप्त होता है।
+#चूँकि  {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} चक्र {{mvar|C}} का भाग हैं, इसलिए {{mvar|B}} में {{math|''e''{{sub|2}}}} को {{math|''e''{{sub|1}}}} से बदलने पर कम वजन वाला एक स्पैनिंग ट्री प्राप्त होता है।
 # यह इस धारणा का खंडन करता है कि {{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>
+अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं जिससे न्यूनतम स्पैनिंग ट्री में वजन का केवल बहु सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम स्पैनिंग ट्री के लिए समान है।<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|e}} का {{mvar|C}} अन्य सभी किनारों के किसी भी व्यक्तिगत भार से बड़ा है {{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}} उपट्री को पुनः जोड़ता है, इसलिए किनारा है {{mvar|f}} का {{mvar|C}} अलग-अलग उपट्री में समाप्त होता है, यानी, यह उपट्री को ट्री में फिर से जोड़ता है {{math|''T''{{sub|2}}}} से कम वजन के साथ {{math|''T''{{sub|1}}}}, क्योंकि का वजन {{mvar|f}} के वजन से कम है {{mvar|e}}.
+प्रमाण: इसके विपरीत मान लें कि {{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|यह आंकड़ा एमएसटी की कटी हुई संपत्ति को दर्शाता है। {{mvar|T}} दिए गए ग्राफ़ का एकमात्र MST है। यदि {{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}}, तो यह किनारा ग्राफ़ के सभी MST से संबंधित है।
+[[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}} एमएसटी था.
+प्रमाण: यह कहना व्यर्थ है कि एमएसटी {{mvar|T}} है  जिसमें सम्मिलित {{mvar|e}} नहीं है . जोड़ा जा रहा है {{mvar|e}} को {{mvar|T}} चक्र का उत्पादन करेगा, जो एक ही बार में कट को पार कर जाएगा {{mvar|e}} और दूसरे किनारे पर वापस चला जाता है {{mvar|e'}}. हटाया जा रहा है {{mvar|e'}} हमें फैला हुआ ट्री मिलता है {{math|''T''∖{''e' ''} ∪ {''e''} }} की तुलना में सख्ती से कम वजन का {{mvar|T}}. यह इस धारणा का खंडन करता है कि {{mvar|T}} एमएसटी था.
-इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम फैले हुए ट्री में समाहित होता है।
+इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम स्पैनिंग ट्री में समाहित होता है।
 ===न्यूनतम-निवेश बढ़त===
-<nowiki>यदि न्यूनतम निवेश बढ़त {{mvar|e}किसी ग्राफ़ का } अद्वितीय है, तो यह किनारा किसी भी MST में सम्मिलित है।</nowiki>
+यदि न्यूनतम निवेश बढ़त e किसी ग्राफ़ का अद्वितीय है, जिससे यह किनारा किसी भी एमएसटी में सम्मिलित है।
-प्रमाण: यदि {{mvar|e}} को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होगा।
+प्रमाण: यदि {{mvar|e}} को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होता है।
 ===संकुचन===
@@ Line 51: / Line 51: @@
-==एल्गोरिदम==
+==एल्गोरिदम                                                                                                                                                              ==
 नीचे दिए गए सभी एल्गोरिदम में, {{mvar|m}} ग्राफ़ में किनारों की संख्या है और {{mvar|n}} शीर्षों की संख्या है.
 === क्लासिक एल्गोरिदम ===
-न्यूनतम फैले हुए ट्री को खोजने के लिए पहला एल्गोरिदम 1926 में चेक वैज्ञानिक ओटाकर बोरोव्का द्वारा विकसित किया गया था (बोरोव्का का एल्गोरिदम देखें)। इसका उद्देश्य [[मोराविया]] का कुशल विद्युत कवरेज था। एल्गोरिदम चरणों के अनुक्रम में आगे बढ़ता है। प्रत्येक चरण में, जिसे बोरुव्का चरण कहा जाता है, यह जंगल की पहचान करता है {{mvar|F}} ग्राफ़ में प्रत्येक शीर्ष पर न्यूनतम-वजन वाली बढ़त की घटना सम्मिलित है {{mvar|G}}, फिर ग्राफ बनाता है {{math|1=''G''{{sub|1}} = ''G'' \ ''F''}} अगले चरण के इनपुट के रूप में। यहाँ {{math|''G'' \ ''F''}} से प्राप्त ग्राफ़ को दर्शाता है {{mvar|G}} किनारों को अंदर की ओर सिकोड़कर {{mvar|F}} (#Cut संपत्ति के अनुसार, ये किनारे MST से संबंधित हैं)। प्रत्येक बोरुव्का चरण में रैखिक समय लगता है। चूँकि प्रत्येक चरण में शीर्षों की संख्या कम से कम आधी हो जाती है, बोरुव्का का एल्गोरिथ्म लेता है {{math|''O''(''m'' log ''n'')}} समय।<ref name=PettieRamachandran2002/>
+न्यूनतम स्पैनिंग ट्री को खोजने के लिए पहला एल्गोरिदम 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}}) समय में किनारा। शुरू में, {{mvar|T}} में मनमाना शीर्ष सम्मिलित है। प्रत्येक चरण में, {{mvar|T}} को कम से कम वजन वाले किनारे के साथ संवर्धित किया गया है {{math|(''x'',''y'')}} ऐसा है कि {{mvar|x}} में है {{mvar|T}} और {{mvar|y}} अभी तक अंदर नहीं है {{mvar|T}}. #Cut प्रॉपर्टी द्वारा, सभी किनारों को जोड़ा गया {{mvar|T}} एमएसटी में हैं। इसका रन-टाइम या तो है {{math|''O''(''m'' log ''n'')}} या {{math|''O''(''m'' + ''n'' log ''n'')}}, प्रयुक्त डेटा-संरचनाओं पर निर्भर करता है।
+दूसरा एल्गोरिथम प्राइम का एल्गोरिथम है, जिसका आविष्कार 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'')}} समय भी लेता है ।
-एक चौथा एल्गोरिदम, जो आमतौर पर उपयोग नहीं किया जाता है, [[रिवर्स-डिलीट एल्गोरिदम]] है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है {{math|O(''m'' log ''n'' (log log ''n''){{sup|3}})}}.
+एक चौथा एल्गोरिदम, जो सामान्यतः उपयोग नहीं किया जाता है, [[रिवर्स-डिलीट एल्गोरिदम]] है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है {{math|O(''m'' log ''n'' (log log ''n''){{sup|3}})}}.
-ये चारों [[लालची एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं ( जटिलता)।
+ये चारों [[लालची एल्गोरिदम|ग्रीडी एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं।
 === तेज़ एल्गोरिदम ===
 कई शोधकर्ताओं ने अधिक कम्प्यूटेशनल रूप से कुशल एल्गोरिदम खोजने का प्रयास किया है।
-एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, {{harvtxt|Karger|Klein|Tarjan|1995}} बोरोव्का के एल्गोरिदम और रिवर्स-डिलीट एल्गोरिदम के संयोजन के आधार पर [[अपेक्षित रैखिक समय एमएसटी एल्गोरिदम]] मिला।<ref>{{citation
+एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, {{harvtxt|कर्गेर|कलें|टार्जन|1995}} बोरोव्का के एल्गोरिदम और रिवर्स-डिलीट एल्गोरिदम के संयोजन के आधार पर [[अपेक्षित रैखिक समय एमएसटी एल्गोरिदम]] मिला था।<ref>{{citation
   | last1 = Karger | first1 = David R. | author1-link = David Karger
   | last2 = Klein | first2 = Philip N.
@@ Line 91: / Line 91: @@
   | year = 2002| isbn = 9780898715132
   }}.</ref>
-ज्ञात जटिलता के साथ सबसे तेज़ गैर-यादृच्छिक तुलना-आधारित एल्गोरिदम, [[बर्नार्ड चेज़ेल]] द्वारा, [[ मुलायम ढेर ]], अनुमानित प्राथमिकता कतार पर आधारित है।<ref name=Chazelle2000>{{citation
+ज्ञात जटिलता के साथ सबसे तेज़ गैर-यादृच्छिक तुलना-आधारित एल्गोरिदम, [[बर्नार्ड चेज़ेल]] द्वारा, [[ मुलायम ढेर | सॉफ्ट हीप]] , अनुमानित प्राथमिकता कतार पर आधारित है।<ref name="Chazelle2000">{{citation
   | last = Chazelle | first = Bernard | author-link = Bernard Chazelle
   | doi = 10.1145/355541.355562
@@ Line 110: / Line 111: @@
   | volume = 47
   | year = 2000| s2cid = 12556140| doi-access = free
-  }}.</ref> इसके चलने का समय है {{math|''[[Big O notation|O]]''(''m'' α(''m'',''n''))}}, कहाँ {{math|α}} शास्त्रीय कार्यात्मक एकरमैन फ़ंक्शन#इनवर्स है। कार्यक्रम {{math|α}} अत्यंत धीमी गति से बढ़ता है, ताकि सभी व्यावहारिक उद्देश्यों के लिए इसे 4 से अधिक नहीं स्थिरांक माना जा सके; इस प्रकार चेज़ेल का एल्गोरिदम रैखिक समय के बहुत करीब ले जाता है।
+  }}.</ref> इसके चलने का समय है {{math|''[[Big O notation|O]]''(''m'' α(''m'',''n''))}}, जहाँ {{math|α}} शास्त्रीय कार्यात्मक एकरमैन फ़ंक्शन इनवर्स है। प्रोग्राम {{math|α}} अत्यंत धीमी गति से बढ़ता है, जिससे सभी व्यावहारिक उद्देश्यों के लिए इसे 4 से अधिक नहीं स्थिरांक माना जा सके; इस प्रकार चेज़ेल का एल्गोरिदम रैखिक समय के बहुत निकट ले जाता है।
-=== विशेष मामलों में रैखिक-समय एल्गोरिदम ===
+=== विशेष स्थितियों में रैखिक-समय एल्गोरिदम ===
 ==== सघन रेखांकन ====
-यदि ग्राफ सघन है (अर्थात्) {{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/>
+यदि ग्राफ सघन है (अर्थात्) {{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>
@@ Line 123: / Line 124: @@
 ==== पूर्णांक भार ====
-यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, तो नियतात्मक एल्गोरिदम ज्ञात होते हैं जो समस्या को हल करते हैं {{math|''O''(''m'' + ''n'')}} पूर्णांक संचालन।<ref>{{citation
+यदि किनारे का भार बाइनरी में दर्शाए गए पूर्णांक हैं, जिससे नियतात्मक एल्गोरिदम ज्ञात होते हैं जो {{math|''O''(''m'' + ''n'')}} पूर्णांक संचालन समस्या को हल करते हैं ।<ref>{{citation
   | last1 = Fredman | first1 = M. L. | author1-link = Michael Fredman
   | last2 = Willard | first2 = D. E. | author2-link = Dan Willard
@@ Line 134: / Line 135: @@
   | volume = 48
   | year = 1994| doi-access = free
-  }}.</ref>
+  }}.</ref> क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है।
-क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है।
 === निर्णय ट्री ===
-दिया गया ग्राफ {{mvar|G}} जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी [[निर्णय वृक्ष|निर्णय ट्री]] (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है {{mvar|x}} और {{mvar|y}} बीच के किनारे के वजन से बड़ा {{mvar|w}} और {{mvar|z}}? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची होती है {{mvar|G}} जो एमएसटी के अनुरूप है। डीटी की रनटाइम जटिलता एमएसटी को खोजने के लिए आवश्यक प्रश्नों की सबसे बड़ी संख्या है, जो डीटी की गहराई है। ग्राफ़ के लिए डीटी {{mvar|G}} को इष्टतम कहा जाता है यदि इसमें सभी सही डीटी की तुलना में सबसे छोटी गहराई हो {{mvar|G}}.
+दिया गया ग्राफ {{mvar|G}} जहां नोड्स और किनारे तय हो गए हैं किन्तु वजन अज्ञात है, वजन के किसी भी क्रमपरिवर्तन के लिए एमएसटी की गणना के लिए बाइनरी [[निर्णय वृक्ष|निर्णय ट्री]] (डीटी) का निर्माण करना संभव है। डीटी के प्रत्येक आंतरिक नोड में दो किनारों के बीच तुलना होती है, उदाहरण के लिए के बीच किनारे का वजन है {{mvar|x}} और {{mvar|y}} बीच के किनारे के वजन से बड़ा {{mvar|w}} और {{mvar|z}}? . नोड के दो बच्चे हां या ना में दो संभावित उत्तरों के अनुरूप हैं। डीटी के प्रत्येक पत्ते में किनारों की सूची {{mvar|G}} होती है  जो एमएसटी के अनुरूप है। डीटी की रनटाइम जटिलता एमएसटी को खोजने के लिए आवश्यक प्रश्नों की सबसे बड़ी संख्या है, जो डीटी की गहराई है। ग्राफ़ के लिए डीटी {{mvar|G}} को इष्टतम कहा जाता है यदि इसमें सभी सही डीटी {{mvar|G}} की तुलना में सबसे छोटी गहराई होटी है .
-प्रत्येक पूर्णांक के लिए {{mvar|r}}, सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री ढूंढना संभव है {{mvar|r}} पाशविक-बल खोज द्वारा शिखर। यह खोज दो चरणों में आगे बढ़ती है.
+प्रत्येक पूर्णांक के लिए {{mvar|r}}, सभी ग्राफ़ के लिए इष्टतम निर्णय ट्री {{mvar|r}} खोज संभव है  पाशविक-बल खोज द्वारा शिखर। यह खोज दो चरणों में आगे बढ़ती है.
 A. सभी संभावित डीटी उत्पन्न करना
-* वहाँ हैं <math>2^{r \choose 2}</math> पर अलग-अलग ग्राफ़  {{mvar|r}} शिखर.
+*{{mvar|r}} शीर्षों पर <math>2^{r \choose 2}</math> अलग-अलग ग्राफ़ हैं।
-* प्रत्येक ग्राफ़ के लिए, एमएसटी का उपयोग हमेशा पाया जा सकता है {{math|''r''(''r'' – 1)}} तुलना, उदा. प्राइम के एल्गोरिदम द्वारा।
+*प्रत्येक ग्राफ़ के लिए एक एमएसटी सदैव {{math|''r''(''r'' – 1)}} तुलनाओं का उपयोग करके पाया जा सकता है जैसे प्राइम के एल्गोरिदम द्वारा।
-* इसलिए, इष्टतम डीटी की गहराई से कम है {{math|''r''{{sup|2}}}}.
+* इसलिए, {{math|''r''{{sup|2}}}} इष्टतम डीटी की गहराई से कम है .
-* इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या कम है <math>2^{r^2}</math>.
+* इसलिए, इष्टतम डीटी में आंतरिक नोड्स की संख्या <math>2^{r^2}</math> कम है .
-* प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या अधिकतम है {{math|''r''{{sup|2}}}} इसलिए तुलनाओं की भिन्न संख्या अधिकतम है {{math|''r''{{sup|4}}}}.
+* प्रत्येक आंतरिक नोड दो किनारों की तुलना करता है। किनारों की संख्या {{math|''r''{{sup|2}}}} अधिकतम है  इसलिए तुलनाओं की भिन्न संख्या अधिकतम {{math|''r''{{sup|4}}}} है .
-* इसलिए, संभावित डीटी की संख्या <p> से कम है<math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.</math></p>
+* इसलिए, संभावित डीटी की संख्या से कम है
+* <p> <math>{(r^4)}^{(2^{r^2})} = r^{2^{(r^2+2)}}.</math></p>
 बी. सही डीटी की पहचान करना
 यह जांचने के लिए कि क्या डीटी सही है, इसे किनारे के वजन के सभी संभावित क्रमपरिवर्तनों पर जांचा जाना चाहिए।
-*ऐसे क्रमपरिवर्तनों की संख्या अधिकतम है {{math|(''r''{{sup|2}})!}}.
+*ऐसे क्रमपरिवर्तनों की संख्या {{math|(''r''{{sup|2}})!}} अधिकतम है .
-* प्रत्येक क्रमपरिवर्तन के लिए, किसी भी मौजूदा एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें।
+* प्रत्येक क्रमपरिवर्तन के लिए, किसी भी वर्तमान एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें।
-* किसी भी MST एल्गोरिदम का रनिंग टाइम अधिकतम होता है {{math|''r''{{sup|2}}}}, इसलिए सभी क्रमपरिवर्तनों की जांच करने के लिए आवश्यक कुल समय अधिकतम है {{math|(''r''{{sup|2}} + 1)!}}.
+* किसी भी एमएसटी एल्गोरिदम का रनिंग टाइम अधिकतम {{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>
-इसलिए, सभी ग्राफ़ के लिए इष्टतम डीटी खोजने के लिए आवश्यक कुल समय {{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>
-{{See also|Decision tree model}}
+{{See also|निर्णय ट्री मॉडल}}
 === इष्टतम एल्गोरिदम ===
-[[सेठ पेटी]] और [[विजय रामचन्द्रन]] ने पाया है {{not a typo|provably}} इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम।<ref name=PettieRamachandran2002>{{citation
+[[सेठ पेटी]] और [[विजय रामचन्द्रन]] ने पाया है {{not a typo|सिद्धतः}} इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम है।<ref name=PettieRamachandran2002>{{citation
   | last1 = Pettie | first1 = Seth
   | last2 = Ramachandran | first2 = Vijaya
@@ Line 178: / Line 182: @@
   }}.</ref> निम्नलिखित एल्गोरिथम का सरलीकृत विवरण है।
-# होने देना {{math|1=''r'' = log log log ''n''}}, कहाँ {{mvar|n}} शीर्षों की संख्या है. सभी इष्टतम निर्णय ट्री खोजें {{mvar|r}} शिखर. यह समय रहते किया जा सकता है {{math|''O''(''n'')}} (ऊपर #निर्णय ट्री देखें)।
+# माना {{math|1=''r'' = log log log ''n''}}, जहाँ {{mvar|n}} शीर्षों की संख्या है. सभी इष्टतम निर्णय ट्री खोजें {{mvar|r}} शिखर. यह {{math|''O''(''n'')}} समय रहते किया जा सकता है (ऊपर निर्णय ट्री देखें)।
-# ग्राफ़ को अधिकतम घटकों में विभाजित करें {{mvar|r}} प्रत्येक घटक में शीर्ष। यह विभाजन नरम ढेर का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है।
+# ग्राफ़ {{mvar|r}} को अधिकतम घटकों में विभाजित करें  प्रत्येक घटक में शीर्ष यह विभाजन सॉफ्ट हीप का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है।
-# प्रत्येक घटक के भीतर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें।
+# प्रत्येक घटक के अन्दर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें।
-# एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को लागू करें जो समय में #घने ग्राफ़ पर काम करता है {{math|''O''(''m'')}} अभ्रष्ट उपसमूह के संकुचन के लिए
+# एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को प्रयुक्त करें जो समय में {{math|''O''(''m'')}} घने ग्राफ़ पर काम करता है  अभ्रष्ट उपसमूह के संकुचन के लिए
-# परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें ताकि सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और शुरुआती ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम लागू करें।
+# परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें जिससे सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और प्रारंभिक ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम प्रयुक्त करें।
-एल्गोरिथम में सभी चरणों का रनटाइम है {{math|''O''(''m'')}}, निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह साबित हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से बेहतर नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है{{not a typo|provably}} इष्टतम, हालांकि इसकी रनटाइम जटिलता अज्ञात है।
+एल्गोरिथम {{math|''O''(''m'')}} में सभी चरणों का रनटाइम है , निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह सिद्ध हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से उत्तम नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है {{not a typo|सिद्धतः}} इष्टतम, चूँकि इसकी रनटाइम जटिलता अज्ञात है।
 === समानांतर और वितरित एल्गोरिदम ===
-{{further|Parallel algorithms for minimum spanning trees}}
+{{further|न्यूनतम स्पैनिंग ट्री के लिए समानांतर एल्गोरिदम}}
-अनुसंधान ने न्यूनतम फैले हुए ट्री की समस्या के लिए [[समानांतर एल्गोरिदम]] पर भी विचार किया है।
-प्रोसेसर की रैखिक संख्या के साथ समस्या को हल करना संभव है {{math|''O''(log ''n'')}} समय।<ref>{{citation
+अनुसंधान ने न्यूनतम स्पैनिंग ट्री की समस्या के लिए [[समानांतर एल्गोरिदम]] पर भी विचार किया है। प्रोसेसर की रैखिक संख्या {{math|''O''(log ''n'')}} समय के साथ समस्या को हल करना संभव है।<ref>{{citation
   | last1 = Chong | first1 = Ka Wong
   | last2 = Han | first2 = Yijie
@@ Line 212: / Line 216: @@
   | volume = 31
   | year = 2002| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf
-  }}.</ref>
+  }}.</ref> {{harvtxt|बदर|कांग|2006}} एल्गोरिदम प्रदर्शित करें जो अनुकूलित अनुक्रमिक एल्गोरिदम की तुलना में 8 प्रोसेसर पर 5 गुना तेजी से एमएसटी की गणना कर सकता है।<ref>{{citation
-{{harvtxt|Bader|Cong|2006}} एल्गोरिदम प्रदर्शित करें जो अनुकूलित अनुक्रमिक एल्गोरिदम की तुलना में 8 प्रोसेसर पर 5 गुना तेजी से एमएसटी की गणना कर सकता है।<ref>{{citation
   | last1 = Bader | first1 = David A. | author1-link = David Bader (computer scientist)
   | last2 = Cong | first2 = Guojing
@@ Line 223: / Line 226: @@
   | volume = 66
   | year = 2006| s2cid = 2004627 }}.</ref>
-अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम फैले हुए ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी भंडारण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।<ref>{{citation
+अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम स्पैनिंग ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी संग्रहण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।<ref>{{citation
   | last1 = Dementiev | first1 = Roman
   | last2 = Sanders | first2 = Peter
@@ Line 232: / Line 236: @@
   | 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
-  | year = 2004}}.</ref> लेखकों के दावों के अनुसार, यह पारंपरिक इन-मेमोरी एल्गोरिदम की तुलना में 2 से 5 गुना धीमी गति से काम कर सकता है। वे ग्राफ़ के आकार को कुशलतापूर्वक कम करने के लिए कुशल बाहरी सॉर्टिंग और ग्राफ़ संकुचन तकनीकों पर भरोसा करते हैं।
+  | year = 2004}}.</ref> लेखकों के प्रमाणों के अनुसार, यह पारंपरिक इन-मेमोरी एल्गोरिदम की तुलना में 2 से 5 गुना धीमी गति से काम कर सकता है। वे ग्राफ़ के आकार को कुशलतापूर्वक कम करने के लिए कुशल बाहरी सॉर्टिंग और ग्राफ़ संकुचन तकनीकों पर विश्वास करते हैं।
-समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अलावा कुछ भी नहीं जानता है, तब भी कोई वितरित न्यूनतम स्पैनिंग ट्री की गणना कर सकता है।
+समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, तब भी कोई वितरित न्यूनतम स्पैनिंग ट्री की गणना कर सकता है।
-==यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी==
+==यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी                                                                                                                ==
-एलन एम. फ़्रीज़ ने दिखाया कि n शीर्षों पर [[पूरा ग्राफ]]़ दिया गया है, किनारे के वजन के साथ जो वितरण फ़ंक्शन के साथ स्वतंत्र समान रूप से वितरित यादृच्छिक चर हैं <math>F</math> संतुष्टि देने वाला <math>F'(0) > 0</math>, फिर जैसे-जैसे n विस्तारित वास्तविक संख्या रेखा के करीब पहुंचता है|+∞ MST का अपेक्षित वजन करीब आता है <math>\zeta(3)/F'(0)</math>, कहाँ <math>\zeta</math> [[रीमैन ज़ेटा फ़ंक्शन]] है (अधिक विशेष रूप से है)। <math>\zeta(3)</math> एपेरी का स्थिरांक)। फ़्रीज़ और जे. माइकल स्टील ने भी संभाव्यता में अभिसरण साबित किया। [[ स्वंते जानसन ]] ने एमएसटी के वजन के लिए [[केंद्रीय सीमा प्रमेय]] साबित किया।
+एलन एम. फ़्रीज़ ने दिखाया कि 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>, छोटे पूर्ण ग्राफ़ के लिए न्यूनतम फैले हुए ट्री के सटीक अपेक्षित आकार की गणना की गई है।<ref>{{citation
+एकसमान यादृच्छिक भार के लिए <math>[0,1]</math>, छोटे पूर्ण ग्राफ़ के लिए न्यूनतम स्पैनिंग ट्री के सटीक अपेक्षित आकार की गणना की गई है।<ref>{{citation
   | last = Steele | first = J. Michael | author-link = J. Michael Steele
   | contribution = Minimal spanning trees for graphs with random edge lengths
@@ Line 252: / Line 256: @@
 {| class="wikitable"
 |-
-!Vertices
+!कार्यक्षेत्र
-!Expected size
+!अपेक्षित आकार
-!Approximate expected size
+!अनुमानित अपेक्षित आकार
 |-
 |2
@@ Line 290: / Line 294: @@
-==अनुप्रयोग==
+==अनुप्रयोग                                                                                                                       ==
 न्यूनतम स्पैनिंग ट्री का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें [[ संगणक संजाल ]], [[दूरसंचार नेटवर्क]], परिवहन नेटवर्क, [[जल आपूर्ति नेटवर्क]] और [[विद्युत ग्रिड]] सम्मिलित हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।<ref>{{citation
   | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham
@@ Line 301: / Line 305: @@
   | title = On the history of the minimum spanning tree problem
   | volume = 7
-  | 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
+  | 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
   |first1       = E.
@@ Line 328: / Line 332: @@
   |archive-url   = https://web.archive.org/web/20040824184059/http://akpublic.research.att.com/~dsj/papers/3way.pdf
   |archive-date  = 24 August 2004
-}}</ref>
+}}</ref> और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाता है <ref>{{cite conference
-और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाना।<ref>{{cite conference
 | url = http://dl.acm.org/citation.cfm?id=804689
 | title = Heuristics for weighted perfect matching
@@ Line 344: / Line 347: @@
 | pages =398–419
 | doi =10.1145/800141.804689
 }}</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 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 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 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=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>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}}
-शीर्षों के उपसमुच्चय के स्टीनर ट्री को खोजने की समस्या, अर्थात, दिए गए उपसमुच्चय को फैलाने वाला न्यूनतम ट्री, एनपी-पूर्ण के रूप में जाना जाता है।<ref>{{Garey-Johnson}}. ND12</ref>
+शीर्षों के उपसमुच्चय के स्टीनर ट्री को खोजने की समस्या, अर्थात, दिए गए उपसमुच्चय को फैलाने वाला न्यूनतम ट्री, एनपी-पूर्ण के रूप में जाना जाता है।<ref>{{Garey-Johnson}}. ND12</ref> एक संबंधित समस्या k-न्यूनतम स्पैनिंग ट्री है | k-न्यूनतम स्पैनिंग ट्री (k-एमएसटी), जो कि वह ट्री है जो न्यूनतम वजन के साथ ग्राफ में k शीर्षों के कुछ सबसेट को फैलाता है।
-एक संबंधित समस्या k-न्यूनतम स्पैनिंग ट्री है|k-न्यूनतम स्पैनिंग ट्री (k-MST), जो कि वह ट्री है जो न्यूनतम वजन के साथ ग्राफ में k शीर्षों के कुछ सबसेट को फैलाता है।
-K-सबसे छोटे फैले हुए ट्री का सेट k फैले हुए ट्री का उपसमूह है (सभी संभावित फैले हुए ट्री में से) ताकि उपसमूह के बाहर किसी भी फैले हुए ट्री का वजन कम न हो।<ref>{{citation
+K-सबसे छोटे स्पैनिंग ट्री का सेट k स्पैनिंग ट्री का उपसमूह है (सभी संभावित स्पैनिंग ट्री में से) जिससे उपसमूह के बाहर किसी भी स्पैनिंग ट्री का वजन कम नही होटी है।<ref>{{citation
   | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
   | mr = 0441784
@@ Line 399: / Line 402: @@
 [[ सरलरेखीय न्यूनतम फैलाव वाला वृक्ष | सरलरेखीय न्यूनतम स्पैनिंग ट्री]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं।
-वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अलावा कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है किन्तु समाधान के लिए अलग-अलग दृष्टिकोण हैं।
+वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अतिरिक्त कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है किन्तु समाधान के लिए अलग-अलग दृष्टिकोण हैं।
-[[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष|क्षमतायुक्त न्यूनतम स्पैनिंग ट्री]] ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। c को ट्री क्षमता कहा जाता है। सीएमएसटी को इष्टतम ढंग से हल करना [[ एनपी कठिन ]] है,<ref>{{citation
+[[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष|क्षमतायुक्त न्यूनतम स्पैनिंग ट्री]] ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। C को ट्री क्षमता कहा जाता है। सीएमएसटी को इष्टतम विधि से हल करना [[ एनपी कठिन ]] है,<ref>{{citation
   | last1 = Jothi | first1 = Raja
   | last2 = Raghavachari | first2 = Balaji
@@ Line 412: / Line 415: @@
   | doi=10.1145/1103963.1103967
 | s2cid = 8302085
-  }}</ref> किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के करीब समाधान उत्पन्न करते हैं।
+  }}</ref> किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के निकट समाधान उत्पन्न करते हैं।
-डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या d के लिए d अन्य शीर्षों से अधिक नहीं जुड़ा होता है। मामला d = 2 ट्रैवलिंग सेल्समैन समस्या का विशेष मामला है, इसलिए न्यूनतम स्पैनिंग ट्री की डिग्री सामान्य रूप से एनपी-हार्ड है।
+डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या d के लिए d अन्य शीर्षों से अधिक नहीं जुड़ा होता है। स्थिति d = 2 ट्रैवलिंग सेल्समैन समस्या का विशेष स्थिति है, इसलिए न्यूनतम स्पैनिंग ट्री की डिग्री सामान्य रूप से एनपी-हार्ड है।
-[[निर्देशित ग्राफ]]़ के लिए, न्यूनतम फैले हुए ट्री की समस्या को आर्बोरेसेंस (ग्राफ़ सिद्धांत) समस्या कहा जाता है और इसे हल किया जा सकता है <math>O(E + V \log V)</math> चू-लियू/एडमंड्स एल्गोरिथम का उपयोग करते हुए समय।
+[[निर्देशित ग्राफ]] के लिए, न्यूनतम स्पैनिंग ट्री की समस्या को आर्बोरेसेंस (ग्राफ़ सिद्धांत) समस्या कहा जाता है और इसे हल किया जा सकता है <math>O(E + V \log V)</math> चू-लियू/एडमंड्स एल्गोरिथम का उपयोग करते हुए समय होता है।
-अधिकतम फैलाव वाला ट्री फैला हुआ ट्री होता है जिसका वजन हर दूसरे फैले हुए ट्री के वजन से अधिक या उसके बराबर होता है।
+अधिकतम स्पैनिंग ट्री फैला हुआ ट्री होता है जिसका वजन हर दूसरे स्पैनिंग ट्री के वजन से अधिक या उसके सामान्य होता है।
-इस तरह के ट्री को किनारे के वजन को -1 से गुणा करने और हल करने के बाद प्राइम या क्रुस्कल जैसे एल्गोरिदम के साथ पाया जा सकता है
+इस तरह के ट्री को किनारे के वजन को -1 से गुणा करने और हल करने के बाद प्राइम या क्रुस्कल जैसे एल्गोरिदम के साथ पाया जा सकता है नए ग्राफ़ पर एमएसटी समस्या अधिकतम स्पैनिंग ट्री में पथ अपने दो समापन बिंदुओं के बीच ग्राफ में सबसे व्यापक पथ समस्या है: सभी संभावित पथों के बीच, यह न्यूनतम-भार वाले किनारे के वजन को अधिकतम करता है।<ref>{{citation
-नए ग्राफ़ पर एमएसटी समस्या। अधिकतम फैले हुए ट्री में पथ अपने दो समापन बिंदुओं के बीच ग्राफ में सबसे व्यापक पथ समस्या है: सभी संभावित पथों के बीच, यह न्यूनतम-भार वाले किनारे के वजन को अधिकतम करता है।<ref>{{citation
   | last = Hu | first = T. C.
   | issue = 6
@@ Line 431: / Line 433: @@
   | doi=10.1287/opre.9.6.898| doi-access = free
   }}.</ref>
-अधिकतम फैले हुए ट्री [[प्राकृतिक भाषा प्रसंस्करण]] के लिए [[ पदच्छेद ]] एल्गोरिदम में अनुप्रयोग पाते हैं<ref>{{cite conference
+अधिकतम स्पैनिंग ट्री [[प्राकृतिक भाषा प्रसंस्करण]] के लिए [[ पदच्छेद | पदच्छेद]] एल्गोरिदम में अनुप्रयोग पाते हैं <ref>{{cite conference
   | last1 = McDonald | first1 = Ryan
   | last2 = Pereira | first2 = Fernando
@@ Line 439: / Line 442: @@
   | book-title = Proc. HLT/EMNLP
   | 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
@@ Line 475: / Line 477: @@
   | year = 1978
   | doi=10.1016/0022-0000(78)90022-3| doi-access = free
-  }}.</ref>
+  }}.</ref> न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को खोज है यदि ग्राफ़ में प्रत्येक किनारा वजन के अतिरिक्त परिमित लेबल सेट से लेबल से संयोजित है।<ref>{{citation
-न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को ढूंढना है यदि ग्राफ़ में प्रत्येक किनारा वजन के बजाय परिमित लेबल सेट से लेबल से संयोजित है।<ref>{{citation
   | last1 = Chang | first1 = R.S.
   | last2 = Leu | first2 = S.J.
@@ Line 485: / Line 486: @@
   | title = The minimum labeling spanning trees
   | 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>
-टोंटी किनारा फैले हुए ट्री में सबसे अधिक भार वाला किनारा होता है। स्पैनिंग ट्री न्यूनतम टोंटी स्पैनिंग ट्री (या एमबीएसटी) है यदि ग्राफ़ में छोटे टोंटी किनारे के वजन वाला स्पैनिंग ट्री नहीं है। एमएसटी आवश्यक रूप से एमबीएसटी है ({{not a typo|provable}} #Cut प्रॉपर्टी द्वारा), किन्तु MBST आवश्यक रूप से MST नहीं है।<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>
@@ Line 494: / Line 495: @@
 ==अग्रिम पठन==
-* [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.)
+* [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]]'', Second Edition. MIT Press and McGraw-Hill, 2001. {{isbn|0-262-03293-7}}. Chapter 23: Minimum Spanning Trees, pp.&nbsp;561–579.
+* [[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.&nbsp;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 discussion]. Manuscript, University of Pennsylvania, April. 78 pp.
+* 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, 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).
+* 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).
@@ Line 503: / Line 504: @@
 {{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.cs.sunysb.edu/~algorith/files/minimum-spanning-tree.shtml The Stony Brook Algorithm Repository - Minimum Spanning Tree codes]
+* [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 QuickGraph for .Net]
+* [https://web.archive.org/web/20100317031339/http://www.codeplex.com/quickgraph Implemented in QuiCkGraph for .Net]
 [[Category: फैले पेड़]] [[Category: बहुपद-समय की समस्याएँ]]

Anonymous

Search

न्यूनतम स्पैनिंग ट्री (एमएसटी): Difference between revisions

Revision as of 10:47, 4 July 2023

गुण

संभावित बहुलता

अद्वितीयता

न्यूनतम-निवेश उपग्राफ

साइकिल प्रोपर्टी

प्रोपर्टी कट

न्यूनतम-निवेश बढ़त

संकुचन

एल्गोरिदम

क्लासिक एल्गोरिदम

तेज़ एल्गोरिदम

विशेष स्थितियों में रैखिक-समय एल्गोरिदम

सघन रेखांकन

पूर्णांक भार

निर्णय ट्री

इष्टतम एल्गोरिदम

समानांतर और वितरित एल्गोरिदम

यादृच्छिक भार के साथ पूर्ण ग्राफ़ पर एमएसटी

अनुप्रयोग

संबंधित समस्याएँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories