Modell 2 Lösung

Wie lässt sich das zweite Segmentierungsproblem (Modell 2) lösen?

Erinnerung:

Eingabe: Ungerichteter Graph $G=(V,E,a,b,w)$ mit Knotengewichten $a(v)\geq 0$ und $b(v)\geq 0, v\in V$ sowie Kantengewichten $w(e) \geq 0, e\in E$
Aufgabe: Bestimme einen Schnitt $(A,B)$ von $G$ mit maximaler Qualität $q(A,B)= a(A) + b(B) - w(A,B)$