Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Matchings in bipartiten Graphen

Beispiel 1: Im Dorf gibt es elf vereinsaktive Einwohner, aber neun Vereine. Im Taubenzüchterverein sind A, C, I und J. Im Eisenbahnverein sind B, D, I und K. Im Briefmarkenverein sind C, E und F. Im Schützenverein sind A, E, H. Bei den Anonymen Alkoholikern sind B, H und J. Im Fussballclub 1890 sind E, F und G. Im Turnverein sind E, F, G, H. Im Männerchor sind F, G und H (zur Zeit nur ein Trio). Und schließlich bilden E, F, G und H den Computerclub.
(a) Zu einer Sitzung wegen dem geplanten gemeinsamen Vereinshaus soll je ein Vertreter aus einem Verein abgeordnet werden, aber niemand soll für zwei Vereine sprechen. Ist dies möglich?
(b) Einen Tag vor der Sitzung wandert G nach Amerika aus. Ist die Sitzung immer noch möglich? 		Probieren Sie es: Durch Anklicken der Kreise werden Vertreter ausgewählt bzw. abgewählt.
Leider zeigt Ihr Brouwser keine Java Applets an.

Beispiel 2: 20 StudentInnen sollen auf fünf Übungsgruppen (mit jeweils nur 4 Plätzen) aufgeteilt werden. Jede StudentIn darf zwei Wünschgruppen angeben. Die Wünsche verteilen sich folgendermaßen (dabei entsprechen die Spalten den StudentInnen):
Gruppe 1: ** * * **
Gruppe 2: **** ** **** ***
Gruppe 3: ** ** *** **
Gruppe 4: ** ** ***
Gruppe 5: *** **
Ist es möglich alle zufriedenzustellen?
Ein Bigraph modelliert Situationen bei denen wir eine (beliebige) Relation R Í A × B zwischen zwei disjunkten Mengen A und B haben. Wenn wir dann V := A È B setzen und Adj = {(a,b), (b,a) / a Î A, b Î B, (a,b) Î R} definieren, erhalten wir das schon erwähnte Konzept der bipartiten Graphen. Diese speziellen Graphen "sind" die oben definierten Bigraphen. Statt mit R werden wir im Folgenden immer mit der irreflexiven symmetrischen Relationen Adj auf V = A È B, bzw. gleich mit der Kantenmenge E arbeiten. Sei G = (V,E) ein bipartiter Graph mit Bipartition V = A È B. Wir verwenden folgende Begriffe:

  • Ein Teilmenge E' der Kantenmenge E eines Graphen G=(V,E) ist
    • ein Matching, wenn keine zwei dieser E'-Kanten eine gemeinsame Ecke haben, d.h. wenn jede Ecke in höchstens einer dieser E'-Kanten auftaucht,
    • Eine E-V-Überdeckung, falls jede Ecke in mindestens einer dieser E'-Kanten auftaucht.
  • Eine Teilmenge V' der Eckenmenge V ist
    • unabhängig, wenn keine zwei dieser V'-Ecken benachbart sind, d.h. jede Kante höchstens eine dieser V'-Ecken enthält.
    • V-E-Überdeckung, wenn jede Kante mindestens eine dieser V'-Ecken enthält.

Offenbar ist es einfach kleine Matchings oder unabhängige Mengen, und große E-V- oder V-E-Überdeckungen zu finden, wir sind aber an größten Matchings oder unabhängige Mengen und an kleinsten E-V- oder V-E-Überdeckungen interessiert. Solche Gebilde nennen wir optimal. Die jeweiligen Größen bezeichnen wir mit m, üEV, u, üVE.

