Involvierte Definitionen:Veranstaltung: AlMaReferenz: @herzogWiSe22
⠀
Theorem: Satz von König
Sei
ein bipartiter Graph. Dann gilt:
ü Das heißt: um die Anzahl der Kanten eines maximalen Matchings zu bestimmen, kann stattdessen auch die Anzahl der Knoten einer minimalen Knotenüberdeckung bestimmt werden (oder vice versa, je nachdem, was einfacher ist).
Anmerkung
Beispiel:
