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

Revision as of 09:06, 4 July 2023

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

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

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

गुण

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

यदि वहाँ $n$ ग्राफ़ में शीर्ष, फिर प्रत्येक फैले हुए ट्री में हैं $n - 1$ किनारे.

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

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

अद्वितीयता

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

सबूत:

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

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

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

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

साइकिल संपत्ति

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

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

संपत्ति में कटौती

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

T

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

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

इस प्रकार

V - S = {C, F},

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

(S, V - S)

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

BC

,

EC

,

EF

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

S \cup {e}

एमएसटी का हिस्सा है

T

.

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

प्रमाण: यह कहना बेतुका है कि एमएसटी है $T$ जिसमें सम्मिलित नहीं है $e$ . जोड़ा जा रहा है $e$ को $T$ चक्र का उत्पादन करेगा, जो ही बार में कट को पार कर जाएगा $e$ और दूसरे किनारे पर वापस चला जाता है $e'$ . हटाया जा रहा है $e'$ हमें फैला हुआ ट्री मिलता है $T ∖{e'} \cup {e}$ की तुलना में सख्ती से कम वजन का $T$ . यह इस धारणा का खंडन करता है कि $T$ एमएसटी था.

इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम फैले हुए ट्री में समाहित होता है।

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

यदि न्यूनतम निवेश बढ़त {{mvar|e}किसी ग्राफ़ का } अद्वितीय है, तो यह किनारा किसी भी MST में सम्मिलित है।

प्रमाण: यदि $e$ को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था $e$ एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होगा।

संकुचन

यदि $T$ एमएसटी किनारों का ट्री है, तो हम अनुबंध कर सकते हैं $T$ अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर $T$ संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।^[4]

एल्गोरिदम

नीचे दिए गए सभी एल्गोरिदम में, $m$ ग्राफ़ में किनारों की संख्या है और $n$ शीर्षों की संख्या है.

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

न्यूनतम फैले हुए ट्री को खोजने के लिए पहला एल्गोरिदम 1926 में चेक वैज्ञानिक ओटाकर बोरोव्का द्वारा विकसित किया गया था (बोरोव्का का एल्गोरिदम देखें)। इसका उद्देश्य मोराविया का कुशल विद्युत कवरेज था। एल्गोरिदम चरणों के अनुक्रम में आगे बढ़ता है। प्रत्येक चरण में, जिसे बोरुव्का चरण कहा जाता है, यह जंगल की पहचान करता है $F$ ग्राफ़ में प्रत्येक शीर्ष पर न्यूनतम-वजन वाली बढ़त की घटना सम्मिलित है $G$ , फिर ग्राफ बनाता है $G1 = G \ F$ अगले चरण के इनपुट के रूप में। यहाँ $G \ F$ से प्राप्त ग्राफ़ को दर्शाता है $G$ किनारों को अंदर की ओर सिकोड़कर $F$ (#Cut संपत्ति के अनुसार, ये किनारे MST से संबंधित हैं)। प्रत्येक बोरुव्का चरण में रैखिक समय लगता है। चूँकि प्रत्येक चरण में शीर्षों की संख्या कम से कम आधी हो जाती है, बोरुव्का का एल्गोरिथ्म लेता है $O (m log n)$ समय।^[4]

दूसरा एल्गोरिथम प्राइम का एल्गोरिथम है, जिसका आविष्कार 1930 में वोजटेक जार्निक द्वारा किया गया था और 1957 में रॉबर्ट सी. प्राइम और 1959 में एडस्गर डब्ल्यू. डिज्क्स्ट्रा द्वारा फिर से खोजा गया था। मूल रूप से, यह एमएसटी को बढ़ाता है ( $T$ ) समय में किनारा। शुरू में, $T$ में मनमाना शीर्ष सम्मिलित है। प्रत्येक चरण में, $T$ को कम से कम वजन वाले किनारे के साथ संवर्धित किया गया है $(x, y)$ ऐसा है कि $x$ में है $T$ और $y$ अभी तक अंदर नहीं है $T$ . #Cut प्रॉपर्टी द्वारा, सभी किनारों को जोड़ा गया $T$ एमएसटी में हैं। इसका रन-टाइम या तो है $O (m log n)$ या $O (m + n log n)$ , प्रयुक्त डेटा-संरचनाओं पर निर्भर करता है।

आमतौर पर उपयोग में आने वाला तीसरा एल्गोरिदम क्रुस्कल का एल्गोरिदम है, जो भी लेता है $O (m log n)$ समय।

एक चौथा एल्गोरिदम, जो आमतौर पर उपयोग नहीं किया जाता है, रिवर्स-डिलीट एल्गोरिदम है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है $O(m log n (log log n) 3)$ .

ये चारों लालची एल्गोरिदम हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफपी (जटिलता) में है, और संबंधित निर्णय समस्याएं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं ( जटिलता)।

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

कई शोधकर्ताओं ने अधिक कम्प्यूटेशनल रूप से कुशल एल्गोरिदम खोजने का प्रयास किया है।

एक तुलना मॉडल में, जिसमें किनारे के वजन पर एकमात्र अनुमत संचालन जोड़ीदार तुलना है, Karger, Klein & Tarjan (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. सभी संभावित डीटी उत्पन्न करना

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

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

ऐसे क्रमपरिवर्तनों की संख्या अधिकतम है $(r 2)!$ .
प्रत्येक क्रमपरिवर्तन के लिए, किसी भी मौजूदा एल्गोरिदम का उपयोग करके दिए गए ग्राफ़ पर एमएसटी समस्या को हल करें, और परिणाम की तुलना डीटी द्वारा दिए गए उत्तर से करें।
किसी भी MST एल्गोरिदम का रनिंग टाइम अधिकतम होता है $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)}}.

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

सेठ पेटी और विजय रामचन्द्रन ने पाया है provably इष्टतम नियतात्मक तुलना-आधारित न्यूनतम स्पैनिंग ट्री एल्गोरिदम।^[4] निम्नलिखित एल्गोरिथम का सरलीकृत विवरण है।

होने देना $r = log log log n$ , कहाँ $n$ शीर्षों की संख्या है. सभी इष्टतम निर्णय ट्री खोजें $r$ शिखर. यह समय रहते किया जा सकता है $O (n)$ (ऊपर #निर्णय ट्री देखें)।
ग्राफ़ को अधिकतम घटकों में विभाजित करें $r$ प्रत्येक घटक में शीर्ष। यह विभाजन नरम ढेर का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है।
प्रत्येक घटक के भीतर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें।
एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को लागू करें जो समय में #घने ग्राफ़ पर काम करता है $O (m)$ अभ्रष्ट उपसमूह के संकुचन के लिए
परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें ताकि सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और शुरुआती ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम लागू करें।

एल्गोरिथम में सभी चरणों का रनटाइम है $O (m)$ , निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह साबित हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से बेहतर नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण हैprovably इष्टतम, हालांकि इसकी रनटाइम जटिलता अज्ञात है।

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

अनुसंधान ने न्यूनतम फैले हुए ट्री की समस्या के लिए समानांतर एल्गोरिदम पर भी विचार किया है। प्रोसेसर की रैखिक संख्या के साथ समस्या को हल करना संभव है $O (log n)$ समय।^[12]^[13] Bader & Cong (2006) एल्गोरिदम प्रदर्शित करें जो अनुकूलित अनुक्रमिक एल्गोरिदम की तुलना में 8 प्रोसेसर पर 5 गुना तेजी से एमएसटी की गणना कर सकता है।^[14] अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम फैले हुए ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी भंडारण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।^[15] लेखकों के दावों के अनुसार, यह पारंपरिक इन-मेमोरी एल्गोरिदम की तुलना में 2 से 5 गुना धीमी गति से काम कर सकता है। वे ग्राफ़ के आकार को कुशलतापूर्वक कम करने के लिए कुशल बाहरी सॉर्टिंग और ग्राफ़ संकुचन तकनीकों पर भरोसा करते हैं।

समस्या का समाधान वितरित कंप्यूटिंग में भी किया जा सकता है। यदि प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अलावा कुछ भी नहीं जानता है, तब भी कोई वितरित न्यूनतम स्पैनिंग ट्री की गणना कर सकता है।

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

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

एकसमान यादृच्छिक भार के लिए $[0,1]$ , छोटे पूर्ण ग्राफ़ के लिए न्यूनतम फैले हुए ट्री के सटीक अपेक्षित आकार की गणना की गई है।^[16]

Vertices	Expected size	Approximate expected size
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]

@@ Line 1: / Line 1: @@
 {{Short description|Least-weight tree connecting graph vertices}}
