Lexikon der Mathematik: Berge-Tutte, Satz von
eine Erweiterung des bekannten Ein-Faktor-Satzes von Tutte, die Berge 1958 gefunden hat. Der Satz lautet:
Es sei G ein Multigraph der Ordnung n und M ein maximales Matching von G.
Dann gilt
Der Spezialfall, daß M ein perfektes Matching ist, also n = 2|M| gilt, liefert gerade den Ein-Faktor-Satz von Tutte.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!