Wir benötigen im Folgenden ein vorbereitendes Lemma über die Struktur von kleinsten Kanten-Ecken-Überdeckungen (1.), sowie einige Konstruktionen (2.-6.), mit denen man aus solchen optimalen Gebilden optimale Gebilde erhält:

  1. Sterne in üEV Sei E' eine kleinste Kanten-Ecken-Überdeckung. Keine zwei benachbarten Ecken haben (V,E')-Grad größer als 1, sonst wäre die Verbindungskante überflüssig, im Widerspruch zur Minimumität von E'. Also ist (V,E') die disjunkte Vereinigung von k Sternen, wobei ein Stern ein Baum mit einer zentralen Ecke und (mindestens einer) peripheren Ecken, die alle zur zentralen Ecke benachbart sind, ist. Jede Komponente von (V,E') ist ein Baum, hat also eine Kante weniger als Ecken. Somit ist die Komponentenzahl von (V,E') gleich |V| - |E'|.
  2. u üVE : Ist W eine (größte) unabhängige Eckenmenge, dann ist das Komplement V \ W eine (kleinste) Ecken-Kanten-Überdeckung und umgekehrt.
  3. üEV ® u : E' sei eine kleinste Kanten-Ecken-Überdeckung. W sei die Menge aller Ecken vom Grad 1 in (V,E'), deren (V,E')-Nachbar nicht (V,E')-Grad 1 hat (also die Menge der Endecken der echten Sterne). Keine der Nachbarn von W kann zu W hinzugefügt werden, wir fügen aber alle (V,E')-Nachbarn aller G-Nachbarn von Ecken aus W hinzu. In dieser Art fahren wir fort. Am Schluß ist W eine unabhängige Eckenmenge in G (sogar eine größte).
    Beweis: ..........
  4. u ® üEV : W sei eine größte unabhängige Eckenmenge in G. Nacheinander wählen wir nun für jedes w Î W einen Nachbarn f(w), falls möglich so, daß f(w) von allen bisher gewählten f(u) verschieden ist (falls das unmöglich ist, wählen wir f(w) irgendwie). Dann bildet E' = {wf(w)/w Î W} eine Kanten-Ecken-Überdeckung (sogar eine kleinste).
    Beweis: ......
  5. üEV ® m : E' sei eine kleinste Kanten-Ecken-Überdeckung. Sie hat die unter 1. beschriebene "Sterneform". Indem wir aus jeder Sternkomponente genau eine Kante auswählen erhalten wir offenbar ein Matching (sogar ein größtes).
  6. m ® üEV : E' sei ein größtes Matching in G. Für jede Ecke x außerhalb von E' sei f(x) ein beliebiger Nachbar. Dann ist E' È {xf(x)/x Î V \ V(E')} eine Kanten-Ecken-Überdeckung (sogar eine kleinste).
    Beweis:

Alle diese Konstruktionen können Sie in einem an verschiedenen bipartiten Graphen ausprobieren.

Aus 2. folgt die schon erwähnte Gleichung u = |V| - üVE.
Aus 3. und 4. folgt

u = üEV in endlichen bipartiten Graphen.
Diese Gleichung folgt auch aus dem Satz von Dilworth ( Wir definieren eine Ordnung auf V durch a £ b falls [a=b oder (a Î A, b Î B, und {a,b} Î E(G))]. Die unabhängigen Mengen in G sind genau die Antiketten in (V,£), während eineKanten-Ecken-Überdeckungen in G einer Partition von V durch (V,£)-Ketten entspricht ).
Aus 1., 5. und 6. folgt m = |V| - üEV in bipartiten Graphen.
Insgesamt erhalten wir:

Satz von König (1931) In jedem endlichen bipartiten Graphen ist die minimale Anzahl von Ecken, die jede Kante berühren gleich der Mächtigkeit eines maximalen Matchings.