-[[File:Minimum spanning tree.svg|thumb|300px|right|एक [[समतलीय ग्राफ]] और उसका न्यूनतम फैलाव वाला वृक्ष। प्रत्येक किनारे को उसके वजन के साथ लेबल किया गया है, जो यहां लगभग उसकी लंबाई के समानुपाती है।]]एक न्यूनतम स्पैनिंग ट्री (एमएसटी) या न्यूनतम वेट स्पैनिंग ट्री [[ जुड़ा हुआ ग्राफ ]] के किनारों का उपसमूह है, किनारे-भारित अप्रत्यक्ष ग्राफ जो बिना किसी [[चक्र (ग्राफ सिद्धांत)]] के सभी वर्टेक्स (ग्राफ सिद्धांत) को साथ जोड़ता है। न्यूनतम संभव कुल बढ़त भार।<रेफ नाम = नम्पी और स्किपी दस्तावेज़ीकरण - नम्पी और स्किपी दस्तावेज़ीकरण >{{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=न्यूनतम स्पैनिंग ट्री एक ग्राफ है जिसमें किनारों का सबसेट होता है जो किनारों पर वजन के कुल योग को कम करते हुए सभी जुड़े हुए नोड्स को एक साथ जोड़ता है।}}<nowiki></ref></nowiki> अर्थात, यह फैला हुआ पेड़ है जिसके किनारे के भार का योग यथासंभव छोटा है। रेफरी नाम = नेटवर्कएक्स 2.6.2 दस्तावेज़ >{{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=एक न्यूनतम स्पैनिंग ट्री ग्राफ़ का एक सबग्राफ (एक ट्री) है जिसमें किनारे के भार का न्यूनतम योग होता है। एक फैला हुआ जंगल ग्राफ़ के प्रत्येक जुड़े घटक के लिए फैले हुए पेड़ों का एक संघ है।}}<nowiki></ref></nowiki> अधिक आम तौर पर, किसी भी किनारे-भारित अप्रत्यक्ष ग्राफ (आवश्यक रूप से जुड़ा नहीं) में न्यूनतम फैले हुए जंगल होते हैं, जो इसके जुड़े घटक (ग्राफ सिद्धांत) के लिए न्यूनतम फैले हुए पेड़ों का संघ है।
+[[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}} समान नोड्स होने के बावजूद भिन्न, कम से कम किनारा है जो का है लेकिन दूसरे का नहीं। ऐसे किनारों के बीच, चलो {{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|A}इसलिए, } में कोई चक्र नहीं है {{mvar|C}} बढ़त होनी चाहिए {{math|''e''{{sub|2}}}} वह अंदर नहीं है {{mvar|A}}.
+#<nowiki>एक ट्री के रूप में, {{mvar|A}इसलिए, } में कोई चक्र नहीं है </nowiki>{{mvar|C}} बढ़त होनी चाहिए {{math|''e''{{sub|2}}}} वह अंदर नहीं है {{mvar|A}}.
 # तब से {{math|''e''{{sub|1}}}} को इनमें से किसी से संबंधित अद्वितीय सबसे कम वजन वाले किनारे के रूप में चुना गया था {{mvar|A}} और {{mvar|B}}, का वजन {{math|''e''{{sub|2}}}} के वजन से अधिक होना चाहिए {{math|''e''{{sub|1}}}}.
-# जैसा {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} चक्र का हिस्सा हैं {{mvar|C}}, प्रतिस्थापित करना {{math|''e''{{sub|2}}}} साथ {{math|''e''{{sub|1}}}} में {{mvar|B}} इसलिए कम वजन वाला फैला हुआ पेड़ प्राप्त होता है।
+# जैसा {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} चक्र का हिस्सा हैं {{mvar|C}}, प्रतिस्थापित करना {{math|''e''{{sub|2}}}} साथ {{math|''e''{{sub|1}}}} में {{mvar|B}} इसलिए कम वजन वाला फैला हुआ ट्री प्राप्त होता है।
 # यह इस धारणा का खंडन करता है कि {{mvar|B}} एमएसटी है.
-अधिक आम तौर पर, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं तो न्यूनतम फैले पेड़ों में वजन का केवल (बहु-) सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम फैले पेड़ों के लिए समान है।<ref>{{cite web|url=https://cs.stackexchange.com/q/2204 |title=Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?|website=cs.stackexchange.com|access-date=4 April 2018}}</ref>
+अधिक सामान्यतः, यदि किनारे के वजन सभी अलग-अलग नहीं होते हैं तो न्यूनतम स्पैनिंग ट्री में वजन का केवल (बहु-) सेट अद्वितीय होना निश्चित है; यह सभी न्यूनतम स्पैनिंग ट्री के लिए समान है।<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|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}} उपट्री को पुनः जोड़ता है, इसलिए किनारा है {{mvar|f}} का {{mvar|C}} अलग-अलग उपट्री में समाप्त होता है, यानी, यह उपट्री को ट्री में फिर से जोड़ता है {{math|''T''{{sub|2}}}} से कम वजन के साथ {{math|''T''{{sub|1}}}}, क्योंकि का वजन {{mvar|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}} दिए गए ग्राफ़ का एकमात्र 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 से संबंधित है।
-प्रमाण: यह कहना बेतुका है कि एमएसटी है {{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}} एमएसटी था.
-इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम फैले हुए पेड़ में समाहित होता है।
+इसी तरह के तर्क से, यदि कट में से अधिक किनारे न्यूनतम वजन के होते हैं, तो ऐसा प्रत्येक किनारा किसी न्यूनतम फैले हुए ट्री में समाहित होता है।
-===न्यूनतम-लागत बढ़त===
+===न्यूनतम-निवेश बढ़त===
-यदि न्यूनतम लागत बढ़त {{mvar|e}किसी ग्राफ़ का } अद्वितीय है, तो यह किनारा किसी भी MST में शामिल है।
+<nowiki>यदि न्यूनतम निवेश बढ़त {{mvar|e}किसी ग्राफ़ का } अद्वितीय है, तो यह किनारा किसी भी MST में सम्मिलित है।</nowiki>
-प्रमाण: यदि {{mvar|e}} को एमएसटी में शामिल नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी लागत) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ पेड़ प्राप्त होगा।
+प्रमाण: यदि {{mvar|e}} को एमएसटी में सम्मिलित नहीं किया गया था, जोड़ने के बाद बने चक्र में किसी भी (बड़ी निवेश) किनारे को हटा दिया गया था {{mvar|e}} एमएसटी के लिए, कम वजन का फैला हुआ ट्री प्राप्त होगा।
 ===संकुचन===
-अगर {{mvar|T}} एमएसटी किनारों का पेड़ है, तो हम अनुबंध कर सकते हैं {{mvar|T}} अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर {{mvar|T}} संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।<ref name=PettieRamachandran2002/>
+यदि {{mvar|T}} एमएसटी किनारों का ट्री है, तो हम अनुबंध कर सकते हैं {{mvar|T}} अनुबंधित ग्राफ प्लस के एमएसटी को अपरिवर्तनीय बनाए रखते हुए ही शीर्ष पर {{mvar|T}} संकुचन से पहले ग्राफ़ के लिए एमएसटी देता है।<ref name=PettieRamachandran2002/>
@@ Line 56: / Line 56: @@
 === क्लासिक एल्गोरिदम ===
