Weg (Graphentheorie)

Definitionen

Sei G=(V, E) ein (gerichteter) (Multi-)Graph und W=(v₁,...,v_n) eine Folge von Knoten aus V, mit der Eigenschaft, dass für alle i aus {1,...,n-1} gilt:

• {v_i,v_i+1} ist Element von E, falls G ein ungerichteter Graph ohne Mehrfachkanten ist,
• (v_i,v_i+1) ist Element von E, falls G ein gerichteter Graph ohne Mehrfachkanten ist,
• E({v_i,v_i+1})>0, falls G ein ungerichteter Graph mit Mehrfachkanten ist,
• E((v_i,v_i+1))>0, falls G ein gerichteter Graph ohne Mehrfachkanten ist,

d.h. v_i und v_i+1 sind durch eine Kante verbunden. Dann bezeichnet man W als ungerichteten Weg in G, falls G ungerichtet ist, und als gerichteten Weg in G, falls G gerichtet ist. Den Knoten v₁ nennt man dann Startknoten von W und den Knoten v_n Endknoten von W. Ferner bezeichnet man W statt als Weg, spezieller als

• Pfad, falls alle Knoten in der Folge W voneinander verschieden sind, d.h. falls für alle i und j aus {1,...,n} gilt, dass v_i≠v_j, falls i≠j.
• Zyklus, falls Start- und Endknoten von W identisch sind, d.h. falls v₁=v_n.
• Kreis, falls nur Start- und Endknoten von W identisch sind, d.h. falls v₁=v_n und für alle i und j aus {1,...,n-1} gilt, dass v_i≠v_j, falls i≠j.

Bemerkung: Jeder Kreis, Zyklus und Pfad in einem Graphen G ist also auch ein Weg und jeder Kreis ist auch ein Zyklus in G. Wege, Pfade, Zykel und Kreise definiert man alternativ auch über Kantenzüge oder Teilgraphen.

In ungerichteten Wegen und Pfaden bezeichnet man den Startknoten meist ebenfalls als Endknoten. In Zyklen und Kreisen verwendet man die Bezeichnungen Startknoten und Endknoten meißt nicht.

Sind A und B Teilmengen von V, so bezeichnet man einen Weg als A-B-Weg, falls der Startknoten in A und der Endknoten in B liegt. Statt von einem {v}-{w}-Weg spricht man auch von einem v-w-Weg.

Zwei Wege W₁=(v_1,1,...,v_1,k) und W₂=(v_2,1,...,v_2,l) heißen kreuzungsfrei, kantendisjunkt oder einfach nur disjunkt, falls es kein Paar (i,j) mit i aus {2,...,k-2} und j aus {2,...,l-2} gibt, so dass v_1,i=v_2,j, d.h., wenn sie keine inneren Knoten gemeinsam haben. Eine Menge von Wegen nennt man kreuzungsfrei, kantendisjunkt oder disjunkt, wenn die Wege paarweise disjunkt sind. Zwei Wege W₁=(v_1,1,...,v_1,k) und W₂=(v_2,1,...,v_2,l) heißen kantendisjunkt, falls es kein Paar (i,j) mit i aus {1,...k-1} und j aus {1,...,l-1} gibt, so dass v_1,i=v_2,j und v_1,i+1=v_2,j+1. Eine Menge von Wegen nennt man kantendisjunkt, wenn die Wege paarweise kantendisjunkt sind. Eine Menge von a-B-Wegen nennt man einen a-B-Fächer, wenn die Wege paarweise nur den Knoten a gemeinsam haben.

Ein Zyklus oder Kreis heißt trivial, wenn er weniger als 3 Knoten enthält. Triviale Kreise oder Zyklen werden meißt nicht betrachtet.

Ein Kreis, der genau 3 Knoten enthält nennt man oft Dreieck. Ein Graph ohne Dreieck nennt man dann dreiecksfrei.

Falls W Pfad bzw. Kreis in G=(V,E) ist, und alle Knoten aus V enthält, so nennt man W auch Hamiltonpfad bzw. Hamiltonkreis. Falls G einen Hamiltonkreis besitzt, so nennt man G hamiltonisch.

Falls W ein Zyklus in einem Graphen G ohne Mehrfachkanten 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 W 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 auch eulersch.

In Graphen ohne Gewichten auf den Kanten bezeichnet man mit n-1 die Länge eines Weges (oder Pfades) und mit n die Länge eines Zyklus (oder Kreises) (v₁,...,v_n). Anschaulich zählt man also die Anzahl zugehöriger Kanten.

In kantengewichteten Graphen bezeichnet man als Länge eines Weges die Summe der Kantengewichte aller zugehörigen Kanten.

Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Fall der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich.

Als Abstand oder Distanz zweier Knoten bezeichnet man die Länge eines kürzsten Pfades zwischen diesen. Falls ein solcher nicht existiert, so setzt man den Abstand auf unendlich. Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Pfades abhängt. Im Extremfall gibt es sogar nur in eine Richtung einen gerichteten Pfad. Den größten Abstand zwischen zwei Knoten in einem Graphen G nennt man Durchmesser von G.

Beispiele

kommen später

wichtige Aussagen und Sätze

Für ungerichtete Graphen gilt folgender Satz.

Satz: Sei G ein Graph. Folgende Aussagen sind äquivalent:

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

Für gerichtete Graphen gilt folgender leicht modifizierter Satz.

Satz: Sei G ein Graph. Folgende Aussagen sind äquivalent:

1. G ist eulersch,
2. G ist stark zusammenhängend und für jedem Knoten sind Eingangsgrad und Ausgangsgrad äquivalent.
3. 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 gestalltet es sich dann auch zusätzlich einen Hamiltonpfad bzw. einen Hamiltonkreis in einem Graphen zu finden, sofern dieser existiert.

Für das Problem zu einem gegeben Graphen zu entscheiden, ob dieser eulersch ist, gibt es insbesondere wegen 2. Algorithmen mit linearer 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 einer Tiefensuche basiert.