Satz von Philip Hall (1935)
Heiratsversion: Sei G ein endlichen bipartiter Graph mit Bipartition V = A È B. Genau dann gibt es ein Matching der Mächtigkeit |A|, falls für jede natürliche Zahl k je k Elemente aus A mindestens k gemeinsame Nachbarn in B haben.
Vertreterversion: Zu einer Menge {Mi/i Î I} von Mengen ist ein Vertretersystem eine injektive Funktion f: I ® ÈiÎ I Mi, wobei für jedes i gilt: f(i) Î Mi. Genau dann gibt es ein Vertretersystem, falls für jede Teilmenge J von I gilt: | Èj Î J Mj | ³ |J|.
Beweis: Die eine Richtung ist einfach: Gibt es eine Teilmenge A' von A mit |NG(A')| < |A'|, dann kann kein Matching alle Ecken von A' enthalten, es also kein Matching der Mächtigkeit |A| geben.
Gibt es umgekehrt kein Matching der Mächtigkeit |A|, so ist nach obigem Satz von König üVE < |A|. V' sei eine Ecken-Kanten-Überdeckung mit |V'| = üVE. Dann liegt jeder Nachbar jeder Ecke von A \ V' in B Ç V', also NG(A \ V') Í B Ç V', also
|NG(A \ V')| £ |B Ç V'| = |V'| - |A Ç V'| = |A \ V'|.

Übungsaufgabe: Sei k £ n/2 für natürliche Zahlen n und k. A sei die Menge aller (k-1)-elementigen Teilmengen von {1,2,...,n}, B sei die Menge aller k-elementigen Teilmengen von {1,2,...,n}, und X Î A, Y Î B seien benachbart, falls X Í B ist. Zeigen Sie mit obigem Satz von Hall, daß der so entstandene bipartite Graph ein Matching der Mächtigkeit |A| hat.

Übungsaufgabe: Beweisen Sie damit den Satz von Sperner.

Wie finde ich größte Matchings?

Die einfachste Idee ist, Kanten hinzuzunehmen solange das möglich ist. Leider gerät man auf diese Art in Sackgassen, wie man im Beispiel links sehen kann. Obwohl wir keine Kante mehr hinzunehmen können ohne die Matchingeigenschaft zu verlieren, ist das gegebene Matching kein größtes.
Aus diese Sackgassen führen sogenannte Verbesserungswege heraus. Ein Weg x0, y0, x1, y1, ... , xk, yk ist ein Verbesserungsweg zu einem gegebenen Matching M, falls weder x0 noch y0 von einer Kante aus M überdeckt werden und y0x1, y1x2, ... yk-1xk Kanten von M sind. In so einem Fall eliminieren wir diese Kanten aus M und fügen x0y0, x1y1, ... , xkyk hinzu und erhalten ein grösseres Matching. Solange wir also Verbesserungswege finden, können wir die Matchings immer weiter vergrößern. Interessanterweise gilt auch die Umkehrung:
Wenn wir zu einem gegebenen Matching keine Verbesserungswege mehr finden können, ist das Matching größtmöglich!

Im ersten Applet können Sie solche Verbesserungswege suchen und, falls Sie einen (blau eingezeichneten) gefunden haben, das Matching vergrössern.

Die Suche nach Verbesserungswegen wird durch den Begriff des Verbesserungsbaums systematisiert. Zu einem gegebenen Matching M und einer nicht von M überdeckten Ecke x möchten wir alle Verbesserungswege suchen, die in x starten. Alle Ecken, die durch nicht-M-Kanten zu x benachbart sind sind die Kinder von x. Ein solches Kind y ist entweder nicht von M überdeckt (in dem Fall haben wir unseren Verbesserungsweg schon gefunden), oder liegt in genau einer M-Kante---die andere Ecke z dieser M-Kante ist dann das Kind von y. Die Kinder der Kindeskinder von x sind wieder alle noch nicht erfassten Ecken, die zu Kindeskinder durch Nicht-M-Kanten benachbart sind, u.s.w. Führt man diese Konstruktion zu Ende findet man genau dann ein KindeskKind von x, das nicht von M überdeckt ist, also einen Verbesserungsweg mit Anfang x, wenn so ein Weg existiert. Wir müssen also nur alle Verbesserungsbäume von nicht von M überdeckten Ecken durchchecken.
Im zweiten Applet können Sie Verbesserungsbäume (rot-blau) suchen, indem Sie auf Ecken klicken, die noch nicht vom Matching überdeckt wurden.

Beispiel 1 nach der Auswanderung von G können Sie im ausführlichen Applet als Graph D studieren. Tatsächlich ist so ein |A|-Matching nicht (mehr) möglich.

Erich Prisner
erstellt im Mai 2000.