Minimum spanning tree
Minimum spanning tree (Minimální kostra) je pojem v oblasti grafové teorie a informatiky. Minimalizuje celkovou váhu hran spojením všech vrcholů v neorientovaném grafu tak, že se vytvoří podgraf, který obsahuje všechny vrcholy a žádné cykly. Hlavním cílem je zajistit, aby součet vah hran v tomto podgrafu byl co nejmenší. Existují různé algoritmy pro nalezení minimální kostry, mezi nejznámější patří Primův algoritmus, Kruskalův algoritmus a Borůvkovy algoritmus. Tyto metody se používají v různých aplikacích, například v optimalizaci sítí, návrhu elektrických obvodů, plánování tras a mnoha dalších oblastech. Minimální kostra má také zajímavé vlastnosti, například je jedinečná, pokud má graf všechny hrany s různými váhami. Tímto způsobem se minimální kostra stává klíčovým nástrojem v teoriích a aplikacích spojených s grafy.