Augmentierender Kantenzug
Einfache Sprache
Def. Augmentierender Kantenzug
Sei $G=(V,E)$ ein Ungerichteter Graph, $M$ ein matching auf $G$ und $P$ ein Alternierender Kantenzug bzgl. $M$ in $G$. $P$ ist ein Augmentierender Kantenzug falls der erste und der letzte Knoten (Start- und End-Knoten) unmatched sind. Also nicht von dem matching $M$ abgedeckt sind.
Wie finde ich einen Augmentierender Kantenzug?
Augmentierender Kantenzug im Bipartiter Graph
Wir haben gegeben ein Bipartiter Graph $G=(V,E)$ und ein matching $M$ auf $G$. Wir definieren zunächst folgenden Gerichteter Graph $G'=(V,E')$. $E'$ verbinden die gleichen Knoten wie $E$. Die Richtung der Kanten wird folgender Maßen durch die Zugehörigkeit zu $M$ bestimmt
- Falls $e\in M$, geht die Kante von $B$ nach $A$,
- Falls $e\in E\setminus M$, geht die Kante von $A$ nach $B$ (Wobei $A$ und $B$ durch die Bipartitheit gegeben sind).
Dann nutzen wir folgen Satz augmentierender Kantenzug unmatched weg bipartite:
Algorithmus
1def find_aug_path(M, G):
2 """
3 Finds a augmenting path P with respect to the matching M in a bipartit graph G, if there exisit one.
4
5 Args:
6 M (Set): The current matching as a set of the vertices.
7 G (Graph): The bipartit Graph as a tuple, consisting of a tuple of sets of verticies (Namely A and B) and a set of edges.
8
9 Returns:
10 set: If a augmenting path P exisits then P in form of a set of vertices, else None
11 """
12 (V, E) = G
13 (A, B) = V
14 V_n = A.union(B)
15 E_n = set()
16 for (u, v) in E:
17 if (u, v) in M or (v, u) in M:
18 if u in A:
19 E_n.add((v,u))
20 else: # This means that u in B.
21 E_n.add((u,v))
22 else: # the edge is not part of M.
23 if u in A:
24 E_n.add((u,v))
25 else: # This means that u in B.
26 E_n.add((v,u))
27 # Find the unmatched vertices in A and B.
28 um_A = set()
29 for a in A:
30 found = False
31 for (u, v) in M:
32 if u == a or v == a:
33 found = True
34 break
35 if found:
36 um_A.append(a)
37 um_B = set()
38 for b in B:
39 found = False
40 for (u, v) in M:
41 if u == b or v == b:
42 found = True
43 break
44 if found:
45 um_B.append(b)
46 # Now we do a DFS to find a path from unmatched
47 # vertex in A to a unmatched vertex in B.
48 for start in um_A:
49 (visited, parent) = dfs_directed((V_n, E_n), start)
50 for end in [x for x in um_B if x in visited]:
51 # find path from end to start.
52 P = [end]
53 while True:
54 n = P[-1]
55 P.append(parent[n])
56 if n == start:
57 break
58 return P.reverse()
59 return None
Siehe Hier für dfs_directed.
Laufzeit
Aus dem Satz oben folgt das ein Augmentierender Kantenzug durch Tiefensuche oder Breitensuche in $G'$ mit einer Laufzeit $\mathcal O(|E|)$ gefunden werden kann.
Augmentierender Kantenzug im generellen Graph
Wir betrachten zunächst Flower (Graphentheorie)
Satz Stamm einer Flower für matching irrelvant
Sei $(P,B)$ eine flower bzgl. einem matching $M$ in einem Graphen $G=(V,E)$ mit einem Stamm $P\subseteq E$ und einer Blume $B\subseteq V$. Sei $G/B$ der Graph der dadurch entsteht, dass wir $B$ zu einem einzelnen Knoten $b$ zusammenfassen. Dabei wird jeder Knoten $\{u,v\}\in E$ mit $u\not\in B$ und $v\in B$ durch $\{u,b\}$ ersetzt und jeder Kante $e\in E$ mit $e\subseteq B$ entfernt wird. Sei $M/B$ die Menge der Kanten von $M$ welche mind. eine Knoten in $V\setminus B$ haben.
Dann ist $M$ ein Maximum Matching in $G$ g.d.w. $M/ B$ ein Maximum Matching in $G/ B$ ist.
note
- Der Beweis ist konstruktiv. Wenn wir ein größeres matching als $M/B$ in $G/B$ haben, dann können wir auch ein größeres matching als $M$ in $G$ finden.
- Der Satz sagt nicht, dass es ausreicht ein maximum matching in $G/B$ zu berechnen und dann $\frac{1}{2}(|B|-1)$ Kanten hinzuzufügen um ein maximum matching in $G$ zu erhalten. Beweis
O.b.d.A können wir annehmen das $P$ leer ist. Wenn das nicht der Fall wäre könnten wir das matching $M\triangle P$ (Symmetrische Differenz) betrachten, welches per Definition einen leeren Stamm hat. Da $(M\triangle P)/B = (M/B)\triangle P$, können wir annehmen das $P$ leer ist.
“$\Rightarrow$”: Nehme an das $N$ ein matching in $G/B$ ist, das größer ist als $M/B$. Dann existiert nach der Definition von $G/B$ ein matching $N'$ in $G$ das höchstens ein Knoten von $B$ matched. Diese matching kann zu dem matching $N^+$ erweitert werden, indem $\frac{1}{2}(|B|-1)$ Kanten zwischen Knoten in $B$ hinzugefügt werden. Dann ist $|N^+| - |M| = |N|-|M/B|$. Also $|N^+|$ ist um den gleichen Wert größer als $|M|$ also $|N|$ zu $|M/B|$.
“$\Leftarrow$” (Beweis durch Widerspruch) Nehme an das $M$ nicht das maximum matching in $G$ ist. Dann existiert ein augmentierender Kantenzug zwischen zwei unmatched Knoten $u$ und $v$. Da $B$ nur einen unmatched Knoten beinhaltet können wir $u\not\in B$ annehmen. (Jetzt machen wir eine Fallunterscheidung) Falls kein Knoten von $P$ in $B$ ist, dann ist $P$ ein augmentierender Kantenzug in $M/B$. Sonst ist mindestens ein Knoten von $P$ in $B$, so sei $w$ der erste Knoten von $P$ der zu $B$ gehört und $Q$ der Teil-Kantenzug von $u$ nach $w$. Nachdem $B$ zu einem Knoten geschrumpft wird bleibt $Q$ als augmentierender Kantenzug in $M/B$. In beiden Fällen is klar das $M/B$ kein maximum matching ist.