2. Základní pojmy / Kostra grafu
Kostrou grafu budeme rozumět libovolný podgraf, který hranami spojuje všechny vrcholy původního grafu a zároveň sám neobsahuje žádnou kružnici (→ jde o strom).
Definice kostry
Nechť G = (V,E) je graf. Libovolný strom (V,E'), kde E' 
E, nazveme kostrou grafu.
Příklady
Pokud původní graf (graf, ke kterému hledáme kostru) obsahuje kružnici, pak máme více možností, jak kostru zvolit.
Obr. č. 2.31 - Příklad různých koster stejného grafu