Kantenzug

Kantenzug ist ein Begriff der Graphentheorie und bezeichnet eine zusammenhängende Folge von Kanten in einem Graphen.

Definition

Sei G = (V,E) ein Graph aus Knoten V und Kanten E (von englisch vertices bzw. edges). Eine Folge $F=(e_1,\dots,e_n)$ von Kanten aus E wird Kantenzug genannt, wenn es eine Folge $(v_0,\dots,v_n)$ von Knoten aus V gibt, so dass jeweils e_i die Knoten v_{i − 1} und v_i „verbindet“, d. h. {v_{i − 1},v_i} bzw. (v_{i − 1},v_i) eine Kante aus E ist oder v_{i − 1} „Anfangs-“ und v_i „Endknoten“ von e_i sind.^[1]

Man beachte, dass eine Kante mehrfach in F auftreten kann, andernfalls spricht man von einem Weg.

Alternativ werden die zugehörigen Knoten explizit in einer alternierenden Folge von Knoten und Kanten $(v_0, e_1, v_1, e_2, v_2, \dots, e_n, v_n)$ angegeben.

Eine weitere alternative Darstellung erhält man im Falle von Graphen ohne Mehrfachkanten (insbesondere für einfache Graphen), indem man lediglich die entsprechende Folge $(v_0,\dots,v_n)$ der Knoten aus V angibt. Eine Folge $(v_0,\dots,v_n)$ von Knoten ist dann ein Kantenzug, wenn für alle v_{i − 1}, v_i eine Kante e_i in E existiert, die v_{i − 1} und v_i verbindet. Liegt hingegen ein Multigraph vor, so dass es mehrere Kanten in G geben kann, die v_{i − 1} mit v_i verbinden, so müssen die Kanten explizit wie weiter oben angegeben werden, um den Kantenzug eindeutig zu beschreiben.

Ein Kantenzug heißt geschlossen oder zyklisch, wenn v₀ = v_n, sonst heißt er offen.

Siehe auch

Die Terminologie ist nicht ganz einheitlich, man vergleiche:

• Wege, Pfade, Zyklen und Kreise in Graphen
• Weg im Artikel Glossar Graphentheorie

Erläuterung

1. ↑ Gerichtete Multigraphen können etwa als Quadrupel (V, E, init, ter) mit Abbildungen init, ter: E → V dargestellt werden, so dass init(e) „Anfangs-“ und ter(e) „Endknoten“ von e ist, vgl. S. 30 von
   • Reinhard Diestel: Graphentheorie. 3 Auflage. Springer, 2006, ISBN 3540213910 (online; PDF, 2.30 MB).

Weblinks

• Spaziergänge und Buslinien – Terminologie in einer gefälligen, anschaulichen und theoretischen Darstellung des Königsberger Brückenproblems mit Hilfe von Kantenzügen (Franz Embacher, Uni Wien)