Paarungen in Graphen

Paarungen in Graphen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich.

Definitionen

Sei GG=(V,E)(V,E) ein ungerichteter Graph ohne Mehrfachkanten und MM eine Teilmenge von EE. Man bezeichnet MM als Paarung oder Matching von GG, wenn je zwei beliebige verschiedene Kanten e1e_{1} und e2e_{2} disjunkt sind, d.h. mit verschiedenen Knoten inzident sind. Ein Knoten von GG heißt von einer Paarung MM überdeckt, falls es eine Kante in MM gibt, die ihn enthält, d.h. die mit ihm inzident ist.
Eine Paarung MM von GG nennt man maximal, wenn man keine weitere Kante ee aus EE zu MM hinzufügen kann, so dass MM zusammen mit ee eine Paarung ist. Gibt es in GG keine Paarung, die mehr Elemente als MM enthält, so nennt man MM größte Paarung. Ist jeder Knoten von VV Element einer Kante von MM (also von MM überdeckt), so nennt man MM eine perfekte Paarung. Die Anzahl Elemente einer größten Paarung nennt man Paarungszahl bzw. Matchingzahl.
Einen kk-regulären Teilgraphen von GG nennt man einen k-Faktor, wenn er alle Knoten von GG enthält. Die Kantenmenge eines 1-Faktors ist also offensichtlich eine perfekte Paarung.
In kantengewichteten Graphen definiert man die Größe einer Paarung über die Summe ihrer Kantengewichte. Als größte gewichtete Paarung eines Graphen GG bezeichnet man dann eine Paarung, die diesen Wert maximiert.
In gerichteten Graphen und solchen mit Mehrfachkanten werden Paarungen nicht betrachtet. Ersteres, weil es bei Paarungen nicht auf die Richtung der Kanten ankommt, letzteres, weil von den Mehrfachkanten nur eine für eine Paarung in Frage kommt. Es spielt also keine Rolle, ob man den Graphen betrachtet, der entsteht, wenn man die Vielfachheiten von Mehrfachkanten auf 1 reduziert oder ob man den Originalgraph mit Mehrfachkanten betrachtet.
Die nachfolgenden Definitionen dienen dem Verständnis der unten gegebenen Aussagen und Sätze.
Einen Pfad PP=v1v_{1},...,vkv_{k} in einem Graphen GG, bezeichnet man als alternierend bezüglich einer Paarung MM von GG, wenn für jedes ii aus {1,...,k2k-2} die Kante {vi,vi+1v_{i},v_{i+1}} genau dann zu MM gehört, wenn die Kante {vi+1,vi+2v_{i+1},v_{i+2}} nicht zu MM gehört, d.h. der Pfad PP führt abwechselnd über Kanten die zu MM gehören und solchen, die nicht zu MM gehören. Werden zusätzlich v1v_{1} und vkv_{k} nicht von MM überdeckt, so nennt man den Pfad PP augmentierend bzw. Verbesserungspfad.
Bezeichnet q(G)q(G) die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen GG=(V,E)(V,E), so nennt man def(G)(G):=qq(GG-SS)-|SS| für ein Teilmenge SS von VV Defekt von GG, falls qq(GG-UU)-|UU|≥qq(GG-SS)-|SS| für jede andere Teilmenge UU von VV gilt. GG-SS bzw. GG-UU bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von SS bzw. UU und ihre inzidenten Kanten aus GG löscht.

Beispiel

