Expected linear time MST algorithm
अपेक्षित रैखिक समय एम. एस. टी. एल्गोरिथ्म एक यादृच्छिक एल्गोरिथ्म है जो बिना किसी पृथक शीर्ष के भारित ग्राफ के न्यूनतम फैले वन की गणना करने के लिए है। इसे डेविड कार्गर, फिलिप क्लेन और रॉबर्ट टार्जन द्वारा विकसित किया गया था। एल्गोरिथ्म रैखिक समय में न्यूनतम फैले हुए पेड़ को सत्यापित करने के लिए एक एल्गोरिथ्म के साथ बोरुवका के एल्गोरिथ्म की तकनीकों पर निर्भर करता है। यह अपेक्षित रैखिक प्रदर्शन प्राप्त करने के लिए विभाजन और विजय एल्गोरिदम, लालची एल्गोरिदम और यादृच्छिक एल्गोरिदम के डिजाइन प्रतिमानों को जोड़ती है। न्यूनतम फैलाव वृक्ष का पता लगाने वाले निर्धारक एल्गोरिदम में प्राइम का एल्गोरिदम, क्रुस्कल का एल्गोरिदम, रिवर्स-डिलीट एल्गोरिदम और बोरुवका का एल्गोरिदम शामिल हैं। अवलोकन एल्गोरिथम के लिए प्रमुख अंतर्दृष्टि एक यादृच्छिक नमूना चरण है जो प्रत्येक उपग्राफ में शामिल करने के लिए किनारों का यादृच्छिक रूप से चयन करके एक ग्राफ को दो उपग्राफ में विभाजित करता है। एल्गोरिथ्म पुनरावर्ती रूप से पहली उप-समस्या के न्यूनतम फैले हुए वन का पता लगाता है और ग्राफ में किनारों को छोड़ने के लिए एक रैखिक समय सत्यापन एल्गोरिथ्म के साथ संयोजन में समाधान का उपयोग करता है जो न्यूनतम फैले हुए पेड़ में नहीं हो सकते हैं। प्रत्येक पुनरावृत्ति पर ग्राफ के आकार को कम करने के लिए बोरुवका के एल्गोरिथ्म से ली गई एक प्रक्रिया का भी उपयोग किया जाता है। बोरुवका चरण एल्गोरिदम की प्रत्येक पुनरावृत्ति बोरुवका के एल्गोरिदम के अनुकूलन पर निर्भर करती है जिसे बोरुवका चरण के रूप में संदर्भित किया जाता हैः इनपुटः एक ग्राफ जी जिसमें कोई पृथक शीर्ष नहीं है 1 प्रत्येक शीर्ष के लिए, वी 2 पर सबसे हल्के किनारे की घटना का चयन करें 'एक अनुबंधित ग्राफ जी' बनाएँ 'चरण 1 में चयनित किनारों से जुड़े जी के प्रत्येक घटक को एक एकल शीर्ष के साथ बदलकर 3 जी आउटपुट से सभी पृथक शीर्ष, स्व-लूप और गैर-न्यूनतम दोहराव वाले किनारों को हटाएंः चरण 1 में चुने गए किनारे और अनुबंधित ग्राफ जी ए बोरुवका चरण बोरुवका के एल्गोरिदम के आंतरिक लूप के बराबर है, जो ओ (एम) समय में चलता है जहां एम है। इस प्रकार, एक बोरुवका चरण ग्राफ में शीर्षों की संख्या को कम से कम दो के कारक से कम कर देता है और कम से कम n/2 किनारों को हटा देता है जहां n, G में शीर्षों की संख्या है। इन्हें एफ-भारी किनारे कहा जाता है और इन्हें निम्नानुसार परिभाषित किया गया है। मान लीजिए कि ग्राफ एच पर एफ एक वन है। एक एफ-भारी किनारा एक किनारा है जो शीर्षों को जोड़ता है, जिसका वजन एफ में यू से वी तक के मार्ग पर सबसे भारी किनारे के वजन से सख्ती से अधिक है। (यदि एफ में कोई पथ मौजूद नहीं है तो इसे अनंत वजन माना जाता है)। कोई भी किनारा जो एफ-भारी नहीं है, वह एफ-लाइट है। यदि एफ जी का उपलेख है तो जी में कोई भी एफ-भारी किनारा चक्र गुण द्वारा जी के न्यूनतम फैले हुए पेड़ में नहीं हो सकता है। वन को देखते हुए, एफ-भारी किनारों की गणना न्यूनतम फैले हुए वृक्ष सत्यापन एल्गोरिदम का उपयोग करके रैखिक समय में की जा सकती है। एल्गोरिदम इनपुटः एक ग्राफ जी जिसमें कोई पृथक शीर्ष नहीं है यदि जी खाली है तो एक खाली वन लौटें जी पर दो क्रमिक बोरुवका चरणों को चलाकर एक अनुबंधित ग्राफ जी बनाएँ संभावना 1/2 के साथ जी में प्रत्येक किनारे का चयन करके एक उपग्राफ एच बनाएँ। अपने न्यूनतम फैले वन एफ को प्राप्त करने के लिए बार-बार एल्गोरिथ्म को एच पर लागू करें. एक रैखिक समय न्यूनतम फैले वृक्ष सत्यापन एल्गोरिथ्म का उपयोग करके जी (जहां एफ चरण 3 से वन है) से सभी एफ-भारी किनारों को हटा दें। न्यूनतम फैले वन को प्राप्त करने के लिए जी के लिए एल्गोरिथ्म को बार-बार लागू करें। आउटपुटः ग्राफ में शीर्षों की संख्या पर प्रेरण द्वारा जी का न्यूनतम फैला हुआ वन और बोरुवका चरणों से सिकुड़े हुए किनारों की शुद्धता साबित होती है। आधार मामला मामूली रूप से सच है। टी * को जी का न्यूनतम फैला हुआ वृक्ष होने दें। बोरुव्का चरण में चुना गया प्रत्येक किनारा कट गुण द्वारा टी * में होता है और अनुबंधित ग्राफ बनाने के लिए हटाए गए किनारों में से कोई भी कट गुण (अनावश्यक किनारों के लिए) और चक्र गुण (स्व लूप के लिए) द्वारा टी * में नहीं होता है। टी * के शेष किनारे जो चरण 2 में नहीं चुने गए हैं, वे कट गुण द्वारा अनुबंधित ग्राफ के न्यूनतम फैले हुए पेड़ का निर्माण करते हैं (प्रत्येक कट को एक सुपरनोड होने दें)। हटा दिया गया प्रत्येक एफ-भारी किनारा साइकिल गुण द्वारा न्यूनतम फैले हुए पेड़ में नहीं है। अंत में एफ 'प्रेरक परिकल्पना द्वारा अनुबंधित ग्राफ का न्यूनतम फैलाव वृक्ष है। इस प्रकार एफ 'और बोरुवका सीढ़ियों से सिकुड़े किनारों से न्यूनतम फैला हुआ पेड़ बनता है। प्रदर्शन अपेक्षित प्रदर्शन यादृच्छिक नमूना चरण का परिणाम है। यादृच्छिक नमूनाकरण चरण की प्रभावशीलता को निम्नलिखित सूत्र द्वारा वर्णित किया गया है जो जी में एफ-प्रकाश किनारों की संख्या पर एक सीमा रखता है जिससे दूसरी उप-समस्या का आकार सीमित हो जाता है। यादृच्छिक नमूना लेम्मा-मान लीजिए कि H, G के प्रत्येक किनारे को स्वतंत्र रूप से संभाव्यता p के साथ शामिल करके बनाया गया G का एक उपलेख है और मान लीजिए कि F, H का न्यूनतम फैला हुआ वन है। G में F-प्रकाश किनारों की अपेक्षित संख्या अधिकतम n/p है जहां n, G में शीर्षों की संख्या है। लेम्मा को साबित करने के लिए G के किनारों की जांच करें क्योंकि उन्हें H में जोड़ा जा रहा है। G में F-प्रकाश किनारों की संख्या उस क्रम से स्वतंत्र है जिसमें H के किनारों का चयन किया जाता है क्योंकि सभी चयन आदेशों के लिए H का न्यूनतम फैला हुआ वन समान है। प्रमाण के लिए एच के लिए किनारों का चयन करने पर विचार करें, एक समय में जी के किनारों को किनारे के वजन के क्रम में सबसे हल्के से लेकर सबसे भारी तक लें। माना जा रहा है कि ई वर्तमान किनारा है। यदि ई के अंतिम बिंदु एच के दो असंबद्ध घटकों में हैं तो ई उन घटकों को जोड़ने वाला सबसे हल्का किनारा है और यदि इसे एच में जोड़ा जाता है तो यह कट गुण द्वारा एफ में होगा। इसका मतलब यह भी है कि ई एफ-लाइट है, भले ही इसे एच में जोड़ा जाए या नहीं, क्योंकि बाद में केवल भारी किनारों पर विचार किया जाता है। यदि ई के दोनों अंतिम बिंदु एच के एक ही घटक में हैं तो यह चक्र गुण द्वारा एफ-भारी है (और हमेशा होगा)। इसके बाद किनारे ई को संभावना पी के साथ एच में जोड़ा जाता है। एच में जोड़े गए एफ-प्रकाश किनारों की अधिकतम संख्या एन-1 है क्योंकि एच के किसी भी न्यूनतम फैले हुए पेड़ में एन-1 किनारे होते हैं। एक बार जब एन-1 एफ-प्रकाश किनारों को एच में जोड़ा जाता है, तो बाद के किनारों में से कोई भी चक्र गुण द्वारा एफ-प्रकाश नहीं माना जाता है। इस प्रकार, जी में एफ-प्रकाश किनारों की संख्या एच के लिए विचार किए गए एफ-प्रकाश किनारों की संख्या से घिरी हुई है, इससे पहले कि एन-1 एफ-प्रकाश किनारों को वास्तव में एच में जोड़ा जाता है। चूंकि किसी भी एफ-प्रकाश किनारे को संभावना पी के साथ जोड़ा जाता है, यह एक सिक्के को पलटने के बराबर है जिसमें आने वाले सिर की संभावना पी के साथ जब तक कि एन-1 सिर दिखाई नहीं देते। सिक्का पलटने की कुल संख्या जी में एफ-प्रकाश किनारों की संख्या के बराबर होती है। सिक्का पलटने की संख्या का वितरण एन-1 और पी मापदंडों के साथ व्युत्क्रम द्विपद वितरण द्वारा दिया जाता है। इन मापदंडों के लिए इस वितरण का अपेक्षित मूल्य (एन-1)/पी है। प्रत्याशित विश्लेषण पुनरावर्ती उप-समस्याओं में किए गए कार्य को नजरअंदाज करते हुए एल्गोरिथ्म के एकल आह्वान में किए गए कार्य की कुल मात्रा इनपुट ग्राफ में किनारों की संख्या में रैखिक होती है। चरण 1 में लगातार समय लगता है। बोरुवका चरणों को समय रैखिक में किनारों की संख्या में निष्पादित किया जा सकता है जैसा कि बोरुवका चरण खंड में उल्लेख किया गया है। चरण 3 किनारों के माध्यम से दोहराता है और प्रत्येक के लिए एक ही सिक्का फ़्लिप करता है ताकि यह किनारों की संख्या में रैखिक हो। चरण 4 को एक संशोधित रैखिक समय न्यूनतम वृक्ष सत्यापन एल्गोरिदम का उपयोग करके रैखिक समय में निष्पादित किया जा सकता है। चूँकि एल्गोरिथ्म के एक पुनरावृत्ति में किया गया कार्य किनारों की संख्या में रैखिक होता है, इसलिए एल्गोरिथ्म के एक पूर्ण रन (सभी पुनरावर्ती कॉल सहित) में किया गया कार्य एक स्थिर कारक गुणा मूल समस्या में किनारों की कुल संख्या और सभी पुनरावर्ती उप-समस्याओं से घिरा होता है। एल्गोरिथम के प्रत्येक आह्वान से अधिकतम दो उप-समस्याएं उत्पन्न होती हैं, इसलिए उप-समस्याओं का समूह एक द्विआधारी वृक्ष बनाता है। प्रत्येक बोरुवका चरण शीर्षों की संख्या को कम से कम दो के कारक से कम कर देता है इसलिए दो बोरुवका चरणों के बाद शीर्षों की संख्या को चार के कारक से कम कर दिया गया है। इस प्रकार, यदि मूल ग्राफ में n शीर्ष और m किनारे हैं तो पेड़ की गहराई d पर प्रत्येक उप-समस्या अधिकतम n/4d शीर्षों के ग्राफ पर है। इसके अलावा पेड़ में अधिकांश लॉग4एन स्तर होते हैं। रिकर्शन ट्री के बारे में तर्क करने के लिए चरण 3 में रिकर्सिव कॉल में बाएं बच्चे की समस्या को उप-समस्या होने दें और चरण 5 में रिकर्सिव कॉल में सही बच्चे की समस्या को उप-समस्या होने दें। मूल समस्या में किनारों की कुल संख्या और पेड़ के प्रत्येक बाएं रास्ते में किनारों की संख्या गिनकर सभी उप-समस्याओं की गणना करें। बाएँ पथ या तो दाएँ बच्चे या जड़ से शुरू होता है और इसमें बाएँ बच्चों के पथ के माध्यम से पहुँचने योग्य सभी नोड्स शामिल होते हैं। द्विआधारी वृक्ष के बाएँ रास्ते दाईं ओर आरेख में नीले रंग में वृत्ताकार दिखाए गए हैं। बाएँ बच्चे की समस्या में प्रत्येक किनारे को इसकी मूल समस्या के किनारों से चुना जाता है (बोरुवका चरणों में संकुचित किनारों को कम करते हुए) संभावना 1/2 के साथ। यदि किसी मूल समस्या में x किनारे हैं तो बाएं बच्चे की समस्या में किनारों की अपेक्षित संख्या अधिकतम x/2 है। यदि x को एक यादृच्छिक चर X द्वारा प्रतिस्थापित किया जाता है तो अपेक्षा की रैखिकता द्वारा बाएं बाल समस्या Y में किनारों की अपेक्षित संख्या द्वारा दी जाती है। इस प्रकार यदि बाएं पथ के शीर्ष पर किसी समस्या में किनारों की अपेक्षित संख्या k है तो बाएं पथ में प्रत्येक उप-समस्या में किनारों की अपेक्षित संख्या का योग अधिक से अधिक है (ज्यामितीय श्रृंखला देखें)। जड़ में एम किनारे होते हैं इसलिए किनारों की अपेक्षित संख्या 2 मीटर के बराबर होती है और प्रत्येक सही उप-समस्या में किनारों की अपेक्षित संख्या से दोगुनी होती है। प्रत्येक दाहिनी उप-समस्या में किनारों की अपेक्षित संख्या मूल समस्या में एफ-प्रकाश किनारों की संख्या के बराबर होती है जहां एफ बाईं उप-समस्या का न्यूनतम फैलाव वृक्ष है। एफ-प्रकाश किनारों की संख्या नमूना लेम्मा द्वारा उप-समस्या में शीर्षों की संख्या से कम या दोगुनी के बराबर होती है। गहराई d पर एक उप-समस्या में शीर्षों की संख्या n/4d है इसलिए सभी सही उप-समस्याओं में शीर्षों की कुल संख्या इसके द्वारा दी जाती है। इस प्रकार, मूल समस्या और सभी उप-समस्याओं में किनारों की अपेक्षित संख्या अधिकतम 2m + n है। चूंकि किसी अलग-थलग शीर्ष वाले ग्राफ के लिए n अधिकतम 2m है, इसलिए एल्गोरिथ्म अपेक्षित समय O (m) में चलता है। सबसे खराब केस विश्लेषण सबसे खराब केस रनटाइम बोरुवका के एल्गोरिदम के रनटाइम के बराबर है। यह तब होता है जब सभी किनारों को प्रत्येक आह्वान पर बाएं या दाएं उप-समस्या में जोड़ा जाता है। इस मामले में एल्गोरिथ्म बोरुवका के एल्गोरिथ्म के समान है जो n शीर्ष और m किनारों के साथ एक ग्राफ पर O (न्यूनतम {n2, mlogn}) में चलता है। संदर्भ आगे पढ़ने के लिए न्यूनतम फैलाव वृक्ष रैखिक समय यादृच्छिक एल्गोरिदम में वृक्ष फैलाव में सत्यापन