77 lines
1.9 KiB
Markdown
77 lines
1.9 KiB
Markdown
|
---
|
||
|
|
title: Matching
|
||
|
|
date: 2018-12-04
|
||
|
|
---
|
||
|
|
|
||
|
|
**Beispiele**
|
||
|
|
|
||
|
|
i) verschiedene Jobs und Bewerber $\widehat{=}$ Knoten. Kanten zwischen Job und
|
||
|
|
Bewerber, falls Bewerber geeignet ist für Job.
|
||
|
|
|
||
|
|
Ziel: Jedem Job einen Bewerber zuordnen
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
i) Statt Jobs haben wir Rechentasks und statt Bewerbern haben wir Rechner.
|
||
|
|
Kanten zwischen Task und Rechner falls Rechner die nötigen Ressourcen hat, um
|
||
|
|
Task auszuführen
|
||
|
|
|
||
|
|
i) Heiraten. Kanten zwischen Personen, falls sie sich heiraten wollen. Ziel:
|
||
|
|
alle sollen heiraten
|
||
|
|
|
||
|
|
|
||
|
|
**Bemerkung**: Fall i) und ii) entsprechen bipartiten Graphen.
|
||
|
|
|
||
|
|
|
||
|
|
# Definition (Matching)
|
||
|
|
|
||
|
|
Sei $G=(V,E)$ ein Graph und $M \subseteq E$
|
||
|
|
|
||
|
|
i) $M$ heißt **Matching**, falls
|
||
|
|
$$
|
||
|
|
\forall e_1,e_2 \in M : e_1 \cap e_2 = \emptyset
|
||
|
|
$$
|
||
|
|
|
||
|
|
i) Ein Knoten $v \in V$ heißt überdeckt von $M$, falls $\exists e\in M:v\in e$
|
||
|
|
|
||
|
|
i) Matching $M$ heißt perfekt, falls alle Knoten überdeckt sind, d.h.
|
||
|
|
$|M|=\frac{|V|}{2}$. Wenn $|V| = 2y + 1$ ($|V|$ ist ungerade), gibt es kein
|
||
|
|
perfektes Matching
|
||
|
|
|
||
|
|
|
||
|
|
**Frage**: Kann man effizient maximale Matchings finden?
|
||
|
|
|
||
|
|
Zumindest für bipartite Graphen, ja!
|
||
|
|
|
||
|
|
|
||
|
|
# Notation
|
||
|
|
|
||
|
|
Sei $G=(V,E)$ Graph und $X \subseteq V$. Dann sei
|
||
|
|
|
||
|
|
$$
|
||
|
|
\Gamma(X) = \bigcup\limits_{a\in X} \Gamma(a)
|
||
|
|
$$
|
||
|
|
|
||
|
|
|
||
|
|
# Satz (Hall, Heiratssatz)
|
||
|
|
|
||
|
|
Sei $G=(A\biguplus B, E)$ ein bipartiter Graph. $G$ enthält ein Matching $M
|
||
|
|
\subseteq E$ mit $|M| = |A|$, genau dann, wenn
|
||
|
|
|
||
|
|
$$
|
||
|
|
\forall X \subseteq A : |\Gamma(X)| \geq |X|
|
||
|
|
$$
|
||
|
|
|
||
|
|
## Bemerkung
|
||
|
|
|
||
|
|
* Falls Bedingung erfüllt, folgt $|B| \geq |A|$, denn $\Gamma(A) \subseteq B$
|
||
|
|
* Falls $|A| = |B|$, dann ist das Matching perfekt.
|
||
|
|
|
||
|
|
|
||
|
|
## Beweis
|
||
|
|
|
||
|
|
"$\Rightarrow$" sei $M$ ein Matching mit $|M| = |A|$ und $X \subseteq A$.
|
||
|
|
Betrachten der Teilgraph $G'=(A\bigcup B, M)$. Dann gilt $| \Gamma(X) | = | X
|
||
|
|
|$ in $G'$, da $M$ Matching und damit gilt $|\Gamma(X)| \geq |X|$ in $G$, da in
|
||
|
|
$G$ nur neue Nachbarn hinzu kommen können.
|