Gegeben sei ein Graph G=(V,E) und eine Menge U⊆V.
Ein Matching wird U-überdeckend genannt, falls jedes Element u∈U einen Matchingpartner in M besitzt:
∃v∈V:{u,v}∈M,∀u∈U
Definition
Ein V-überdeckendes Matching M in einem Graphen G=(V,E) wird auch perfekt genannt.
Dies ist genau dann der Fall, wenn 2⋅∣M∣=∣V∣.
Insbesondere in bipartiten Graphen , mit PartitionV=L∪˙R, ist dies äquivalent zu ∣M∣=∣L∣=∣R∣.
Beispiele:
In einem Kreis gerader Länge existieren immer genau zwei perfekte Matchings (gezeigt in rot und blau).
Enthält der Graph eine ungerade Anzahl Knoten, kann kein perfektes Matching existieren.
Aber auch mit einer geraden Anzahl Knoten ist nicht immer gewährleistet, dass ein perfektes Matching existiert.
Selbst wenn der Graph bipartit ist.
Existieren isolierte Knoten, kann es kein perfektes Matching geben.
Verständnisfragen
Wie viele verschiedene perfekte Matchings existieren im gezeigten Graphen?
Gegeben sei ein bipartiter GraphG=(V,E) mit PartitionV=L∪˙R, sodass gilt ∣L∣=∣R∣=n.
Wie viele perfekte Matchings existieren?
Gegeben sei ein vollständiger bipartiter Graph, deren Partitionsklassen jeweils n Knoten enthalten.
Wie viele perfekte Matchings existieren?
❗ Der gezeigte Graph enthält nicht nur ein perfektes Matching. Klicke die Kante an, welche Teil jedes perfekten Matchings ist.
Korrekt! Da der grün markierte Knoten nur einen Nachbarn hat, muss diese Kante immer Teil eines perfekten Matchings in diesem Graphen sein.
❗ Derselbe Graph aus der vorherigen Aufgabe. Klicke diesmal die Kante an, welche niemals Teil eines perfekten Matchings ist.
Korrekt! Aus der vorherigen Aufgabe ist bekannt, dass die grün markierte Kante immer Teil eines perfekten Matchings ist.
Da die gesuchte Kante adjazent zu dieser ist, ist sie selbst niemals Teil eines perfekten Matchings.
Beobachtung
Perfekte Matchings sind immer (kardinalitäts-)maximal.
Dies ist offensichtlich der Fall, denn die Kanten eines Matchings sind paarweise nicht zueiander inzident.
Also gilt für jedes Matching M in Graph G=(V,E) folgende Obergrenze: ∣M∣≤2∣V∣.
Per Definition befinden sich perfekte Matchings an genau dieser Grenze.□
Anmerkung: Zwar sind perfekte Matchings immer kardinalitätsmaximal, aber anders herum gilt dies nicht unbedingt:
Auch wenn kein perfektes Matching existiert, ein kardinalitätsmaximales Matching existiert trotzdem.
Perfekte Matchings in bipartiten Graphen
Satz von Hall (Heiratssatz)
Satz
Gegeben sei ein bipartiter GraphG=(L∪˙R,E).
Sei N(S) die Nachbarschaft der Menge S, also alle Knoten, welche adjazent zu mindestens einem Knoten in S sind.
Es existiert genau dann ein L-überdeckendes Matching in G, falls ∣S∣≤∣N(S)∣,∀S⊆L gilt.
Analog können die Mengen L und R vertauscht werden, um eine notwendige und hinreichende Bedingung zu erhalten, wann ein R-überdeckendes Matching existiert.
Beweis
M={{A,X},{B,Y},{C,Z}}
Zunächst wird die Hinrichtung bewiesen:
Wenn ein L-überdeckendes Matching existiert, dann ist auch die Kardinalität der Nachbarschaft jeder Teilmenge von L mindestens genau so groß ist wie die Kardinalität der Teilmenge selbst.
Gegeben sei ein bipartiter Graph G=(L∪˙R,E) und ein L-überdeckendes Matching M⊆E.
S={A,B}M(S)={X,Y}N(S)={X,Y,Z}N(S)∖M(S)={Z}
Betrachtet man nun eine beliebige Teilmenge S⊆L.
Im Folgenden wird die Menge der Matchingpartner aller Knoten aus S als M(S) bezeichnet.
Es gilt, dass zumindest alle Matchingpartner der Elemente in der Nachbarschaft sein müssen:
M(S)⊆N(S).
Da M ein L-überdeckendes Matching ist, gilt ∣S∣=∣M(S)∣.
Aus diesen beiden Bedingungen kann man ∣S∣≤∣N(S)∣ schließen und damit die Hinrichtung beweisen.
Weitere Knoten können natürlich trotzdem in der Nachbarschaft sein.
U={A,B,Z}
Der Beweis für die Rückrichtung kann mithilfe des Satzes von König geführt werden.
Sei U⊆L∪R eine minimale Knotenüberdeckung. Im Beispiel links ist dieses gelb markiert.
U={A,B,Z}L′={C}N(L′)={Z}
Betrachte die Knoten auf der linken Seite, die nicht in der minimalen Knotenüberdeckung liegen. Sei L′=L∖U die Menge dieser Knoten. Im Beispiel links ist diese blau eingefärbt.
Da U eine Knotenüberdeckung ist und alle Elemente in L′ nicht selbst in U liegen gilt N(L′)⊆U∩R.
L′={C}N(L′)={Z}U∩R={Z}
Für den Beweis der Rückrichtung wird angenommen, dass ∣S∣≤∣N(S)∣,∀S⊆L gilt.
Dies muss auch für die Menge L′ gelten, sodass wir ∣L′∣≤∣N(L′)∣≤∣U∩R∣ erhalten.
Die Menge U kann mithilfe der Partition in zwei disjunkte Mengen aufgeteilt werden:
∣U∣=∣U∩L∣+∣U∩R∣
Weil ∣L′∣≤∣U∩R∣ kann ∣U∣≥∣U∩L∣+∣L′∣ geschlussfolgert werden.
Kombiniert man dies mit der Definition von L′, erhält man ∣U∣≥∣L∣.
L′={C}N(L′)={Z}U∩R={Z}
Da U minimal ist, gilt aber auch ∣U∣≤∣L∣.
Zusammengenommen mit der Erkenntnis der letzten Folie ergibt sich also ∣U∣=∣L∣.
Da der Satz von König besagt, dass die Größe einer minimalen Knotenüberdeckung der Größe eines kardinalitätsmaximalen Matchings entspricht, muss ein Matching der Größe ∣L∣ existieren.
Dieses Matching ist also L-überdeckend.□
Falls ∣L∣=∣R∣, kann der Heiratssatz dafür verwendet werden, die Existenz eines perfekten Matchings zu beweisen oder zu widerlegen:
Soll die Existenz belegt werden, muss bewiesen werden, dass die Kardinalität der Nachbarschaft jeder Teilmenge von L mindestens gleich groß ist wie die der Teilmenge selbst.
Soll die Existenz widerlegt werden, reicht es ein Gegenbeispiel zu finden, also eine Teilmenge, deren Kardinalität kleiner ist als die der Nachbarschaft.