9 Matchings bzw. Paarungen
Folgende Situation wird dabei betrachtet: Gegeben sei eine Menge von Dingen und zu diesen Dingen Informationen darüber, welche davon einander zugeordnet werden könnten. Ein Matching ist dann als eine solche Auswahl aus den möglichen Zuordnungen definiert, die kein Ding mehr als einmal zuordnet.
Definition
Matchingzahl \(\nu(G)\) ist definiert als \[\nu(G) = \max \{ |M| : M \subseteq E \text{ und } \forall e_1, e_2 \in M, e_1 \neq e_2 \implies e_1 \cap e_2 = \emptyset \}\]
Definition
Die Knotenüberdeckungszahl \(\tau(G)\) ist \[\tau(G) = \min \{ |C| : C \subseteq V \text{ und } \forall e \in E : e \cap C \neq \emptyset \}\]
Bemerkung
Die Knotenüberdeckungszahl eines Graphen ist mindestens so groß wie seine Paarungszahl, andererseits kann die Knotenüberdeckungszahl höchstens doppelt so groß sein wie die Paarungszahl. Also \[\nu(G) \leq \tau(G) \leq 2\nu(G) \leq n(G)\]
Beispiel
Ein Beispiel eines bipartiten Graphen, mit größter Paarung (blau) und kleinster Knotenüberdeckung (rot):
