De graaf die, binnen een verbonden, gewogen graaf met het kleinst mogelijk totale gewicht alle punten verbindt, noemen we de [b][url=https://nl.wikipedia.org/wiki/Minimaal_opspannende_boom]minimaal opspannende boom[/url][/b] (in het Engels: Minimal Spanning Tree). Deze graaf is altijd een boom, dat wil zeggen dat hij geen cykels heeft (= een reeks door zijden verbonden knopen met hetzelfde begin- en eindpunt).
