Minimální kostra (nebo minimální kostra ) v (neorientovaném) spojeném váženém grafu je kostra tohoto grafu, která má minimální možnou váhu, kde váha stromu je součtem vah jeho hran.
Problém najít minimální kostru se často vyskytuje v podobném prostředí: předpokládejme, že existuje n měst, která je třeba propojit silnicemi, aby se člověk mohl dostat z jakéhokoli města do kteréhokoli jiného (přímo nebo přes jiná města). Je povoleno stavět silnice mezi danými dvojicemi měst a náklady na výstavbu každé takové silnice jsou známy. Je nutné rozhodnout, které silnice postavit, aby se minimalizovaly celkové náklady na výstavbu.
Tento problém lze z hlediska teorie grafů formulovat jako problém najít minimální kostru v grafu, jehož vrcholy reprezentují města, hrany jsou dvojice měst, mezi kterými lze položit přímou silnici a váha hrany je stejná na náklady na výstavbu odpovídající silnice.
Existuje několik algoritmů pro nalezení minimální kostry. Některé z těch známějších jsou uvedeny níže:
Problém Steinerova stromu je podobný problému minimálního spanning tree . Obsahuje několik bodů v rovině a je potřeba mezi nimi položit graf cest tak, aby se minimalizoval součet délek cest. Hlavním rozdílem od problému s minimální kostrou je v tomto případě to, že je povoleno přidat další body větvení, aby se dále snížil součet délek hran. Problém Steinerova stromu je NP-úplný .
| Algoritmy vyhledávání grafů | ||
|---|---|---|
| Neinformované metody | ||
| Informované metody | ||
| Zkratky | ||
| Minimální kostra | ||
| jiný | ||