Efektívne algoritmy a zložitosť - 09 - Najlacnejšia kostra, Artikulácie

Zhrnutie prednášky

Prednáška pripomína problém hľadania najlacnejšej (minimálnej) kostry súvislého neorientovaného ohodnoteného grafu, teda stromu s n-1 hranami s minimálnym súčtom váh. Opakuje Kruskalov greedy algoritmus, ktorý hrany zoradí podľa váhy a postupne pridáva tie, ktoré nevytvoria cyklus. Jeho zložitosť O(m log m) závisí od testu cyklu implementovaného cez dátovú štruktúru Union-Find. Hlavná časť sa venuje dôkazu správnosti indukciou: pre hrany E1 až Ek pridané algoritmom existuje minimálna kostra, ktorá ich obsahuje. V indukčnom kroku sa do minimálnej kostry T* pridá hrana Ek, vznikne cyklus a z neho sa odstráni hrana s' prechádzajúca medzi množinami A a B. Keďže w(s') ≥ w(Ek), nová kostra T' nie je ťažšia ako T*, a teda je tiež minimálna.

• - Kostra grafu je acyklická podmnožina hrán s n-1 hranami, ktorá prepája všetky vrcholy.
• - Kruskalov algoritmus je greedy: hrany triedi podľa váhy a pridáva tie, ktoré netvoria cyklus.
• - Zložitosť Kruskalovho algoritmu je O(m log m) pri použití Union-Find na test cyklov.
• - Dôkaz správnosti sa vedie indukciou: existuje minimálna kostra obsahujúca prvých k hrán E1 až Ek.
• - Formulácia hovorí o existencii minimálnej kostry, lebo minimálnych kostier môže byť viac.
• - V indukčnom kroku sa pridá hrana Ek do T*, a z vzniknutého cyklu sa odstráni hrana s' medzi množinami A a B.
• - Z w(s') ≥ w(Ek) vyplýva w(T') ≤ w(T*), takže T' je tiež minimálna kostra obsahujúca E1 až Ek.

Zhrnutie pripravené s pomocou AI z prepisu videa.