Satz von König (Graphentheorie)

Der Satz von König ist ein mathematischer Satz aus der Graphentheorie, der für bipartite Graphen einen Zusammenhang zwischen einer größten Paarung und einer minimalen Knotenüberdeckung aufzeigt. Er lautet:

In einem bipartiten Graphen ist die Größe einer größten Paarung gleich der Größe einer minimalen Knotenüberdeckung.

Der Satz ist nach dem ungarischen Mathematiker Dénes Kőnig benannt.

Beispiel

Ein Beispiel eines bipartiten Graphen, mit größter Paarung (blau) und minimaler Knotenüberdeckung (rot):

Algorithmus

Dieser Algorithmus beschreibt wie man aus einer größten Paarung die minimale Knotenüberdeckung erhält. Eine größte Paarung kann beispielsweise mit dem Algorithmus von Hopcroft und Karp berechnet werden. Die beiden Knotenmengen des bipartiten Graphen werden in Folge mit $O$ (oben) und $U$ (unten) bezeichnet.

1. Größte Paarung berechnen.
2. Alle nicht in der Paarung enthaltenen Knoten aus $O$ werden in $T$ eingefügt.
3. Auf nicht in der Paarung enthaltenen Kanten gehen wir von diesen Knoten nach $U$. Alle besuchten Knoten werden in $T$ eingefügt.
4. Von den so erreichten Knoten in $U$ gehen wir auf in der Paarung enthaltenen Kanten wieder nach $O$. Alle besuchten Knoten werden in $T$ eingefügt.
5. Die minimale Knotenüberdeckung ergibt sich aus $(O \setminus T) \cup (U \cap T)$

Weblinks

• König-Egeváry Theorem auf MathWorld
• [1] Beweis vom Satz von König (PDF-Datei; 286 kB)