Satz von Berge/Austausch/Beispiel/Aufgabe/Kommentar

Der Satz behauptet, dass es bei einer nicht optimalen Paarung einen alternierenden Weg mit zwischen unabgedeckten verschiedenen Punkten gibt. Der Beweis zeigt, wie man einen solchen alternierenden Weg unter Verwendung einer optimalen Paarung findet und wie man damit die gegebene Paarung zu einer optimalen Paarung abändern kann. Das Beispiel ist besonders einfach, da es nur eine optimale Paarung gibt, nämlich diejenige, die aus den abstehenden Kanten besteht. Nennen wir diese ${}Q$. Wir bestimmen die symmetrische Differenz von ${}P$ und ${}Q$, diese besteht aus den drei Kanten links. Dies ist wie im Beweis des Satzes von Berge vorausgesagt eine alternierender Weg mit einer Kante aus ${}Q$ (nämlich zwei Stück) mehr als Kanten aus ${}P$ (nämlich eine). Wir schmeißen aus ${}P$ die Dreieckseite links heraus und nehmen die zwei abstehenden Kanten hinzu und erhalten eine optimale Paarung

(die in diesem Beispiel mit ${}Q$ übereinstimmt).

Zur kommentierten Aufgabe