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.)...