Satz von König (Graphentheorie)

Einfache Sprache

Def. Satz von König (Graphentheorie)

In jedem Bipartiter Graph ist die Größe des Maximum Matching gleich der minimalen Größe des Knotenüberdeckung.

Als Beweis dient der Satz Korrektheit maximum matching Algorithmus in Maximum Kardinalität Matching-Problem.