Einleitung

Hier geht es um eine etwas umgangssprachlicher formulierte Version meiner Masterarbeit. Wem das nicht akkurat genug ist, der liest sich die Masterarbeit hier durch.

Der Algorithmus basiert auf einem Paper von Kezdy und McGuinness und kann entscheiden, ob ein Graph K₅-Minor-frei ist.

Das ist insofern interessant, als dass einige Probleme auf K₅-Minor-freien Graphen bedeutend besser gelöst werden können oder zumindest beschleunigt werden, wenn die K₅-Minoren bekannt sind. Beispielsweise ist das Max-Cut Problem auf K₅-Minor-freien Graphen nicht mehr NP-schwer, sondern in Polynomialzeit lösbar.

Die Basis für die Berechnung bildet eine Planaritätsprüfung, denn über diese können K₅-, leider aber auch K_3,3-Minoren gefunden werden. Wird ein K_3,3-Minor gefunden, wird dieser entfernt und die Prüfung auf dem dadurch entstehenden Teilgraph wiederholt bis alle Teilgraphen planar sind oder ein K₅-Minor gefunden wurde.

Inhaltsverzeichnis

1. Graphen, Planarität, Minoren?
2. Planaritätsprüfung
3. Der Algorithmus von Kezdy & McGuinness
4. Sequenzieller Algorithmus zum Finden von K₅-Minoren

Graphen, Planarität, Minoren?

Schnell ein paar Begrifflichkeiten erklärt: Ein Graph besteht aus einer Menge von Knoten, die über eine Menge von Kanten paarweise miteinander verbunden sind. Ein Pfad ist eine Menge von aufeinander folgenden Kanten im Graph, die wir durchlaufen können. Beispielsweise besteht beim Haus vom Nikolaus die Herausforderung darin, das Haus durch einen einzelnen Pfad zu zeichnen (kleiner Tipp dazu: Start- und Endpunkt müssen immer die Knoten b und c sein).

Wo wir gerade beim Zeichnen sind: Ein Graph ist dann planar, wenn es eine Möglichkeit gibt, ihn etwa auf einem Blatt Papier zu zeichnen, sodass sich keine Kanten kreuzen. Das Haus vom Nikolaus ist z.B. planar, weil wir es so zeichnen können:

Kuratowski hat festgestellt, dass Graphen dann planar sind, wenn sie keine K₅- oder K_3,3-Subdivisionen als Teilgraphen enthalten. Die als K₅ bzw. K_3,3 bezeichneten Graphen sind die beiden kleinstmöglichen Graphen, die nicht planar sind:

Wenn einer dieser beiden in einem größeren Graphen G in irgendeiner Form enthalten ist, kann folglich G auch nicht planar sein.

Weil es besser zum Thema passt, nehmen wir allerdings nicht den Satz von Kuratowski, sondern eine äquivalente Formulierung von Wagner: Ein Graph ist planar, wenn er weder einen K₅- noch einen K_3,3-Minor enthält. Was ist also ein Minor? Es gibt drei Operationen, die wir beliebig oft auf einem Graph anwenden dürfen, um einen Minor daraus zu erzeugen:

1. Eine Kante löschen
2. Einen Knoten löschen, an dem keine Kanten mehr hängen
3. Zwei Knoten verschmelzen, sofern sie mit einer Kante verbunden sind (doppelte Kanten werden entfernt)

Hier eine Animation von Wikipedia, die zeigt, dass der Graph einen K_3,3-Minor hat:

Ungünstiger Weise steigt die Anzahl der möglichen Minoren exponentiell mit der Knoten- und Kantenanzahl. Durch eine Planaritätsprüfung finden wir aber zumindest heraus, ob der Graph planar (K₅-Minor-frei) ist oder einen K₅-Minor enthält…oder ob er einen K_3,3-Minor enthält. Diesen Fall müssen wir später gesondert behandeln.

Planaritätsprüfung

