Vergrößerungs-Prinzip

#Studium #Informatik #Definition #DS

Wenn ein erweiternder Pfad $P$ existiert, so besitzt er genau eine Kante mehr aus $E (G) ∖ M$ als aus $M$ . Diese Methode kann man algorithmisch zum Berechnen von matchings maximaler Größe in bipartiten Graphen benutzen, indem man die Kantenbelegung invertiert.

Beispiel zur Augmentierung:
Sei $M = {{b_{1}, a_{2}}}$ ein initiales Matching.
Ein erweiternder Pfad starte im $M$ -freien Knoten $a_{1} \in A$ und ende im $M$ -freien Knoten $b_{2} \in B$ : $P = (a_{1}, {a_{1}, b_{1}}, b_{1}, {b_{1}, a_{2}}, a_{2}, {a_{2}, b_{2}}, b_{2})$ Die Kanten ${a_{1}, b_{1}}$ und ${a_{2}, b_{2}}$ sind nicht in $M$ , während ${b_{1}, a_{2}} \in M$ ist.
Durch das Vertauschen der Zugehörigkeit erhalten wir das neue Matching: $M^{'} = {{a_{1}, b_{1}}, {a_{2}, b_{2}}}$ Es gilt $| M^{'} | = | M | + 1 = 2$ .
Laufzeit: Dann kann ein matching $M$ von $G$ der Größe $A$ in Zeit $O (| V (G) | \cdot | E (G) |)$ berechnet werden.