Kantenzug
Kantenzug ist ein Begriff der Graphentheorie und bezeichnet eine zusammenhängende Folge von Kanten in einem Graphen.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Sei
ein Graph aus Knoten V und Kanten E (von englisch vertices bzw. edges). Eine Folge
von Kanten aus E wird Kantenzug genannt, wenn es eine Folge
von Knoten aus V gibt, so dass jeweils
die Knoten
und
„verbindet“, d. h.
bzw.
eine Kante aus E ist oder
„Anfangs-“ und
„Endknoten“ von
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
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
der Knoten aus V angibt. Eine Folge
von Knoten ist dann ein Kantenzug, wenn für alle
,
eine Kante
in E existiert, die
und
verbindet. Liegt hingegen ein Multigraph vor, so dass es mehrere Kanten in G geben kann, die
mit
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
, sonst heißt er offen.
[Bearbeiten] Siehe auch
Die Terminologie ist nicht ganz einheitlich, man vergleiche:
[Bearbeiten] Erläuterung
- ↑ 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).
[Bearbeiten] 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)