Kapitel 8Olympiade27 Min.
Maximale Schnitte
Schnitte, Paarungen und Austauschpfade · Abschnitt 29 von 64
Gelöstes Beispiel
Knotenverschiebung als Test
In einem maximalen Schnitt kann kein einzelner Knoten mehr innere als äußere Nachbarn haben.
Gelöstes Beispiel
Alternierend vergrößern
Ein augmentierender Weg tauscht Rollen und fügt netto eine Paarungskante hinzu.
Gelöstes Beispiel
Vier Optimalitätsstufen
Maximal, minimal, lokal optimal und global maximum brauchen jeweils andere Begründungen.