Grundlagen

Definition: Sei G=(V,E) ein ungerichteter, schlichter Graph. Ein Matching M in G ist eine Teilmenge von E, so daß keine zwei Kanten aus M einen Endpunkt gemeinsam haben.

Definition:

1.

Ein Matching M in G=(V,E) heißt perfekt (oder vollkommen), falls

$$\vert M\vert = \frac{\vert V\vert}{2}$$

2.

Ein Matching M heißt ,,Matching maximaler Kardinalität`` (engl. maximum matching) in G, falls es in G kein Matching M' mit |M'|>|M| gibt. ($\rightarrow$ durchgehend geringelt (rot) im Beispiel)

3.

Ein Matching M heißt maximal in G, falls es bezüglich ,,$\subseteq$`` maximal ist. (engl. maximal matching, $\rightarrow$ gepunktet geringelt (grün) im Beispiel)

Definition:

1.

Ein einfacher Pfad (Kreis) $v_0,v_1,\ldots,v_r$ heißt alternierend bzgl. eines Matchings M, falls die Kanten $\{v_i,v_{i+1}\} \text{, } 0 \leq i < r$, abwechselnd in M und nicht in M liegen.

2.

Ein alternierender Pfad heißt augmentierend, falls er bzgl. ,,$\subseteq$`` maximal ist und an beiden Enden ungematchte Kanten hat.

Bemerkung: Es kann keine augmentierenden Kreise geben.

Definition: Sei G=(V,E) ein Graph. Wenn V in zwei nichtleere Teilmengen V₁ und V₂ partitioniert werden kann ($V_1 \cup V_2=V$, $V_1 \cap V_2=\emptyset$), so daß $E \subseteq V_1 \times V_2$ ist, so heißt G bipartit (G=(V₁,V₂,E)).

Definition: Seien S, T zwei Mengen, dann bezeichne $S \ominus T$ die symmetrische Differenz von S und T, d.h. $S \ominus T = (S-T) \cup (T-S)$.

Lemma: Sei M ein Matching, P ein augmentierender Pfad bzgl. M. Dann ist auch $M \ominus P$ ein Matching und es gilt $\vert M \ominus P\vert = \vert M\vert + 1$.

Beweis:
,,$\Leftarrow$``

,,$\Rightarrow$`` Satz von Berge $\Diamond$



Lemma: Seien M, N Matchings in G, und sei |N| > |M|. Dann enthält $N \ominus M$ mindestens |N|-|M| knotendisjunkte augmentierende Pfade bzgl. M.

Beweis: Der Grad eines Knotens in $(V,\ N \ominus M)$ ist $\leq 2$.
Die Zusammenhangskomponenten von $(V,\ N \ominus M)$ sind also

1.

isolierte Knoten

2.

einfache Kreise (gerade Länge)

3.

alternierende Pfade

Seien $C_1,\ldots,C_r$ die Zusammenhangskomponenten in $(V,\ N \ominus M)$ dann gilt:

$$M \ominus \underbrace{C_1 \ominus C_2 \ominus \ldots \ominus C_r}_{N \ominus M} = N$$

