Semestrálna práca: Základy teórie grafov

Kostra grafu je taký podgraf, ktorý obsahuje všetky vrcholy pôvodného grafu a neobsahuje uzavretý cyklus. Je to vlastne strom, ktorý obsahuje všetky vrcholy pôvodného grafu.
Minimálna kostra – kostra grafu, ktorej súčet ohodnotení hrán je minimálny.
Niekoľko aplikácií : optimálne spojenie miest (spojenie ciest telefónnej siete tak, aby sme spotrebovali minimum kábla, rozvody elektrickej energie, plynu a pod.)...