Durchlaufbarkeit von Graphen

Definitionen

Sei G=(V, E) ein (gerichteter) Graph ohne Mehrfachkanten. Falls E ein Zyklus in G ist, und für jede Kante {v_a,v_b} bzw. (v_a,v_b) gilt, dass es genau ein i aus {1,...,n} gibt, so dass v_a=v_i und v_b=v_j, wobei j=i+1, falls i≠n und j=0 sonst, so nennt man E Eulerkreis oder Eulertour. Anschaulich bedeutet die Definition, dass W jede Kante genau einmal benutzt. Falls ein Graph G einen Eulerkreis enthält, so nennt man G eulersch. Beim Eulerweg muss der alle Kanten benutzende Kantenzug nicht geschlossen sein.

Sei G=(V, E) ein (gerichteter) Graph ohne Mehrfachkanten. Ist H ein Pfad bzw. Kreis, der alle Knoten aus V enthält, so nennt man W Hamiltonpfad bzw. Hamiltonkreis. Falls ein Graph G einen Hamiltonkreis besitzt, so nennt man G hamiltonisch. Das Problem zu entscheiden, ob ein gegebener Graph einen Hamiltonpfad besitzt, bzw. ob er hamiltonisch ist, nennt man Hamiltonpfad-Problem bzw. Hamiltonkreis-Problem.

In vollständigen Graphen mit Kantengewichten bezeichnet man einen Hamiltonkreis als Traveling-Salesman-Tour. Das Problem, zu einem solchen Graphen zu entscheiden, ob eine Traveling-Salesman-Tour der Länge höchstens k existiert, wobei k eine beliebige reelle Zahl ist, bezeichnet man als Problem des Handlungsreisenden bzw. Traveling-Salesman-Problem oder abgekürzt TSP. Neben diesem Entscheidungsproblem gibt es noch das Optimierungsproblem das kleinste k zu bestimmen, für das eine Traveling-Salesman-Tour der Länge k existiert und das Suchproblem eine kürzeste Traveling-Salesman-Tour zu finden.

In der Praxis betrachtet man häufig nur Graphen, in denen die Kantengewichtsfunktion f die Dreiecksungleichung erfüllt, d.h. für drei beliebige verschiedene Knoten x, y, z aus V gilt f({x,y})+f({y,z})≥f({x,z}). Solche Graphen nennt man auch metrisch. Beschränkt man sich auf Graphen, in denen diese Bedingung erfüllt ist, so spricht man vom metrischen Traveling-Salesman-Problem. Zwei Speziallfälle sind das euklische Travelings-Salesman-Problem und das rectilineare Traveling-Salesman-Problem. Diese Fälle liegen vor, wenn es eine Funktion gibt, die den Knoten des Graphen einen Punkt in der euklidischen Ebene zuordnet, so dass die Kantengewichte gerade dem Abstand der zugeordneten Punkte in der Ebene nach L2-Norm (für euklidisches TSP) bzw. L1-Norm (für rectilineares TSP) entsprechen.

Graphen mit Mehrfachkanten werden hier nicht betrachtet, da es offensichtlich nicht auf die Vielfachheit der Kanten ankommt.

Anschauung

Das Traveling-Salesman-Problem ist sicher ein Problem, das viele Personen aus dem Alltag kennen. Es modelliert die Frage, wie man möglichst schnell oder billig mehrere Orte hintereinander besuchen kann und wieder zum Ausgangsort zurückkehrt. In der Praxis wird man dabei auch zulassen Orte mehrmals zu besuchen, wenn die Reise dadurch günstiger wird. Die für allgemeines TSP gegebene Einschränkung jeden Ort genau einmal zu besuchen ist also eher künstlich. Indem man gestattet Orte mehrmals zu besuchen, kann man das Problem immer als metrisches TSP modellieren (man bildet einfach den Distanzgraphen und ersetzt in einer Lösung die Kanten des Distanzgraphen durch die Pfade des Orginalgraphen). Wie unten dargestellt, ist dies vorteilhaft bei der algorithmischen Lösung des Problems.

wichtige Aussagen und Sätze

Für ungerichtete sind folgende Aussagen äquivalent:

G ist eulersch,
G ist zusammenhängend und jeder Knoten hat geraden Grad (Graphentheorie).
G ist zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten geschlossenen Kantenzügen.

Analog sind für gerichtete Graphen folgende Aussagen äquivalent:

