Google Classroom
GeoGebraGeoGebra Klaslokaal

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