न्यूनतम स्पैनिंग ट्री
एक न्यूनतम स्पैनिंग ट्री एक भारित, संयोजित ग्राफ के सभी शीर्षों को सबसे कम संभव कुल किनारे के भार के साथ जोड़ता है; क्रुस्कल और प्रिम जैसे ग्रीडी एल्गोरिदम इसे कुशलता से गणना करते हैं।
Definition
एक संयोजित, एज-भारित ग्राफ का न्यूनतम स्पैनिंग ट्री किनारों का एक उपसमूह है जो सभी शीर्षों को जोड़ता है, जिसमें कोई साइकिल नहीं होती है, और ऐसे सभी स्पैनिंग ट्री में न्यूनतम कुल भार होता है।
Scope
यह विषय न्यूनतम-स्पैनिंग-ट्री समस्या और इसके क्लासिक ग्रीडी समाधानों को शामिल करता है — क्रुस्कल का एल्गोरिदम, जो एक डिसजॉइंट-सेट संरचना का उपयोग करके बढ़ते भार क्रम में किनारों को जोड़ता है, और प्रिम का एल्गोरिदम, जो एक प्रायोरिटी क्यू का उपयोग करके एक एकल ट्री को बढ़ाता है — साथ ही कट और साइकिल गुण जो इन एल्गोरिदम की शुद्धता को सिद्ध करते हैं। यह सहायक डिसजॉइंट-सेट (यूनियन-फाइंड) डेटा संरचना पर भी प्रकाश डालता है।
Core questions
- स्पैनिंग ट्री क्या है, और न्यूनतम भार वाला स्पैनिंग ट्री क्या बनाता है?
- ग्रीडी एज जोड़ वैश्विक रूप से न्यूनतम स्पैनिंग ट्री क्यों उत्पन्न करते हैं?
- कट प्रॉपर्टी और साइकिल प्रॉपर्टी MST एल्गोरिदम को कैसे सही ठहराते हैं?
- क्रुस्कल और प्रिम के एल्गोरिदम रणनीति और डेटा संरचनाओं में कैसे भिन्न हैं?
- डिसजॉइंट-सेट (यूनियन-फाइंड) संरचना क्रुस्कल के एल्गोरिदम को कुशल कैसे बनाती है?
Key concepts
- स्पैनिंग ट्री
- कट प्रॉपर्टी
- साइकिल प्रॉपर्टी
- क्रुस्कल का एल्गोरिदम
- प्रिम का एल्गोरिदम
- डिसजॉइंट-सेट (यूनियन-फाइंड)
- ग्रीडी सेफ एज
- एज वेट्स
Key theories
- कट प्रॉपर्टी
- शीर्षों के किसी भी विभाजन के लिए दो सेटों में, विभाजन को पार करने वाला न्यूनतम-भार वाला किनारा किसी न्यूनतम स्पैनिंग ट्री से संबंधित होता है; यह सेफ-एज गारंटी क्रुस्कल और प्रिम दोनों के ग्रीडी एल्गोरिदम के लिए शुद्धता का आधार है।
- डिसजॉइंट-सेट यूनियन-फाइंड सपोर्ट
- क्रुस्कल का एल्गोरिदम रैंक द्वारा यूनियन और पाथ कम्प्रेशन के साथ एक यूनियन-फाइंड संरचना का उपयोग करता है ताकि लगभग स्थिर अमोर्टाइज्ड समय में यह परीक्षण किया जा सके कि क्या एक किनारा जोड़ने से एक साइकिल बनेगी।
Clinical relevance
न्यूनतम स्पैनिंग ट्री सबसे कम लागत वाले नेटवर्क डिज़ाइन का मॉडल बनाते हैं: संचार, विद्युत, या परिवहन नेटवर्क बिछाना जो सभी साइटों को सस्ते में जोड़ते हैं। वे क्लस्टरिंग, इमेज सेगमेंटेशन, ट्रैवलिंग सेल्समैन समस्या के लिए सन्निकटन एल्गोरिदम और बिंदु सेटों के विश्लेषण में भी बिल्डिंग ब्लॉक के रूप में कार्य करते हैं।
History
न्यूनतम-स्पैनिंग-ट्री समस्या को सबसे पहले ओटाकर बोरुव्का ने 1926 में विद्युत-नेटवर्क डिज़ाइन के लिए हल किया था। वोज्तेच जार्निक (1930) और बाद में प्रिम (1957) और डिज्क्स्ट्रा ने ट्री-ग्रोइंग दृष्टिकोण विकसित किया, जबकि क्रुस्कल (1956) ने एज-सॉर्टिंग ग्रीडी विधि दी, जिससे यह सबसे शुरुआती अच्छी तरह से समझी जाने वाली कॉम्बिनेटरियल ऑप्टिमाइजेशन समस्याओं में से एक बन गई।
Key figures
- Joseph Kruskal
- Robert Prim
- Otakar Borůvka
- Vojtěch Jarník
Related topics
Seminal works
- kruskal1956
- cormen2009
Frequently asked questions
- क्रुस्कल और प्रिम के एल्गोरिदम में क्या अंतर है?
- क्रुस्कल का एल्गोरिदम सभी किनारों को सॉर्ट करता है और उन्हें बढ़ते भार क्रम में जोड़ता है, किसी भी ऐसे किनारे को छोड़ देता है जो एक साइकिल बनाएगा, साइकिल का पता लगाने के लिए यूनियन-फाइंड का उपयोग करता है। प्रिम का एल्गोरिदम एक प्रारंभिक शीर्ष से एक एकल संयोजित ट्री को बढ़ाता है, वर्तमान ट्री से निकलने वाले सबसे सस्ते किनारे को बार-बार जोड़ता है, एक प्रायोरिटी क्यू का उपयोग करता है। दोनों एक न्यूनतम स्पैनिंग ट्री उत्पन्न करते हैं।
- क्या न्यूनतम स्पैनिंग ट्री अद्वितीय है?
- यदि सभी किनारे के भार अलग-अलग हैं, तो न्यूनतम स्पैनिंग ट्री अद्वितीय होता है। जब कुछ भार समान होते हैं, तो कई अलग-अलग न्यूनतम स्पैनिंग ट्री हो सकते हैं, सभी का कुल भार समान न्यूनतम होता है।