Matchings

Def: Für Graph G = (V, E): unabhängige Menge M $\subseteq$ E heißt Matching (Paarung).

Def: Knoten x $\in$ V heißt gesättigt bzgl. M, falls $\exists$y $\in$ V : xy $\in$ M.

Def: Matching M von G heißt maximal, falls für jedes Matching M' von G gilt: | M|$\ge$| M'|.

Def: Matching M von G heißt perfekt, falls es V sättigt.