Wege, Pfade, Zyklen und Kreise in Graphen

Wege, Pfade, Zyklen und Kreise sind Begriffe der Graphentheorie und beschreiben im Allgemeinen eine spezielle, zusammenhängende Folge von Knoten in einem Graphen. Da die Begriffe eng miteinander verwandt sind, werden sie in diesem Übersichtsartikel zusammen dargestellt.

Definitionen

Gerichtete und ungerichtete Wege

Sei G=(V,E)G = (V, E) ein (gerichteter) (Multi-)Graph und W=(v1,   ,vn)W = (v_1, \, \, \, , v_n) eine Folge von Knoten aus VV mit der Eigenschaft, dass für alle ii aus {1,   ,n−1}\{ 1, \, \, \, , n - 1 \} gilt:
  • Die Menge {vi,vi+1}\{ v_i, v_{i + 1} \} ist Element von EE, falls GG ein ungerichteter Graph ohne Mehrfachkanten ist.
  • Das Paar (vi,vi+1)(v_i, v_{i + 1}) ist Element von EE, falls GG ein gerichteter Graph ohne Mehrfachkanten ist.
  • E({vi,vi+1})>0E( \{ v_i, v_{i + 1} \} ) > 0, falls GG ein ungerichteter Graph mit Mehrfachkanten ist.
  • E({vi,vi+1})>0E( \{ v_i, v_{i + 1} \} ) > 0, falls GG ein gerichteter Graph mit Mehrfachkanten ist.
Das heißt viv_i und vi+1v_{i + 1} sind durch eine Kante verbunden. Dann bezeichnet man WW als ungerichteten Weg in GG, falls GG ungerichtet ist, und als gerichteten Weg in GG, falls GG gerichtet ist. Eine andere Bezeichnung für Weg ist Kantenfolge. Den Knoten v1v_1 nennt man Startknoten von WW und den Knoten vnv_n Endknoten von WW.

Pfade, Zyklen und Kreise

Einen Weg WW bezeichnet man als
  • Pfad, falls alle Knoten in der Folge WW voneinander verschieden sind, das heißt falls für alle ii und jj aus {1,   ,n}\{ 1, \, \, \, , n \} gilt, dass vi≠vjv_i \ne v_j, falls i≠ji \ne j.
  • Zyklus, falls Start- und Endknoten von WW identisch sind, das heißt falls v1=vnv_1 = v_n.
  • Kreis, falls nur Start- und Endknoten von WW identisch sind, das heißt falls v1=vnv_1 = v_n und v1,   ,vn−1v_1, \, \, \, , v_{n - 1} einen Pfad bilden, also für alle ii und jj aus {1,   ,n−1}\{ 1, \, \, \, , n - 1 \} gilt, dass vi≠vjv_i \ne v_j, falls i≠ji \ne j.
Bemerkung: Jeder Kreis, Zyklus oder Pfad in einem Graphen GG ist also auch ein Weg und jeder Kreis ist auch ein Zyklus in GG. Wege, Pfade, Zyklen und Kreise definiert man alternativ auch über Kantenzüge oder Teilgraphen. Gibt es einen Weg von Knoten uu zu Knoten vv in GG, so heißt vv von uu aus erreichbar (Erreichbarkeitsproblem in Graphen).
In ungerichteten Wegen und Pfaden bezeichnet man den Startknoten meist ebenfalls als Endknoten. In Zyklen und Kreisen verwendet man die Bezeichnungen Startknoten und Endknoten meist nicht.
Graphen mit Zyklen heißen zyklisch. Graphen ohne Zyklen heißen azyklisch. Ein Zyklus oder Kreis heißt trivial, wenn er weniger als drei Knoten enthält. Triviale Kreise oder Zyklen werden meist nicht betrachtet. Ein Kreis, der genau drei Knoten enthält nennt man oft Dreieck. Ein Graph ohne Dreieck nennt man dann dreiecksfrei.

A-B-Weg, v-w-Weg, a-B-Fächer

Sind AA und BB Teilmengen von VV, so bezeichnet man einen Weg als AA-BB-Weg, falls der Startknoten in AA und der Endknoten in BB liegt. Statt von einem {v}\{v\}-{w}\{w\}-Weg spricht man auch von einem vv-ww-Weg. Eine Menge von aa-BB-Wegen nennt man einen aa-BB-Fächer, wenn die Wege paarweise nur den Knoten aa gemeinsam haben.

Kreuzungsfrei, knotendisjunkt, kantendisjunkt

