Ungerichteter Graph/Optimale Paarung/Alternierender Weg/Fakt

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Satz von Berge

Eine Paarung in einem Graphen

ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.