Paarungen in Graphen

Paarungen in Graphen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich.

Sei $G$=$(V,E)$ ein ungerichteter Graph ohne Mehrfachkanten und $M$ eine Teilmenge von $E$. Man bezeichnet $M$ als Paarung oder Matching von $G$, wenn je zwei beliebige verschiedene Kanten $e_{1}$ und $e_{2}$ disjunkt sind, d.h. mit verschiedenen Knoten inzident sind. Ein Knoten von $G$ heißt von einer Paarung $M$ überdeckt, falls es eine Kante in $M$ gibt, die ihn enthält, d.h. die mit ihm inzident ist.

Eine Paarung $M$ von $G$ nennt man maximal, wenn man keine weitere Kante $e$ aus $E$ zu $M$ hinzufügen kann, so dass $M$ zusammen mit $e$ eine Paarung ist. Gibt es in $G$ keine Paarung, die mehr Elemente als $M$ enthält, so nennt man $M$ größte Paarung. Ist jeder Knoten von $V$ Element einer Kante von $M$ (also von $M$ überdeckt), so nennt man $M$ eine perfekte Paarung. Die Anzahl Elemente einer größten Paarung nennt man Paarungszahl bzw. Matchingzahl.

Einen $k$-regulären Teilgraphen von $G$ nennt man einen k-Faktor, wenn er alle Knoten von $G$ 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 $G$ 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 $P$=$v_{1}$,...,$v_{k}$ in einem Graphen $G$, bezeichnet man als alternierend bezüglich einer Paarung $M$ von $G$, wenn für jedes $i$ aus {1,...,$k-2$} die Kante {$v_{i},v_{i+1}$} genau dann zu $M$ gehört, wenn die Kante {$v_{i+1},v_{i+2}$} nicht zu $M$ gehört, d.h. der Pfad $P$ führt abwechselnd über Kanten die zu $M$ gehören und solchen, die nicht zu $M$ gehören. Werden zusätzlich $v_{1}$ und $v_{k}$ nicht von $M$ überdeckt, so nennt man den Pfad $P$ augmentierend bzw. Verbesserungspfad.

Bezeichnet $q(G)$ die Anzahl der Zusammenhangskomponenten mit ungerader Anzahl Knoten in einem Graphen $G$=$(V,E)$, so nennt man def$(G)$:=$q$($G$-$S$)-|$S$| für ein Teilmenge $S$ von $V$ Defekt von $G$, falls $q$($G$-$U$)-|$U$|≥$q$($G$-$S$)-|$S$| für jede andere Teilmenge $U$ von $V$ gilt. $G$-$S$ bzw. $G$-$U$ bezeichnet dabei den Graphen, der entsteht, wenn man die Knoten von $S$ bzw. $U$ und ihre inzidenten Kanten aus $G$ löscht.

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.

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.

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.

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.

Es lässt sich leicht zeigen, dass eine maximale Paarung eines Graphen $G$ höchstens so viele Kanten wie eine größte Paarung in $G$ enthält (jede größte Paarung ist auch eine maximale Paarung). Andererseits enthält eine größte Paarung in $G$ höchstens doppelt so viele Kanten, wie eine maximale Paarung.

Von Berge (1957) stammt ein leicht beweisbarer Satz, der besagt, dass eine Paarung $M$ von einem Graphen $G$ genau dann eine größte Paarung von $G$ ist, wenn es keinen augmentierenden Pfad zu $M$ 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 $O$(√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 $G$ mit Bipartition {$A,B$} genau dann eine Paarung $M$ existiert, die jeden Knoten aus $A$ überdeckt, falls für jede Teilmenge $S$ von $A$ gilt, dass ihre Nachbarschaft mindestens so groß ist wie $S$ 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 |$A$|=|$B$|, kann man leicht zeigen, dass auch die Heiratsbedingung |$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 $k$ folgt dann auch leicht, dass ein $k$-regulärer Graph $k$ disjunkte Paarungen besitzt, die zusammengenommen seine Kantenmenge ergeben. Hier wird der Sinn der Definition eines $k$-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 $G$ der Anzahl Knoten von $G$ abzüglich seines Defektes entspricht. Daraus leitet sich leicht ein Satz von Tutte (1947) ab, der besagt, dass ein Graph $G$=$(V,E)$ genau dann eine perfekte Paarung besitzt, wenn für jede Teilmenge $S$ von $V$ gilt: $q$($G$-$S$)≤|$S$|. 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.