Modell 1 Lösung

Wie lässt sich das erste Segmentierungsproblem (Modell 1) lösen?

Erinnerung:

Eingabe: Ungerichteter Graph $G=(V,E,w)$ mit Kantengewichten $w(e) \geq 0, e\in E$
Aufgabe: Bestimme einen Schnitt $(A,B)$ von $G$ mit minimalen Kosten $w(A,B)$