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 schlichter Graph ist,
(v_i,v_i+1) ist Element von E, falls G ein gerichteter Graph ist,
E({v_i,v_i+1})>0, falls G ein Multigraph ist,
E((v_i,v_i+1))>0, falls G ein gerichteter Multigraph ist,

d.h. v_i und v_i+1 sind durch eine (gerichtete) Kante verbunden.

W bezeichnet man dann 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.
Zykel, 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, Zykel und Pfad in einem Graphen G ist also auch ein Weg und jeder Kreis ist auch ein Zykel in G.

Falls W Pfad bzw. Kreis ist, und alle Knoten aus V enthält, so nennt man W auch Hamiltonpfad bzw. Hamiltonkreis. Falls ein Graph G einen Hamiltonkreis besitzt, so nennt man G hamiltonisch.

Falls W ein Zykel in einem Graphen G ohne Mehrfachkanten ist (letzteres bedeutet G ist kein Multigraph), 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 Zykels (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.

Beispiele

kommen später

Aussagen und Sätze

Für ungerichtete Graphen gilt folgender Satz.

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

G ist eulersch,
G ist zusammenhängend und jeder Knoten hat geraden Grad (Graphentheorie).
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:

G ist eulersch,
G ist stark zusammenhängend und für jedem Knoten sind Eingangsgrad und Ausgangsgrad äquivalent.
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 einfache Algorithmen mit linearer Laufzeit, der im wesentlichen auf einer Tiefensuche basiert.