Nur die C_i's die augmentierende Pfade bzgl. M sind, vergrößern die Kardinalität des Matchings und zwar jeweils um genau 1. Also muß es mindestens |N|-|M| C_i's geben, die augmentierende Pfade bzgl. M sind (ev. knotendisjunkt da ZHK's). $\Diamond$





Lemma: Sei M ein Matching der Kardinalität r, und sei s die maximale Kardinalität eines Matchings in G=(V, E). Dann gibt es einen augmentierenden Pfad bzgl. M der Länge $\leq 2\lfloor \frac{r}{s-r} \rfloor + 1$, wobei s > r vorausgesetzt sei.

Beweis: Sei N ein Matching maximaler Kardinalität in G, |N|=s. $N \ominus M$ enthält $\geq s - r$ augmentierende Pfade bzgl. M, die alle knotendisjunkt und damit auch kantendisjunkt sind. Einer dieser augmentierenden Pfade enthält daher $\leq \lfloor \frac{r}{s-r} \rfloor$ Kanten aus M. $\Diamond$



Lemma: Sei P ein kürzester augmentierender Pfad bzgl. M und sei P' ein augmentierender Pfad bzgl. des neuen Matchings $M \ominus P$. Dann gilt:
$\quad \vert P'\vert \geq \vert P\vert + 2\vert P \cap P'\vert$

Beweis: $N = M \ominus P \ominus P'$, also N = |M| + 2. Also enthält $M \ominus N$ mindestens 2 knotendisjunkte augmentierende Pfade bzgl. M, etwa $P_1,\ P_2$. Es gilt:

$$\begin{split} &N \ominus M = P \ominus P'\text{, also}\\ &... ...rt P\vert}_{\vert P\vert} + 2\vert P \cap P'\vert \end{split}$$

$\Diamond$


Schema für Matching Algorithmus:

1.

Beginne mit Matching $M_0 := \emptyset$.

2.

Berechne Folge $M_0,\ P_0,\ M_1,\ P_1,\ldots,\ M_i,\ P_i,\ldots$ Wobei jeweils P_i ein kürzester augmentierender Pfad bzgl. M_i ist und $M_{i+1}= M_i \ominus P_i$.

Es gilt: $\vert P_{i+1}\vert \geq \vert P_i\vert$

Lemma: Seien P_i und P_j in obiger Folge zwei augmentierende Pfade gleicher Länge. Dann sind P_i und P_j knotendisjunkt.

Beweis: Annahme: es gibt eine Folge $(P_k)_{k \geq 0}$ mit |P_i| = |P_j|, j>i, $P_i \cap P_j \neq 0$, j-i minimal gewählt. Durch die Wahl von j sind die Pfade $P_{i+1},\ldots,P_j$ knotendisjunkt. Also ist P_j ein augmentierender Pfad bzgl. M', dem Matching nach dem augmentieren mit $P_0,\ P_1,\ldots,\ P_i$. Mit vorigem Lemma: $\vert P_j\vert \geq \vert P_i\vert + 2\vert P_i \cap P_j\vert$ also $P_i,\ P_j$ kantendisjunkt. Da in M' jeder Knoten in P_i gematcht ist (und auch in $M' \ominus P_{i+1} \ominus P_{i+2} \ominus \ldots \ominus P_{j-1}$) können P_i und P_j auch keinen Knoten gemeinsam haben. $\Diamond$






Beweis: Sei $r:=\lfloor s - \sqrt{s}\rfloor$. Per Konstruktion ist |M_i|=i, also |M_r|=r. Mit dem Lemma über die maximale Länge eines kürzesten augmentierenden Pfades folgt

$$\vert P_r\vert \quad \leq \quad 2 \left\lfloor\frac{\lfloor... ...right\rfloor + 1 \quad = \quad 2 \lfloor\sqrt{s}\rfloor + 1.$$

Für $i \leq r$ ist also |P_i| eine der ungeraden Zahlen in $[1, 2\sqrt{s}+1]$, also eine von $\lfloor\sqrt{s}\rfloor+1$ ungeraden Zahlen. $P_{r+1}, \ldots, \P_{s-1}$ tragen höchstens $s-r-1 < \sqrt{s}$ zusätzliche Längen bei. $\Diamond$

Verfeinertes Schema:

$M:=\emptyset$; 
while $\exists$ augmentierender Pfad bzgl. M do
		 l := Länge des kürzesten augmentierenden Pfades bzgl. M;
		 bestimme eine bzgl. ,,$\subseteq$`` maximale Menge $\{Q_1,\ldots,Q_m\}$ 
		 augmentierender Pfade bzgl. M, die alle Länge l haben und knotendisjunkt sind;
		 $M := M \ominus Q_1 \ominus \ldots \ominus Q_m$; 
od