ARTP - 11 - Minimálna kostra v očakávanom lineárnom čase

Zhrnutie prednášky

Prednáška sa venuje problému hľadania najlacnejšej (minimálnej) kostry v ohodnotenom grafe, pričom definícia zahŕňa aj nesúvislé grafy, kde výsledkom je strom v každom komponente. Zopakované je pravidlo inklúzie: najlacnejšia hrana vychádzajúca z ľubovoľného vrchola patrí do minimálnej kostry, a preto ju možno kontrahovať a z viacnásobných hrán ponechať najlacnejšiu. Na tomto pravidle stoja klasické algoritmy: Kruskalov so zložitosťou O(m log n) pri použití Union-Find a Primov, ktorý s Fibonacciho haldou dosiahne O(n log n + m). Ako tretí je predstavený Borůvkov algoritmus z roku 1926, ktorý z každého vrchola vyberie najlacnejšiu hranu a všetky vybrané hrany kontrahuje naraz, čo je základ pre pravdepodobnostný algoritmus s očakávaným lineárnym časom.

• - Minimálna kostra: acyklická maximálna množina hrán s minimálnym súčtom váh, v nesúvislom grafe strom v každom komponente.
• - Pravidlo inklúzie: najlacnejšia hrana z ľubovoľného vrchola patrí do minimálnej kostry.
• - Po kontrakcii hrany sa z viacnásobných hrán ponecháva len najlacnejšia.
• - Kruskalov algoritmus (1956) s Union-Find beží v čase O(m log n).
• - Primov algoritmus s Fibonacciho haldou beží v čase O(n log n + m).
• - Borůvkov algoritmus (1926) vyberie z každého vrchola najlacnejšiu hranu a všetky ich naraz skontrahuje.

Zhrnutie pripravené s pomocou AI z prepisu videa.