Hopcroft und Tarjan haben bereits 1974 einen Algorithmus vorgestellt, der in linearer Zeit einen Graph auf Planarität prüft und eine planare Darstellung liefern kann. Im Wesentlichen wird der Graph dafür durch eine Tiefensuche als Baum in der Ebene dargestellt (Bäume sind immer planar). Alle übrigen Kanten führen zu einem Kreis und können entweder links oder rechts (Abb. 5 ist um 90° gedreht, also oberhalb/unterhalb) am bisher eingebetteten Baum hinzugefügt werden. Eventuell wechseln diese Kanten beim Hinzufügen weiterer Kanten von links nach rechts oder umgekehrt. Sobald eine Kante nicht mehr auf diese Art hinzugefügt werden konnte, muss laut dem Theorem von Kuratowski ein K_3,3 oder K₅ vorliegen. Andernfalls ist der Graph planar. Der tatsächliche Algorithmus ist etwas komplexer, für uns ist jedoch lediglich interessant zu wissen, dass wir eine Menge an Knoten und Kanten zurückbekommen, die zu einem nicht-planaren Teilgraph führen.

Der Algorithmus von Kezdy & McGuinness

Die Planaritätsprüfung findet also einen K₅-Minor, einen K_3,3-Minor oder der Graph ist planar. Wie bereits zuvor festgestellt, können wir im ersten und letzten Fall bereits eindeutig sagen, ob der Graph K₅-Minor-frei ist. Wird dagegen ein K_3,3-Minor gefunden, wird dieser entfernt und der Algorithmus rekursiv auf die dadurch entstehenden Minoren angewendet. Das funktioniert grundlegend so, dass wir ein paar Knoten des K_3,3-Minoren entfernen, damit wir bei der erneuten Planaritätsprüfung nicht noch einmal darüber stolpern. Wir sorgen dafür, dass alle dadurch entstehenden Komponenten nicht nur Minoren unseres ursprünglichen Graphs sind, sondern dass das zusätzlich genau die Minoren sind, die einen K₅-Minor enthalten können. Umgekehrt ist der Graph also K₅-Minor-frei, wenn alle seine so erzeugten Minoren K₅-Minor-frei sind. Schauen wir uns also an, wie wir einen K_3,3-Minor entfernen können. Dazu bilden wir augmentierte Komponenten:

Oben ist ein Graph mit einem K_3,3-Minor dargestellt. Die Knoten d, e und f liegen jeweils in Teilgraphen, welche nur angedeutet wurden. Unten ist eine der 3 augmentierten Komponenten dargestellt, welche ein gültiger Minor des oberen Graphen ist. Die roten Kanten sind durch Verschmelzungen von Knoten entstanden. Etwa erhält man die Kante zwischen a und b, indem im oberen Graph der Knoten b mit dem gesamten Teilgraph e verschmolzen wird. Neben der dargestellten augmentierten Komponente gibt es 2 weitere, die nahezu identisch sind, aber statt dem Teilgraph d die Teilgraphen e bzw. f enthalten.

Allgemein werden augmentierte Komponenten für eine Menge an Knoten (im Beispiel a, b und c) wie folgt gebildet:

1. Die Knoten werden entfernt, wodurch mehrere voneinander getrennte Komponenten entstehen (die Teilgraphen d, e und f).
2. Die entfernten Knoten werden untereinander verbunden (rote Kanten) und anschließend zu jedem der Teilgraphen hinzugefügt.

Wenn wir einen Graph durch 3 Knoten in augmentierte Komponenten aufteilen, ist es wichtig, dass dadurch mindestens 3 Komponenten entstehen. Denn wenn zum Beispiel die Knoten a, b und c entfernt werden, der Graph danach aber nicht in 3 getrennte Teilgraphen zerfällt und das gleiche für den Fall eintritt, wenn wir die Knoten d, e und f entfernen, dann können wir aus dem gefundenen K_3,3-Minor mit den zusätzlichen Pfaden einen K₅-Minor bilden:

Wir wissen jetzt, wie wir K_3,3-Minoren bei der Planaritätsprüfung behandeln können, müssen allerdings die beiden Ausnahmen beachten:

