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.

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_0 = 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

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)