Blossom algorithm

Einfache Sprache

Der Blossom algorithm findet für einen Graph ein Maximum Matching. Namens gebend sind die im Algorithmus verwendete Flower Struktur.

Idee Blossom algorithm

Der Algorithmus von Edmonds besteht aus zwei Phasen. In der ersten Phase wird ein Wald gepflanzt und in der zweiten wächst der Wald. Wald pflanzen: Sei $M$ ein matching in $G$. Wir beschriften alle unmatched Knoten mit $\mathrm{EVEN}$ und alle anderen Knoten lassen wir unbeschriftet. Wir halten auch einen Alternierender Wald vor. Um genau zu sein bildet jeder mit $\mathrm{EVEN}$ beschrifteter Knoten einen so genannten singleton tree, nur aus einem Knoten besteht. Auch seed genannt. Wald wächst: Gegeben ein alternierender Wald und ein partielle Beschriftung. Wir verarbeiten jeden mit $\mathrm{EVEN}$ beschrifteten Knoten $u$ wie folgt, dazu betrachten wir welche Kanten $u$ inzident ist und machen eine Fallunterscheidung:

1. Falls eine Kante $\{u,v\}$ existiert, wobei $v$ unbeschriftet ist, dann beschrifte $v$ mit $\mathrm{ODD}$. Da $v$ nicht unmatched sein kann (sonst hätten wir $v$ ja in Wald pflanzen mit $\mathrm{EVEN}$ beschriftet) beschriften wir den mit $v$ gematcheten Knoten $w$ ($\{v,w\}\in M$) mit $\mathrm{EVEN}$. $w$ kann noch nicht beschriftet sein, da wir immer die zwei Knoten eines matchings gleichzeitig beschriften.
2. Falls eine Kanten $\{u,v\}$ existiert, wobei $v$ mit $\mathrm{EVEN}$ beschriftet ist und $v$ zu einem anderen Alternierender Baum als $u$ gehört, dann überschneiden sich die Kantenzüge von $u$ und $v$ zu ihrer jeweiligen Wurzel nicht (haben keinen Knoten gemeinsam). Zusammen mit der Kante $\{u,v\}$ existiert somit ein augmentierender Kantenzug von der einen Wurzel zu der anderen Wurzel. Damit können wir das matching $M$ um 1 vergrößern (indem wir alle kannten in dem argumentierenden Kantenzug invertieren), wobei wir Blumen entschrumpfen und folgenden Satz benutzen, und erhalten $M'$. Falls $M'$ nicht optimal ist beginnen wir erneut mit Wald pflanzen mit dem neuen Matching $M'$.
3. Falls eine Kanten $\{u,v\}$ existiert, wobei $v$ mit $\mathrm{EVEN}$ beschriftet ist und $v$ zu dem gleichen Alternierender Baum wie $u$ gehört, dann bilden die zwei Kantenzüge von $u$ und $v$ zu ihrer jeweiligen Wurzel (haben keinen Knoten gemeinsam) und $\{u,v\}$ eine flower $(P,B)$. Dann können wir die Blume $B$ dieser flower zu einem Knoten $b$ schrumpfen. Wir beschriften $b$ mit $\mathrm{EVEN}$ und können unsere restliche Beschriftung unverändert lassen. Fahre nun mit Wald wächst fort aber mit dem kleinern Graphen $G/B$, dem matching $M/B$ und der Beschriftung.

Falls keine Alternative möglich ist, breche ab und gib das matching mit den entschrumpften Blumen aus.

Beweis / Korrektheit Nimm an, dass für jeden mit $\mathrm{EVEN}$ beschrifteten Knoten keine der drei Fälle zutrifft. Dann behauten wir das wir das Maximum Matching $M'$ in dem Graphen $G' = (V',E')$ gefunden haben (Hier ist $G'$ der Graph wo die Blumen noch geschrumpft sind). Dazu betrachten wir die Teilmenge $U := \mathrm{ODD}\subseteq V'$. Also die Teilmenge, welche alle mit $\mathrm{ODD}$ beschriftete Knoten enthält. Dann wenden wir folgen Formel aus der Tutte-Berge Formel für $G'$ an. Da keine Kanten zwischen mit $\mathrm{EVEN}$ beschriftete Knoten existiert (sonst würde Schritt 2. und 3. anwendbar sein) und keine Kante zwischen einem mit $\mathrm{EVEN}$ beschrifteten Knoten und einem mit $\mathrm{ODD}$ beschrifteten Knoten existieren kann (sonst würde Schritt 1. anwendbar sein), ist jeder mit $\mathrm{EVEN}$ beschriftete Knoten eine zusammenhängend Komponente in $G'\setminus \mathrm{ODD}$. Daher ist $o(G'\setminus \mathrm{ODD}) = |\mathrm{EVEN}|$. Bemerke das $|M'| = |\mathrm{ODD}| + \frac{1}{2}(|V'| - |\mathrm{ODD}| - |\mathrm{EVEN}|)$, da alle nicht beschriftete Knoten mit nicht beschriftete Knoten gematchet sind. Dann ergibt sich

Das zeigt, dass $M'$ ein Maximum Matching in $G'$ ist. Durch wiederholte Anwendung von Satz erhält man ein Maximum Matching in $G$.