Maximal Matching

Einfache Sprache

Def. maximal matching

Das matching $M\subseteq E$ ist ein maximales Matching, wenn es keine Kante $e\in E\setminus M$ gibt so, dass $\{e\}\cup M$ ein matching ist. Das matching darf also nicht eine Teilmenge eines anderen matching sein.

Example

Drei Graphen mit dem maximalen Matching in Rot.