Satz von König

Die maximale Größe eines matchings in einem bipartiten Graph $G$ ist gleich der minimalen Größe eines vertex covers in $G$.

Beweis des Satzes von König

Sei $M$ ein matching in $G$ maximaler Größe. Wir konstruieren eine menge $U\subseteq V(G)$ wie folgt:
Für alle $e=\{a,b\}\in M$ füge a oder b zu $U$ hinzu:
Wenn ein alternierender Pfad in b endet, wähle b. Sonst wähle a.

Behauptung: $U$ ist ein minimales vertex cover von $G$.

1. Minimalität: Minimalität ist klar. $U$ deckt alle $e\in M$ ab. Da kein vertex cover kleiner als das maximale matching sein kann ($|X|\ge |M|$), ist die Minimalität gegeben.
2. Überdeckung: Zu zeigen: Wenn $\{a,b\}\in E(G)\mathrm{\setminus }M$ dann ist $a\in U$ oder $b\in U$. Wenn $a\in U$, sind wir fertig. Also nehmen wir an, dass $a\notin U$.
   • Behauptung: Es gibt einen alternierenden Pfad, der in b endet.
   • 1. Wenn $a\notin V(M)$, dann ist ab ein solcher Pfad.
   • 2. Sonst, ist $a\in V(M)$ und es gibt $b^{\prime }\in B$ mit $\{a,b^{\prime }\}\in M$. Da $a\notin U$, endet ein alternierender Pfad $P$ in $b^{\prime }$. Dann ist aber $P^{\prime }=Pab$ ein alternierender Pfad, der in b endet.
   • Da $M$ maximal es ist, kann $P^{\prime }$ kein erweiternder Pfad sein. Also ist $b\in e^{\prime }$ für ein $e^{\prime }\in M$ und wurde daher zu $U$ hinzugefügt. Jede Kante ist somit durch $U$ überdeckt. $◻$

Links

• DS_vollständiger_foliensatz.pdf
• Matching
• Bipartiter Graph
• Vertex Cover