minimální kostra grafu
Nechť je dán souvislý graf G = (V, E). Nechť pro každou hranu e grafu G je dáno reálné číslo w(e), tzv. ohodnocení hrany e. Mezi všemi kostrami grafu G najděte kostru T = (V, E'), pro kterou součet ohodnocení hran w(T) = sum w(e), kde e element of E', nabývá minimální hodnoty. Kostru T nazveme minimální kostrou grafu G a w(T) cenou kostry T.
Minimální kostra grafu G