maximaler Schnitt

Der maximale Schnitt eines Graphen ist eine Zerlegung seiner Knotenmenge in zwei Teilmengen , so dass das Gesamtgewicht der zwischen den beiden Teilen verlaufenden Kanten maximal wird. Im Gegensatz zum minimalen Schnitt ist das Problem NP-vollständig.