Satz von König (Graphentheorie)

Der Satz v​on König i​st ein mathematischer Satz a​us der Graphentheorie, d​er für bipartite Graphen e​inen Zusammenhang zwischen e​iner größten Paarung u​nd einer minimalen Knotenüberdeckung aufzeigt. Er lautet:[1]

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

Der Satz ist nach dem ungarischen Mathematiker Dénes Kőnig benannt, der ihn 1931 bewiesen hat. Unabhängig von König hat der Mathematiker Jenő Egerváry, ebenfalls im Jahr 1931[2][3] , eine allgemeinere Formulierung des Theorems für gewichtete Graphen bewiesen. Deshalb wird der Satz gelegentlich auch als Satz von König und Egerváry bezeichnet.

Beispiel

Ein Beispiel e​ines bipartiten Graphen, m​it größter Paarung (blau) u​nd minimaler Knotenüberdeckung (rot):

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 ${\displaystyle O}$ (oben) und ${\displaystyle U}$ (unten) bezeichnet.

1. Eine größte Paarung berechnen.
2. Alle nicht in der Paarung enthaltenen Knoten aus ${\displaystyle O}$ werden in ${\displaystyle T}$ eingefügt.
3. Auf nicht in der Paarung enthaltenen Kanten gehen wir von diesen Knoten nach ${\displaystyle U}$. Alle besuchten Knoten werden in ${\displaystyle T}$ eingefügt.
4. Von den so erreichten Knoten in ${\displaystyle U}$ gehen wir auf in der Paarung enthaltenen Kanten wieder nach ${\displaystyle O}$. Alle besuchten Knoten werden in ${\displaystyle T}$ eingefügt.
5. Wiederhole die beiden vorherigen Schritte, solange bis keine neuen Knoten mehr in ${\displaystyle T}$ eingefügt werden.
6. Die minimale Knotenüberdeckung ergibt sich aus ${\displaystyle (O\setminus T)\cup (U\cap T)}$

Variante für gewichtete Graphen

Unabhängig von König hat der Mathematiker Jenő Egerváry eine Variante des Theorems für gewichtete Graphen bewiesen[3]. Hier betrachtet man bipartite Graphen ${\displaystyle G=(V=A\cup B,E)}$ mit einer Gewichtsfunktion ${\displaystyle d\colon E\to \mathbb {N} }$ die jeder Kante im Graphen eine nichtnegative ganze Zahl zuordnet. Eine gewichtete Knotenüberdeckung von ${\displaystyle d}$ ist eine Funktion ${\displaystyle \pi \colon V\to \mathbb {N} }$ die jedem Knoten im Graphen eine nichtnegative ganze Zahl zuordnet, sodass ${\displaystyle \pi (u)+\pi (v)\geq d(\{u,v\})}$ für alle Kanten ${\displaystyle \{u,v\}\in E}$ gilt. Das Gewicht von ${\displaystyle \pi }$ is durch ${\displaystyle \sum _{v\in V}\pi (v)}$ gegeben. Der Satz lautet dann wie folgt:

In einem vollständigen bipartiten Graphen ${\displaystyle G=(V=A\cup B,E)}$ mit ${\displaystyle |A|=|B|}$ und einer Gewichtsfunktion ${\displaystyle d\colon E\to \mathbb {N} }$, entspricht das maximale Gewicht einer Paarung dem minimalen Gewicht einer gewichteten Knotenüberdeckung von ${\displaystyle d}$.

Einzelnachweise

1. Klaus Wagner: Graphentheorie. Bibliographisches Institut Hochschultaschenbücher, Mannheim 1970, ISBN 3-411-00248-4, Satz 9.9
2. Jenő Egerváry: Matrixok kombinatorius tulajdonságairól. In: Matematikai és Fizikai Lapok. Band 38, 1931, S. 16–28. (On combinatorial properties of matrices)
3. Harold W. Kuhn: On combinatorial properties of matrices. In: George Washington University (Hrsg.): Logistics Papers. Band 11, 1955, S. 1–11.

Weblinks

• Eric W. Weisstein: König-Egeváry Theorem. In: MathWorld (englisch).
• Beweis zum Satz von König (PDF; 286 kB)