Matching_Beispiel_Qualifikationen.png
Abb. 1: Qualifikationen
Dem Arbeitsamt liegen vier Stellenangebote und ebenso viele Stellengesuche vor. Dabei haben einige Arbeitssuchende mehrere Berufe angegeben, für die sie qualifiziert sind. Zur Veranschaulichung der Ausgangssituation kann ein bipartiter Graph gezeichnet werden (Abb. 1): dabei steht jeder Knoten in der linken Teilmenge für einen Arbeitssuchenden und jeder in der rechten für eine offene Stelle. Ist ein Arbeitssuchender mit einem Stellenangebot mittels einer Kante verbunden, so bedeutet das, dass er für den entsprechenden Beruf qualifiziert ist. So ist z. B. Laura in der Lage, als Kellnerin oder Stewardess zu arbeiten; Eduard und Klaus sind beide gelernte Schlosser und konkurrieren um die offene Stelle.
Matching.png
Abb. 2: Paarung
Die Vermittlung von möglichst vielen Jobs ist ein Paarungs-Problem. Erneut werden die Stellengesuche und -angebote als Knoten eines bipartiten Graphen aufgefasst, diesmal stehen die Kanten jedoch für zugewiesene Jobs. Es sollen nun möglichst viele Kanten aus Abb. 1 übernommen werden, dabei darf an jedem Knoten allerdings höchstens eine Kante anliegen, denn natürlich kann für jedes Stellenangebot nur ein Bewerber angenommen werden, und jeder kann nur einen Job ausführen.
Kann der Mitarbeiter des Arbeitsamtes nicht alle Stellengesuche und -angebote bearbeiten, weil ihm nicht genug Zeit zur Verfügung steht, so vermittelt er unter Umständen weniger Jobs, als möglich wären. Im Beispiel (Abb. 2) wurden nur zwei Jobs vermittelt, und zwar soll Eduard Schlosser werden und Laura Stewardess. Man spricht dennoch von einer Paarung (Matching), denn niemandem wurden zwei Jobs vermittelt, und keine Arbeitsstelle wurde zwei Bewerbern zugewiesen.
Maximales_Matching.png
Abb. 3: Größte Paarung
Doch auch wenn das Arbeitsamt alle Möglichkeiten berücksichtigt, ist es in diesem Fall nicht möglich, allen Arbeitssuchenden einen Job zu vermitteln. Die größte Paarung ist also in diesem Fall keine perfekte Paarung. Die Gründe dafür sind, dass die beiden gelernten Schlosser um eine einzige Stelle konkurrieren, während Maria entweder Taxifahrerin oder Kellnerin wird und somit eine Stelle offen bleibt. Dass eine perfekte Paarung nicht möglich ist, lässt sich mit dem Heiratssatz von Hall (siehe unten) beweisen.
Das Arbeitsamt kann sich nun etwa entscheiden, Eduard die Stelle als Schlosser und Maria die als Taxifahrerin zu vermitteln (Abb. 3). Hier sieht man, dass es in einem Graphen mehr als eine größte Paarung geben kann: eine andere größte Paarung würde z. B. so aussehen, dass Klaus den Schlosserjob bekommt.
Perfektes_Matching.png
Abb. 4: Perfekte Paarung
Nun kontaktiert das Arbeitsamt Klaus und berichtet ihm von dem Problem. Um nicht arbeitslos zu werden, erklärt dieser sich bereit, statt als Schlosser als Taxifahrer zu arbeiten. Dadurch ist es möglich, jedem Arbeitssuchenden eine Stelle zu vermitteln (Abb. 4). Graphentheoretisch betrachtet, inzidiert also jeder Knoten mit genau einer Kante. Man spricht von einer perfekten Paarung. Eine perfekte Paarung ist nur dann möglich, wenn genauso viele Stellengesuche wie -angebote vorliegen, und, wie wir gesehen haben, selbst dann nicht immer.

Wichtige Aussagen und Sätze