Zwei Wege W1=(v1,1,   ,v1,k)W_1 = (v_{1,1}, \, \, \, , v_{1,k}) und W2=(v2,1,   ,v2,l)W_2 = (v_{2, 1}, \, \, \, , v_{2,l}) heißen kreuzungsfrei, knotendisjunkt oder einfach nur disjunkt, falls es kein Paar (i,j)(i, j) mit ii aus {2,   ,k−2}\{ 2, \, \, \, , k - 2 \} und jj aus {2,   ,l−2}\{ 2, \, \, \, , l - 2 \} gibt, so dass v1,i=v2,jv_{1,i} = v_{2,j}, das heißt, wenn sie keine inneren Knoten gemeinsam haben. Eine Menge von Wegen nennt man kreuzungsfrei, knotendisjunkt oder disjunkt, wenn die Wege paarweise disjunkt sind. Zwei Wege W1=(v1,1,   ,v1,k)W_1 = (v_{1,1}, \, \, \, , v_{1,k}) und W2=(v2,1,   ,v2,l)W_2 = (v_{2,1}, \, \, \, , v_{2,l}) heißen kantendisjunkt, falls es kein Paar (i,j)(i, j) mit ii aus {1,   ,k−1}\{ 1, \, \, \, , k - 1 \} und jj aus {1,   ,l−1}\{ 1, \, \, \, , l - 1 \} gibt, so dass v1,i=v2,jv_{1,i} = v_{2,j} und v1,i+1=v2,j+1v_{1, i + 1} = v_{2, j + 1}. Eine Menge von Wegen nennt man kantendisjunkt, wenn die Wege paarweise kantendisjunkt sind.

Länge eines Weges (Zyklus, Kreises), Abstand

In Graphen ohne Gewichte auf den Kanten bezeichnet man mit n−1n - 1 die Länge eines Weges (oder Pfades) und mit nn die Länge eines Zyklus (oder Kreises) (v1,   ,vn)(v_1, \, \, \, , 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 einen kürzesten Weg von einem Knoten ss zu einem Knoten tt in einem Graphen bezeichnet man einen Weg von ss nach tt, dessen Länge minimal ist. Die Länge eines kürzesten Weges nennt man dann Abstand oder Distanz von ss nach tt. Falls kein Weg zwischen zwei Knoten existiert, so setzt man den Abstand auf unendlich. Man beachte, dass in gerichteten Graphen der Abstand von der Richtung des Weges abhängt. Insbesondere kann es sein, dass nur in eine Richtung ein gerichteter Weg existiert.

Durchmesser und Taillenweite

Den größten Abstand zwischen zwei Knoten in einem Graphen GG nennt man Durchmesser von GG. Als Taillenweite eines Graphen bezeichnet man die Länge eines kürzesten nicht trivialen Kreises. Falls der Graph keinen Kreis besitzt, so setzt man die Taillenweite auf unendlich.

Distanzgraph

Der Distanzgraph zu einem Graphen G=(V,E)G = (V, E) bezeichnet den vollständigen (das heißt je zwei Knoten sind durch eine Kante verbunden, ggf. in gerichteten Graphen in beide Richtungen, wobei es aber keine Schleifen gibt) kantengewichteten Graphen auf der Knotenmenge VV, der jeder Kante als Kantengewicht den Abstand zwischen den beiden Knoten in GG zuordnet.

Wichtige Algorithmen

Der Algorithmus von Dijkstra findet einen kürzesten Pfad zwischen zwei beliebigen Knoten in einem (kantengewichteten) Graphen. Mit seiner Hilfe lässt sich auch der Distanzgraph bestimmen, indem man ihm ausgehend von jedem Knoten den Abstand zu jedem anderen bestimmt. Für jeden Knoten ist dabei nur ein Aufruf des Algorithmus von Dijkstra nötig, da dieser auch den Abstand von einem Knoten zu allen anderen Knoten bestimmen kann.
Weitere Algorithmen zum Finden von kürzesten Pfaden sind der Algorithmus von Floyd und Warshall, der Algorithmus von Bellman und Ford und der Algorithmus von Johnsons, welcher Bellman-Ford mit Dijkstras Algorithmus kombiniert.
Der Distanzgraph ist für das Problem des Handlungsreisenden interessant, da dieser metrisch ist, weshalb verschiedene Approximationsalgorithmen die optimale Lösung dieses Problem approximieren können.
 
 

Im großen Garten der Geometrie kann sich jeder nach seinem Geschmack einen Strauß pflücken.

David Hilbert

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Wege, Pfade, Zyklen und Kreise in Graphen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Diskrete Mathematik