1. Der K_3,3-Minor ist Teil eines K₅-Minors. Teilen wir den Graph entlang des K_3,3s in augmentierte Komponenten, machen wir ggf. genau diesen K₅-Minor kaputt. Also suchen wir nach ein paar zusätzlichen Pfaden außerhalb des K_3,3-Minors, um das zu prüfen. Hier gibt es eine Menge an verschiedenen Fällen, die wir uns nicht alle einzeln anschauen werden - das Grundprinzip ist das aus Abb. 7.
2. Der Graph ist eine Art Rad mit 8 Knoten (s. Abb. 8). Dieser spezielle Graph wird W genannt und ist eine Sackgasse für unseren Algorithmus. Auf ihn treffen zwar die Bedingungen für das Aufteilen in augmentierte Komponenten zu, allerdings enthält W zu wenig Pfade dafür. Aber W enthält auch keinen K₅-Minor also können wir unseren Algorithmus hier stoppen.

Langsam wird es kompliziert…denn zu den beiden Ausnahmen (und dem gesamten Algorithmus) sei erwähnt, dass wir ihn nur auf 3-zusammenhängenden Graphen ausführen. D.h. dass wir 2 beliebige Knoten aus unserem Graph entfernen können und er danach immer noch zusammenhängend ist.

Ist der Graph z.B. nur 2-zusammenhängend, gibt es mindestens ein Knotenpaar, dass wir entfernen können, sodass der Graph in mehrere getrennte Komponenten zerfällt. Solche Knoten werden als 2-Separator bezeichnet, weil es 2 Knoten sind und sie bei Entfernen den Graph separieren:

Warum führen wir unsere Suche nur auf 3-zusammenhängenden Graphen aus? Schauen wir uns einen Graph an, der in 2 Komponenten zerfällt, wenn wir 2 Knoten entfernen. Diese beiden Knoten können Knoten für einen K₅-Minor sein. Dieser muss allerdings entweder vollständig in der linken oder der rechten Komponente liegen. Denn durch die 2 Knoten verlaufen nur 2 Pfade, die die beiden Komponenten verbinden und das sind zu wenig für einen K₅. Was machen wir in diesem Fall? Wir bilden wir augmentierte Komponenten durch alle Knoten, die dafür sorgen, dass unser Graph nicht 3-zusammenhängend ist.

Sequenzieller Algorithmus zum Finden von K₅-Minoren

Hier eine Zusammenfassung, wie der Algorithmus auf einem Graph G arbeitet:

1. Gibt es einen 1-Separator in G, dann bilde damit augmentierte Komponenten und wende den Algorithmus rekursiv auf jede an.
2. Gibt es einen 2-Separator in G, dann bilde damit augmentierte Komponenten und wende den Algorithmus rekursiv auf jede an.
3. Planaritätstest:
   1. G ist planar: Gib zurück, dass kein K₅-Minor enthalten ist.
   2. G enthält einen K₅-Minor: Gib den K₅-Minor zurück und beende den Algorithmus.
   3. G enthält einen K_3,3-Minor: Weiter zu Schritt 4
4. G ist W: Gib zurück, dass kein K₅-Minor gefunden wurde. Andernfalls weiter zu Schritt 5
5. Wenn die roten Knoten einen 3-Separator bilden, sodass die blauen Knoten in jeweils eigenen Komponenten liegen, können wir daraus augmentierte Komponenten erzeugen und den Algorithmus ab Schritt 3 rekursiv auf diese Komponenten anwenden. (Analog für die blauen Knoten als 3-Separator)
6. Ist dieser Schritt erreicht, enthält G einen K₅-Minor bestehend aus dem K_3,3-Minor und dem Pfad, der zwei rote, sowie dem Pfad, der zwei blaue Knoten verbindet.

• K5
• K33
• Kuratowski
• Planarität
• Graphalgorithmen
• Minor
• Subdivision
• Kezdy
• McGuiness
• Wagner