G ist eulersch,
G ist stark zusammenhängend und für jedem Knoten sind Eingangsgrad und Ausgangsgrad äquivalent.
G ist stark zusammenhängend und die Kantenmenge von G ist die Vereinigung aller Kanten von paarweise disjunkten gerichteten geschlossenen Kantenzügen.

Sind x und y zwei nicht benachbarte Knoten, in einem ungerichteten Graphen G, deren Gradsumme d_G(x)+d_G(y) mindestens so groß wie die Anzahl der Knoten |V(G)| in G ist, so ist G hamiltonisch genau dann, wenn G+{x,y} hamiltonisch ist. Ist G₀,...,G_k eine Folge von ungerichteten Graphen, wobei G_i aus G_i-1 für jedes i aus {1,...,k} durch Hinzufügen einer Kante {x,y} mit d_{G_i-1}(x)+d_{G_i-1}(y)&ge|V(G_i-1)| entsteht und d_{G_k}(x)+d_{G_ik}(y)&le|V(G_i-1)| für jedes Paar in G_k nicht benachbarter Knoten x und y, so bezeichnet man G_k als Hamiltonabschluss von G₀. Ein weiterer Satz besagt, dass der Hamiltionabschluss für jeden Graphen eindeutig ist. Ein Graph ist daher genau dann hamiltonisch, wenn sein Hamiltonabschluss hamiltonisch ist.

Daraus lassen sich folgende hinreichender Bedingungen für hamiltonische Graphen ableiten. Unter anderem ist ein Graph G mit mindestens drei Knoten hamiltonisch falls:

d_G(x)+d_G(y)≥|V(G)| für alle {x,y} die nicht zu E(G) gehören oder
der Minimalgrad mindestens |V(G)|/2 ist oder
die Knotenzusammenhangszahl von G mindestens so groß wie die Stabilitätszahl von G ist.

Diese Aussagen sind scharf in dem Sinne, das es Gegenbeispiele bei minimal schwächeren Voraussetzungen gibt.

graphentheoretische Probleme und ihre algorithmische Komplexität

Für das Problem zu einem gegeben Graphen zu entscheiden, ob dieser eulersch ist, gibt es lineare Algorithmen, d.h. mit Worst-Case-Laufzeit (O(|V|+|E|)). Auch für das Finden einer Eulertour (sofern eine existiert) gibt es einen einfachen Algorithmus mit linearer Laufzeit, der im Wesentlichen auf Tiefensuche basiert. Die Algorithmen machen sich vor allem die obigen Aussagen zur Charakterisierung eulerscher Graphen zu nutze.

Die Probleme Hamiltonpfad und Hamiltonkreis sind NP-vollständig. Entsprechend schwierig gestaltet es sich dann auch zusätzlich einen Hamiltonpfad bzw. einen Hamiltonkreis in einem Graphen zu finden, sofern dieser existiert.

Das Traveling-Salesman-Problem ist in all seinen Varianten (Entscheidungs-, Optimierungs- und Suchproblem) NP-schwer. Es bleibt selbst dann NP-schwer, wenn man sich auf metrisches TSP oder sogar noch spezieller auf euklidisches oder rectilineares TSP beschränkt. Es gibt aber verschiedene polynomielle Algorithmen (Heuristiken) für das Problem. Die einfachste ist die so genannte Nearest-Neighbor-Heuristik (zu deutsch Nächster-Nachbar-Heuristik), die bei einem beliebigen Knoten beginnend den jeweils am nähesten noch nicht besuchten Nachbarn aufsucht und so eine Traveling-Salesman-Tour generiert. Die Güte der so erzeugten Tour kann aber beliebig schlecht werden. Für metrisches TSP gibt es zwei bessere Heuristiken. Die Minimum-Spanning-Tree-Heuristik kurz auch MST-Heuristik genannt, liefert eine Approximationsgüte mit dem Faktor 2, d.h. die gefundene Traveling-Salesman-Tour ist höchstens doppelt so lang wie die kürzeste. Dazu berechnet sie zunächst einen minimal spannenden Baum und erzeugt dann einen Umlauf um diesen (Verdopplung der Kanten, finden einer Eulertour in dem entstandenen eulerschen Graphen und ersetzen benachbarter Kanten, falls ihr gemeinsamer Nachbar in der Eulertour mehr als einmal besucht wird). Noch besser ist die Cristofides-Heuristik mit Approximationsgüte 1,5. Hierbei wird statt der Verdopplung der Kanten zusätzlich zur MST-Heuristik eine kleinste perfekte Paarung auf den Knoten ungeraden Grades im minimal spannenden Baum berechnet, um einen eulerschen Graphen zu erzeugen.