Matching (Graphentheorie)
Matching
Def. Matching
Matching in einem Ungerichteter Graph $G = (V, E)$ ist eine Teilmenge $E' \subseteq E$ von Kanten, von denen keine zwei Kanten einen gemeinsamen Endpunkt gemeinsam haben.
Alternativ: Sei $G=(V,E)$ ein Ungerichteter Graph. Die Teilmenge von Kanten $M\subseteq E$ nennt man matching, falls jeder Knoten in $V$ incident zu höchstens einer Kante in $M$ ist. Ein Knoten $v\in V$ heißt unmatched wenn es keine Kante $e\in M$ gibt so, dass $v$ incident zu $e$ ist.