Kruskal एल्गोरिथ्म - एक इष्टतम ढांचे के निर्माण

19 वीं सदी ज्यामितिशास्त्रीय में बर्लिन से जेकब स्टेनर कैसे तीन गांवों कनेक्ट करने के लिए इतना है कि उनकी लंबाई कम से कम था का कार्य निर्धारित किया है। बाद में, वह समस्या संक्षेप: यह एक विमान में एक बिंदु को खोजने के लिए आवश्यक है, एन अन्य बिंदुओं के लिए इसे से दूरी सबसे कम थे। 20 वीं सदी में, यह इस विषय पर काम करने के लिए जारी है। यह कुछ ही अंक लेते हैं और उन्हें इस तरह से कि उनके बीच की दूरी कम से कम था में कनेक्ट करने के लिए निर्णय लिया गया। यह सब समस्या का एक विशेष मामला अध्ययन किया जा रहा है।

"लालची" एल्गोरिथ्म

Kruskal एल्गोरिथ्म "लालची" एल्गोरिथ्म (भी बुलाया ढाल) को दर्शाता है। उन का सार - हर कदम पर सर्वोच्च जीत। हमेशा नहीं, "लालची" एल्गोरिदम समस्या का सबसे अच्छा समाधान प्रदान करते हैं। एक सिद्धांत दिखा रहा है कि विशिष्ट कार्यों के लिए अपने आवेदन में वे इष्टतम समाधान देने के लिए, नहीं है। यह matroids का सिद्धांत है। Kruskal एल्गोरिथ्म इस तरह की समस्याओं को दर्शाता है।

एक न्यूनतम शव वजन ढूँढना

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

विवरण

Kruskal एल्गोरिथ्म काम करता है। सबसे पहले, प्रारंभिक ग्राफ के सभी किनारे वजन के आरोही क्रम में व्यवस्थित कर रहे हैं। प्रारंभ में, फ्रेम किसी भी पसलियों शामिल नहीं है लेकिन सभी कोने भी शामिल है। शव है, जो एक फैले जंगल है की पहले से ही निर्माण किया हिस्से के लिए एल्गोरिथ्म के अगले कदम के बाद, एक किनारे जोड़ा जाता है। यह मनमाने ढंग से नहीं चुना है। ग्राफ के सभी किनारे, फ्रेम से संबंधित नहीं, लाल और हरे रंग कहा जा सकता है। प्रत्येक लाल किनारों के शीर्ष निर्माण वन कनेक्टिविटी के तहत एक ही घटक में हैं, और हरे रंग सबसे ऊपर - अलग। इसलिए, यदि आप लाल किनारे को जोड़ने के लिए, वहाँ एक चक्र है, और अगर हरी - के रूप में इस कदम के बाद प्राप्त लकड़ी जुड़े घटकों एक से कम हो जाएगा। इस प्रकार, जिसके परिणामस्वरूप निर्माण कोई लाल बढ़त नहीं जोड़ सकते हैं, लेकिन किसी भी हरे किनारे जंगल प्राप्त करने के लिए जोड़ा जा सकता है। और कम से कम वजन के साथ एक हरे रंग की बढ़त कहते हैं। परिणाम कम से कम वजन की एक रूपरेखा है।

कार्यान्वयन

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

1. एन-वें आरोही वजन करने के लिए 1 से ग्राफ के सभी किनारे व्यवस्थित करें। (ऐ, द्वि - मैं सुप्रीम बढ़त संख्या के साथ)।

2. के लिए मैं = 1 एन से करते हैं।

3. एक्स: = भाग (AI)।

4. y: = भाग (बीआई)।

5. एक्स बराबर y तो यूनाईटेड (एक्स, वाई) नहीं है, तो बढ़त एफ मैं संख्या के साथ शामिल करने के लिए।

यथार्थता

चलो टी - अपनी मनमानी फ्रेम - मूल ग्राफ के फ्रेम Kruskal एल्गोरिथ्म और एस का प्रयोग कर बनाया। हम साबित होता है कि डब्ल्यू (टी) डब्ल्यू (एस) से अधिक नहीं है।

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

Kruskal एल्गोरिथ्म की मजबूती matroids पर Rado-एडमंड्स की प्रमेय से इस प्रकार है।

आवेदन उदाहरण Kruskal एल्गोरिथ्म

नोड्स ए, बी, सी, डी, ई और पसलियों (क, ख), (ए, ई), (ख, ग), (ख, ई) के साथ दान ग्राफ, (ग, घ), (ग, ई) , (घ, ङ)। किनारों के वजन तालिका में और आकृति में दिखाए जाते हैं। प्रारंभ में, निर्माण वन एफ ग्राफ के सभी कोने में शामिल है और किसी भी पसलियों शामिल नहीं है। एल्गोरिथ्म Kruskal पहली पसली (ए, ई), तो रिब जोड़ने के बाद से वजन कम किया था, और कोने एक और ई विभिन्न घटकों में हैं लकड़ी कनेक्टिविटी एफ (रिब (ए, ई) हरे रंग है), (सी, डी), क्योंकि कि कम से कम ग्राफ किनारों के इस किनारे वजन, एफ के लिए नहीं संबंधित है, और यह हरे रंग की है, एक ही कारण तो के लिए बढ़त अर्जित करते हैं (ए, बी)। लेकिन बढ़त (ख, ई) पारित हो जाता है, भले ही वह और शेष किनारों के कम से कम वजन है, क्योंकि यह लाल है: कोने बी और ई वन कनेक्टिविटी एफ के एक ही घटक के हैं, वह यह है कि, अगर हम एफ को बढ़त (ख, ई) जोड़ने के लिए, बनाई है चक्र। फिर हरे किनारे (ख, ग), पारित हो जाता है लाल बढ़त (ग, ई), और फिर डी, ई गयी। इस प्रकार, किनारों जोड़ रहे हैं क्रमिक रूप से (एक, ई), (ग, घ), (ए, बी), (ख, ग)। nihera इष्टतम फ्रेम से और मूल ग्राफ के होते हैं। तो इस मामले में यह एक एल्गोरिथ्म संचालित Kruskal। एक उदाहरण दिखाया गया है।

आंकड़ा दो जुड़े घटक होते हैं जो एक ग्राफ, पता चलता है। बोल्ड लाइनों इष्टतम फ्रेम पसलियों (हरा) Kruskal कलन विधि का उपयोग निर्माण संकेत मिलता है।

कम से कम वजन की एक कंकाल, उसके लिए बनाया एल्गोरिदम के उपयोग द्वारा - शीर्ष चित्र मूल ग्राफ, और नीचे से पता चलता।

जोड़ा पसलियों के अनुक्रम (1.6); (0.3), (2,6) या (2,6), (0.3) - महत्वपूर्ण नहीं है; (3,4); (0,1), (1,6) या (1,6), (0,1), भी परवाह (5,6)।

Kruskal एल्गोरिथ्म गैसकेट संचार, प्रत्येक देश में नए आवास एस्टेट इलाकों, साथ ही में अन्य मामलों में सड़कों का अनुकूलन करने के उदाहरण के लिए, व्यावहारिक अनुप्रयोग पाता है,।