Gegeben ist ein (bipartiter) Graph G=(V,E). Dann heißt ein Matching M in Gkardinalitätsmaximal, wenn für alle Matchings M′ gilt: ∣M∣≥∣M′∣.
Ein Matching ist also kardinalitätsmaximal, wenn es kein anderes Matching in dem Graphen mit mehr Kanten gibt.
Beispiel
Das Matching M ist kardinalitätsmaximal.
Das Matching M′ ist nicht kardinalitätsmaximal, da ∣M∣≥∣M′∣⇒3≥2.
Der Satz von Berge
Mit dem Satz von Berge lässt sich herausfinden, ob ein Matching kardinalitätsmaximal ist oder nicht. Benannt ist dieser Satz nach dem
französischen Mathematiker Claude Berge.
Sei M ein Matching und P ein M-augmentierender
Weg. Es könnte ein vergrößertes Matching M′ durch einen Kantentausch mit Kanten aus der symmetrischen DifferenzM△P erzeugt werden.
⇒M′=M△P. Dazu wird mit einer Breitensuche beim ersten ungematchten Knoten gestartet und ein M-augmentierender Weg gesucht.
Falls einer gefunden wurde, wird ein Kantentausch durchgeführt. Dieses Prinzip spielt beim später aufgeführten Beweis eine wichtige Rolle.
Finden eines augmentierenden Pfades und anschließendes Vergrößern eines Matchings
Matching M={{A,D},{B,E}} in einem Graphen G.
Starte beim ersten ungematchten Knoten C.
Satz von Berge
Sei G=(V,E) ein Graph und M⊆E ein Matching in diesem Graphen. M ist kardinalitätsmaximal genau dann, wenn es keinen M-augmentierenden Weg gibt.ber1957
Beweis
⇒
Für die Hinrichtung wird angenommen, dass G=(V,E) ein Graph mit einem Matching M⊆E und mit einem
M-augmentierenden Weg P sei. Schaut man sich jetzt die symmetrische DifferenzM′=M△P an, erkennt man, dass ∣M′∣>∣M∣ gilt und somit kann M nicht kardinalitätsmaximal sein.
⇐
Es wird angenommen, es gäbe ein Matching M und ein weiteres Matching M′ mit ∣M′∣>∣M∣. Schaut man sich weiter unten die symmetrische Differenz M△M′ der beiden Matchings an,
erkennt man, dass M′△M aus folgenden Teilen besteht: isolierten Knoten, elementaren M-alternierenden Kreisen und M-alternierenden
Wegen. Ein elementarer Kreis enthält dabei die gleiche Kantenanzahl aus M wie aus M′. Falls es einen elementaren Weg gibt, der mehr Kanten aus
M′ als aus M enthält, dann wäre es ein augmentierender Weg. Dies ist zwangsläufig der Fall, da M nicht kardinalitätsmaximal ist. Somit existiert
ein augmentierender Weg, was ein Widerspruch zu der Annahme ist, dass ein kardinalitätsmaximales Matching keinen augmentierenden Weg enthalten darf. □
Matching M
Matching M′ mit ∣M′∣>∣M∣
Die symmetrische Differenz M△M′
Man erkennt die isolierten Knoten, einen elementaren Kreis und einen elementaren Weg.
Der elementare Weg ist in diesem Fall augmentierend und M kann vergrößert werden durch diesen Weg.
In den folgenden beiden Graphen ist jeweils ein Matching M farblich markiert. Man erkennt im linken Matching, dass beispielsweise der Weg (e,b,d,a) ein M-augmentierender
Weg ist, da e und a keine Knoten sind, die inzident zu einer gematchten Kante sind. Somit ist das Matching nicht kardinalitätsmaximal. Im rechten Graphen gibt
es keinen augmentierenden Weg, weswegen das rechte Matching nach dem Satz von Berge ein kardinalitätsmaximales Matching ist.
Die Knotenanzahl im folgenden Graphen G ist ungerade, was bedeutet, dass kein perfektes Matching existieren kann. Es wurde trotzdem ein
kardinalitätsmaximales Matching M gefunden, da es keinen M-augmentierenden Weg P gibt.
Verständnisfragen
Befindet sich in diesem Graphen ein $M$-augmentierender Weg ?
Wie viele Matchingkanten könnten durch einen Kantentausch hinzugefügt werden, damit ein kardinalitätsmaximales Matching entsteht?
BER1957: Berge, Claude: Two Theorems in Graph Theory. Proceedings of the National Academy of Sciences of the United States of America, 43 (9): 842–844.↩