MST
Ein minimaler Spannbaum ist ein zusammenhängender Teilgraphen (Suchbaum, also zusammenhängend, kein Zyklus) mit minimalem Gewicht.
- sichere Kanten: enthalten in jedem MST
- Schnittprinzip: die kleinste ausgehende Kante von allen ausgehenden Kanten eines subsets einer Knotenmenge ist sicher in dem MST
siehe → 07 Boruvka → 08 Prim → 09 Kruskal