Es lässt sich leicht zeigen, dass eine maximale Paarung eines Graphen GG höchstens so viele Kanten wie eine größte Paarung in GG enthält (jede größte Paarung ist auch eine maximale Paarung). Andererseits enthält eine größte Paarung in GG höchstens doppelt so viele Kanten, wie eine maximale Paarung.
Von Berge (1957) stammt ein leicht beweisbarer Satz, der besagt, dass eine Paarung MM von einem Graphen GG genau dann eine größte Paarung von GG ist, wenn es keinen augmentierenden Pfad zu MM gibt. Mit Hilfe dieses Satzes lässt sich leicht ein polynomieller Algorithmus entwerfen, der zu einem gegebenen Graphen ein größtes Matching findet, indem man nach augmentierenden Pfaden in einem Graphen sucht.
In bipartiten Graphen lässt sich mit dem Algorithmus von Hopcroft und Karp in OO(√nm) eine größte Paarung finden. Der Algorithmus basiert auf der Idee simultan mehrere Verbesserungspfade zu finden.
Man zeigt leicht, dass die Knotenüberdeckungszahl eines Graphen mindestens so groß ist, wie seine Paarungszahl, aber höchstens so groß wie das 2-fache seiner Paarungszahl. Für bipartite Graphen konnte König (1931) zeigen, dass die Paarungszahl genau der Knotenüberdeckungszahl entspricht. Dies impliziert insbesondere polynomielle Algorithmen zur Bestimmung der Knotenüberdeckungszahl und in Folge auch der Stabilitätszahl eines bipartiten Graphen. Im allgemeinen sind diese Probleme NP-schwer.
Der so genannte Heiratssatz von Hall (1935) besagt, dass in bipartiten Graphen GG mit Bipartition {A,BA,B} genau dann eine Paarung MM existiert, die jeden Knoten aus AA überdeckt, falls für jede Teilmenge SS von AA gilt, dass ihre Nachbarschaft mindestens so groß ist wie SS selbst. Der Name Heiratssatz rührt daher, dass es nach diesem Satz möglich ist, jede Frau zu verheiraten, falls es für jede Gruppe von Frauen mehr Männer gibt, die sich für wenigstens eine der Frauen in der Gruppe interessieren.
Der Satz von Hall hat einige leicht ableitbare Konsequenzen. Da in regulären bipartiten Graphen gilt, dass |AA|=|BB|, kann man leicht zeigen, dass auch die Heiratsbedingung |N(S)N(S)|≥|S| immer erfüllt ist, so dass jeder bipartite reguläre Graph eine perfekte Paarung besitzt. Diesen Satz konnte König schon 1916 beweisen (damals natürlich unabhängig vom Heiratssatz). Mit Induktion über kk folgt dann auch leicht, dass ein kk-regulärer Graph kk disjunkte Paarungen besitzt, die zusammengenommen seine Kantenmenge ergeben. Hier wird der Sinn der Definition eines kk-Faktors deutlich.
In Graphen mit ungerader Knotenzahl gibt es offensichtlich keine perfekten Paarungen, da jede Paarung eine gerade Anzahl Knoten überdeckt. Die Defektformel von Berge (1958) besagt jedoch, dass das 2-fache der Paarungszahl eines Graphen GG der Anzahl Knoten von GG abzüglich seines Defektes entspricht. Daraus leitet sich leicht ein Satz von Tutte (1947) ab, der besagt, dass ein Graph GG=(V,E)(V,E) genau dann eine perfekte Paarung besitzt, wenn für jede Teilmenge SS von VV gilt: qq(GG-SS)≤|SS|. Ebenfalls leicht folgt der schon 1891 von Petersen damals sehr aufwändig bewiesene Satz, dass ein kubischer Graph mit höchstens zwei trennenden Kanten ein perfektes Matching besitzt.
In Graphen mit sehr vielen Kanten (sog. dichte Graphen) gibt es meistens auch eine (fast) perfekte Paarung. Algorithmisch interessant ist der Spezialfall, dass der Graph viele (fast) perfekte Paarungen besitzt und das Rechenverfahren die Aufgabe hat, eine solche Paarung zu finden.
 
 

Ich stimme mit der Mathematik nicht überein. Ich meine, daß die Summe von Nullen eine gefährliche Zahl ist.

Stanislaw Jerzy Lec

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Paarungen in Graphen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе