अप्रत्यक्ष बनाम निर्देशित ग्राफ के लिए न्यूनतम स्पैनिंग पेड़ एल्गोरिदम के बीच क्या अंतर है?

Question

क्या अप्रत्यक्ष ग्राफ एमएसटी एल्गोरिदम (प्राइम या क्रस्कल) निर्देशित एमएसटी एल्गोरिदम (एडमंड/चिउ) का एक सामान्य रूप है? निर्देशित मामले के लिए एमएसटी स्रोत कोड को खोजना कितना मुश्किल है? क्या हम निर्देशित ग्राफ में एमएसटी प्राप्त करने के लिए अप्रत्यक्ष समाधान का उपयोग कर सकते हैं?

इस से संबंधित है निम्नलिखित: अपने प्रश्न के मूल लगता है Why can't Prim's or Kruskal's algorithms be used on a directed graph?

Answer 1

क्या बनाता है एक MST खोजने एक निर्देशित ग्राफ में (तकनीकी तौर पर एक इष्टतम शाखाओं या न्यूनतम लागत शखिरूपता कहा जाता है) होने के लिए अप्रत्यक्ष ग्राफ में एमएसटी खोजने से अलग और इसलिए कठिन।

प्राइम और क्रस्कल के एल्गोरिदम दोनों कट संपत्ति की वजह से काम करते हैं। यदि जी = (वी, ई) एक ग्राफ है, तो जी में किसी भी कट (एस, वी - एस) के लिए, यदि कम से कम लागत वाला किनारा है {u, v} उस कट को पार करना, वह किनारा सभी एमएसटी से संबंधित होना चाहिए दुर्भाग्यवश, यह संपत्ति निर्देशित मामले में सच नहीं है। यहाँ एक counterexample है:

 2 
    A ----> B 
    |  |^
1 | -99 | | 1 
    |  v | 
    +-----> C 

यहाँ, कम से कम लागत वाली शखिरूपता एक में निहित इस एक है:

 2 
    A ----> B 
      | 
     -99 | 
      v 
      C 

हालांकि

, कटौती को देखो ({एक} {बी, सी}) कम से कम लागत वाली धार इस कटौती को पार करने के किनारे (ए, सी) है, लेकिन उस किनारे किसी भी कम से कम लागत वाली शखिरूपता ए

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

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

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

आशा है कि इससे मदद मिलती है!

Answer 2

मैं,