-न्यूनतम फैले हुए पेड़ को खोजने के लिए पहला एल्गोरिदम 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}} (#Cut संपत्ति के अनुसार, ये किनारे MST से संबंधित हैं)। प्रत्येक बोरुव्का चरण में रैखिक समय लगता है। चूँकि प्रत्येक चरण में शीर्षों की संख्या कम से कम आधी हो जाती है, बोरुव्का का एल्गोरिथ्म लेता है {{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}}. #Cut प्रॉपर्टी द्वारा, सभी किनारों को जोड़ा गया {{mvar|T}} एमएसटी में हैं। इसका रन-टाइम या तो है {{math|''O''(''m'' log ''n'')}} या {{math|''O''(''m'' + ''n'' log ''n'')}}, प्रयुक्त डेटा-संरचनाओं पर निर्भर करता है।
 आमतौर पर उपयोग में आने वाला तीसरा एल्गोरिदम क्रुस्कल का एल्गोरिदम है, जो भी लेता है {{math|''O''(''m'' log ''n'')}} समय।
@@ Line 64: / Line 64: @@
 एक चौथा एल्गोरिदम, जो आमतौर पर उपयोग नहीं किया जाता है, [[रिवर्स-डिलीट एल्गोरिदम]] है, जो क्रुस्कल के एल्गोरिदम के विपरीत है। इसका रनटाइम है {{math|O(''m'' log ''n'' (log log ''n''){{sup|3}})}}.
-ये चारों [[लालची एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे पेड़ों को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं ( जटिलता)।
+ये चारों [[लालची एल्गोरिदम]] हैं। चूंकि वे बहुपद समय में चलते हैं, ऐसे ट्री को खोजने की समस्या एफ[[पी (जटिलता)]] में है, और संबंधित [[निर्णय समस्या]]एं जैसे कि यह निर्धारित करना कि क्या कोई विशेष किनारा एमएसटी में है या यह निर्धारित करना कि न्यूनतम कुल वजन निश्चित मूल्य से अधिक है या नहीं, पी में हैं ( जटिलता)।
 === तेज़ एल्गोरिदम ===
@@ Line 137: / Line 137: @@
 क्या तुलना-आधारित एल्गोरिदम द्वारा रैखिक समय में सामान्य ग्राफ़ के लिए समस्या को निश्चित रूप से हल किया जा सकता है या नहीं यह खुला प्रश्न बना हुआ है।
-=== निर्णय वृक्ष ===
+=== निर्णय ट्री ===
-दिया गया ग्राफ {{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. सभी संभावित डीटी उत्पन्न करना
@@ Line 178: / Line 178: @@
   }}.</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}} प्रत्येक घटक में शीर्ष। यह विभाजन नरम ढेर का उपयोग करता है, जो ग्राफ़ के किनारों की छोटी संख्या को दूषित करता है।
-# प्रत्येक घटक के भीतर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय पेड़ों का उपयोग करें।
+# प्रत्येक घटक के भीतर अदूषित सबग्राफ के लिए एमएसटी खोजने के लिए इष्टतम निर्णय ट्री का उपयोग करें।
 # एमएसटी द्वारा फैलाए गए प्रत्येक जुड़े हुए घटक को शीर्ष पर अनुबंधित करें, और किसी भी एल्गोरिदम को लागू करें जो समय में #घने ग्राफ़ पर काम करता है {{math|''O''(''m'')}} अभ्रष्ट उपसमूह के संकुचन के लिए
-# परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें ताकि सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री शामिल होने की गारंटी हो, और शुरुआती ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम लागू करें।
+# परिणामी फ़ॉरेस्ट में दूषित किनारों को वापस जोड़ें ताकि सबग्राफ़ बनाया जा सके जिसमें न्यूनतम स्पैनिंग ट्री सम्मिलित होने की गारंटी हो, और शुरुआती ग्राफ़ की तुलना में स्थिर कारक से छोटा हो। इस ग्राफ़ पर पुनरावर्ती रूप से इष्टतम एल्गोरिदम लागू करें।
-एल्गोरिथम में सभी चरणों का रनटाइम है {{math|''O''(''m'')}}, निर्णय वृक्षों का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, लेकिन यह साबित हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय वृक्ष से बेहतर नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है{{not a typo|provably}} इष्टतम, हालांकि इसकी रनटाइम जटिलता अज्ञात है।
+एल्गोरिथम में सभी चरणों का रनटाइम है {{math|''O''(''m'')}}, निर्णय ट्री का उपयोग करने के चरण को छोड़कर। इस चरण का रनटाइम अज्ञात है, किन्तु यह साबित हो चुका है कि यह इष्टतम है - कोई भी एल्गोरिदम इष्टतम निर्णय ट्री से बेहतर नहीं कर सकता है। इस प्रकार, इस एल्गोरिथम में विशिष्ट गुण है{{not a typo|provably}} इष्टतम, हालांकि इसकी रनटाइम जटिलता अज्ञात है।
 === समानांतर और वितरित एल्गोरिदम ===
 {{further|Parallel algorithms for minimum spanning trees}}
-अनुसंधान ने न्यूनतम फैले हुए पेड़ की समस्या के लिए [[समानांतर एल्गोरिदम]] पर भी विचार किया है।
+अनुसंधान ने न्यूनतम फैले हुए ट्री की समस्या के लिए [[समानांतर एल्गोरिदम]] पर भी विचार किया है।
 प्रोसेसर की रैखिक संख्या के साथ समस्या को हल करना संभव है {{math|''O''(log ''n'')}} समय।<ref>{{citation
   | last1 = Chong | first1 = Ka Wong
@@ Line 223: / Line 223: @@
   | volume = 66
   | year = 2006| s2cid = 2004627 }}.</ref>
-अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम फैले हुए पेड़ों की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी भंडारण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।<ref>{{citation
+अन्य विशिष्ट एल्गोरिदम इतने बड़े ग्राफ़ के न्यूनतम फैले हुए ट्री की गणना करने के लिए डिज़ाइन किए गए हैं कि उनमें से अधिकांश को हर समय डिस्क पर संग्रहीत किया जाना चाहिए। ये बाहरी भंडारण एल्गोरिदम, उदाहरण के लिए, जैसा कि रोमन, डिमेंटिव एट अल द्वारा इंजीनियरिंग ए एक्सटर्नल मेमोरी मिनिमम स्पैनिंग ट्री एल्गोरिदम में वर्णित है।<ref>{{citation
   | last1 = Dementiev | first1 = Roman
   | last2 = Sanders | first2 = Peter
@@ Line 239: / Line 239: @@
 एलन एम. फ़्रीज़ ने दिखाया कि n शीर्षों पर [[पूरा ग्राफ]]़ दिया गया है, किनारे के वजन के साथ जो वितरण फ़ंक्शन के साथ स्वतंत्र समान रूप से वितरित यादृच्छिक चर हैं <math>F</math> संतुष्टि देने वाला <math>F'(0) > 0</math>, फिर जैसे-जैसे n विस्तारित वास्तविक संख्या रेखा के करीब पहुंचता है|+∞ MST का अपेक्षित वजन करीब आता है <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 291: / Line 291: @@
 ==अनुप्रयोग==
-न्यूनतम फैले पेड़ों का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें [[ संगणक संजाल ]], [[दूरसंचार नेटवर्क]], परिवहन नेटवर्क, [[जल आपूर्ति नेटवर्क]] और [[विद्युत ग्रिड]] शामिल हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।<ref>{{citation
+न्यूनतम स्पैनिंग ट्री का नेटवर्क के डिज़ाइन में प्रत्यक्ष अनुप्रयोग होता है, जिसमें [[ संगणक संजाल ]], [[दूरसंचार नेटवर्क]], परिवहन नेटवर्क, [[जल आपूर्ति नेटवर्क]] और [[विद्युत ग्रिड]] सम्मिलित हैं (जैसा कि ऊपर बताया गया है, जिसके लिए उनका पहली बार आविष्कार किया गया था)।<ref>{{citation
   | last1 = Graham | first1 = R. L. | author1-link = Ronald Graham
   | last2 = Hell | first2 = Pavol | author2-link = Pavol Hell
@@ Line 301: / Line 301: @@
   | 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 329: / Line 329: @@
   |archive-date  = 24 August 2004
 }}</ref>
-और न्यूनतम-लागत भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाना।<ref>{{cite conference
+और न्यूनतम-निवेश भारित पूर्ण मिलान (ग्राफ़ सिद्धांत) का अनुमान लगाना।<ref>{{cite conference
 | url = http://dl.acm.org/citation.cfm?id=804689
 | title = Heuristics for weighted perfect matching
@@ Line 345: / Line 345: @@
 | 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 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>
@@ Line 358: / Line 358: @@
 * द्वि-आयामी सामग्रियों की एकरूपता को मापना।<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-MST), जो कि वह पेड़ है जो न्यूनतम वजन के साथ ग्राफ में 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 395: / Line 395: @@
   }}.</ref> (ध्यान दें कि यह समस्या k-न्यूनतम स्पैनिंग ट्री से असंबंधित है।)
-[[ यूक्लिडियन न्यूनतम फैलाव वाला पेड़ ]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारों का भार शीर्षों के बीच यूक्लिडियन दूरी के अनुरूप होता है, जो समतल (या स्थान) में बिंदु होते हैं।
+[[ यूक्लिडियन न्यूनतम फैलाव वाला पेड़ | यूक्लिडियन न्यूनतम स्पैनिंग ट्री]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारों का भार शीर्षों के बीच यूक्लिडियन दूरी के अनुरूप होता है, जो समतल (या स्थान) में बिंदु होते हैं।
-[[ सरलरेखीय न्यूनतम फैलाव वाला वृक्ष ]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं।
+[[ सरलरेखीय न्यूनतम फैलाव वाला वृक्ष | सरलरेखीय न्यूनतम स्पैनिंग ट्री]] ग्राफ का स्पैनिंग ट्री है, जिसके किनारे का वजन शीर्षों के बीच रेक्टिलिनियर दूरी के अनुरूप होता है, जो कि समतल (या स्थान) में बिंदु होते हैं।
-वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अलावा कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है लेकिन समाधान के लिए अलग-अलग दृष्टिकोण हैं।
+वितरित कंप्यूटिंग में, जहां प्रत्येक नोड को कंप्यूटर माना जाता है और कोई भी नोड अपने स्वयं के जुड़े लिंक के अलावा कुछ भी नहीं जानता है, कोई वितरित न्यूनतम स्पैनिंग ट्री पर विचार कर सकता है। समस्या की गणितीय परिभाषा ही है किन्तु समाधान के लिए अलग-अलग दृष्टिकोण हैं।
-[[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष]] ऐसा पेड़ है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपवृक्ष में एसी नोड्स से अधिक नहीं होता है। c को वृक्ष क्षमता कहा जाता है। सीएमएसटी को इष्टतम ढंग से हल करना [[ एनपी कठिन ]] है,<ref>{{citation
+[[क्षमतायुक्त न्यूनतम फैलाव वाला वृक्ष|क्षमतायुक्त न्यूनतम स्पैनिंग ट्री]] ऐसा ट्री है जिसमें चिह्नित नोड (मूल, या जड़) होता है और नोड से जुड़े प्रत्येक उपट्री में एसी नोड्स से अधिक नहीं होता है। c को ट्री क्षमता कहा जाता है। सीएमएसटी को इष्टतम ढंग से हल करना [[ एनपी कठिन ]] है,<ref>{{citation
   | last1 = Jothi | first1 = Raja
   | last2 = Raghavachari | first2 = Balaji
@@ Line 412: / Line 412: @@
   | doi=10.1145/1103963.1103967
 | s2cid = 8302085
-  }}</ref> लेकिन एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के करीब समाधान उत्पन्न करते हैं।
+  }}</ref> किन्तु एसाउ-विलियम्स और शर्मा जैसे अच्छे अनुमान बहुपद समय में इष्टतम के करीब समाधान उत्पन्न करते हैं।
 डिग्री-बाधित स्पैनिंग ट्री न्यूनतम स्पैनिंग ट्री है जिसमें प्रत्येक शीर्ष किसी दी गई संख्या 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 431: @@
   | 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 476: / Line 476: @@
   | doi=10.1016/0022-0000(78)90022-3| doi-access = free
   }}.</ref>
-न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को ढूंढना है यदि ग्राफ़ में प्रत्येक किनारा वजन के बजाय परिमित लेबल सेट से लेबल से जुड़ा हुआ है।<ref>{{citation
+न्यूनतम लेबलिंग स्पैनिंग ट्री समस्या कम से कम प्रकार के लेबल वाले स्पैनिंग ट्री को ढूंढना है यदि ग्राफ़ में प्रत्येक किनारा वजन के बजाय परिमित लेबल सेट से लेबल से संयोजित है।<ref>{{citation
   | last1 = Chang | first1 = R.S.
   | last2 = Leu | first2 = S.J.
@@ Line 486: / Line 486: @@
   | year = 1997
   | doi=10.1016/s0020-0190(97)00127-0}}.</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>
+टोंटी किनारा फैले हुए ट्री में सबसे अधिक भार वाला किनारा होता है। स्पैनिंग ट्री न्यूनतम टोंटी स्पैनिंग ट्री (या एमबीएसटी) है यदि ग्राफ़ में छोटे टोंटी किनारे के वजन वाला स्पैनिंग ट्री नहीं है। एमएसटी आवश्यक रूप से एमबीएसटी है ({{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>

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 09:06, 4 July 2023

Contents

गुण

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

अद्वितीयता

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

साइकिल संपत्ति

संपत्ति में कटौती

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

संकुचन

एल्गोरिदम

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

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

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

सघन रेखांकन

पूर्णांक भार

निर्णय ट्री

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

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

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

अनुप्रयोग

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

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 09:06, 4 July 2023

गुण

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

अद्वितीयता

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

साइकिल संपत्ति

संपत्ति में कटौती

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

संकुचन

एल्गोरिदम

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

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

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

सघन रेखांकन

पूर्णांक भार

निर्णय ट्री

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

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

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

अनुप्रयोग

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

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories