Esquema
Minimaal opspannende boom
De graaf die, binnen een verbonden, gewogen graaf met het kleinst mogelijk totale gewicht alle punten verbindt, noemen we de minimaal opspannende boom (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).
