Perfekt Matching

Einfache Sprache

Ein matching heißt perfektes Matching, falls kein Knoten unmatched ist.

Def. Maximal Matching

Das Matching $M\subseteq E$ ist eine perfektes Matching, falls $2\cdot|M| = |V|$. Also jeder Knoten gematcht wurde.

Example

Von den drei Graphen besitzt nur der mittlere ein perfektes Matching