Maximum matching no augmenting path theorem

Einfache Sprache

Def. Maximum matching no augmenting path theorem

Sei $G=(V,E)$ ein Ungerichteter Graph, und $M$ ein matching in $G$. Dann ist $M$ ein Maximum Matching g.d.w. keine Augmentierender Kantenzug bzgl. $M$ existiert.

Beweis: G.d.w. wird durch Implikation in beide Richtungen gezeigt. “$\Rightarrow$”: Beweis durch Widerspruch: Man nehme an das ein Augmentierender Kantenzug $P$ bzgl. $M$ existiert. Dann ist nach dem Matching Augmentation Lemma $M\mathbin{\vartriangle} P$ ein matching in $G$ mit $|M\mathbin{\vartriangle} P| = |M| + 1$, was der maximalität von $M$ widerspricht.

“$\Leftarrow$”: Indirekter Beweis: Man nehme an, dass $M$ kein Maximum Matching. Es muss also ein Maximum Matching $M^*$ existieren so, dass $|M| < |M^*|$. Sei $Q:= M \mathbin{\vartriangle} M^*$. Dann können wir folgende Beobachtungen machen:

1. $Q$ enthält mehr Kanten von $M^*$ als von $M$, da $|M| < |M^*|$ gilt.
2. Jeder Knoten von $Q$ ist inzident zu höchstens einer Kante in $M\cap Q$ und einer Kanter in $M^*\cap Q$.
3. Daher besteht $Q$ aus Zyklen und Kantenzügen, dessen Knoten zwischen $M$ und $M^*$ alternieren.
4. Da $|M| < |M^*|$ ist, muss es einen Kantenzug $P$ geben, der mehr Knoten von $M^*$ als von $M$ beinhaltet. Dieser Kantenzug $P$ ist ein Augmentierender Kantenzug bzgl. $M$.