Durchlaufbarkeit von Graphen

Definitionen

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.

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}). 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.

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 auch Eulerweg, Eulerkreis oder Eulertour. Anschaulich bedeutet die Definition, dass W jede Kante genau einmal benutzt. Falls ein Graph G einen Eulerweg enthält, so nennt man G eulersch.

Für Graphen mit Mehrfachkanten kann man die Begriffe Eulerweg bzw. eulersch ebenfalls definieren, die Definition ist dann aber technisch etwas schwieriger (eine Kante muss entsprechend ihrer Vielfachheit mehrfach benutzt werden). Da es eine einfache Reduktion auf Graphen ohne Mehrfachkanten gibt, so dass der resultierende Graph ohne Mehrfachkanten genau dann eulersch ist, wenn es der originale Graph mit Mehrfachkanten ist, verzichten wir hier auf die Definition. Die Reduktion ersetzt lediglich Mehrfachkanten {v,w} bzw. (v,w) durch neue Knoten (entsprechend ihrer Vielfachheit) und verbindet diese (im gerichteten Fall unter Berücksichtigung ihrer Richtung) mit v und w.

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.

graphentheoretische Probleme und ihre algorithmische Komplexität

Die Probleme für einem gegeben Graphen zu entscheiden, ob dieser einen Hamiltonpfad bzw. Hamiltonkreis besitzt 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. Noch besser ist die Cristofides-Heuristik mit Approximationsgüte 1,5. Hierbei wird zusätzlich zur MST-Heuristik eine größte gewichtete Paarung auf dem minimal spannenden Baum berechnet und der Umlauf basierend auf dieser Paarung etwas geschickter gewählt.

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 Algorithmen mit linearer Laufzeit, der im Wesentlichen auf Tiefensuche basiert. Die Algorithmen machen sich vor allem die obigen Aussagen zur Charakterisierung eulerscher Graphen zu nutze.