Def. ein Weg in einem Graphen G
- ist eine Folge von (abwechselnd) Knoten und Kanten
[v0, e0, v1, e1,..., ek - 1, vk],
- so daß für alle
0i < k gilt:
ei = {vi, vi + 1} E(G)
- und
[v0, v1,..., vk1] sind paarweise verschieden
sowie
[v1, v2,..., vk] sind paarweise verschieden
- Die einzige zugelassene Knoten-Wiederholung ist v0 = vk,
ein solcher Weg heißt Kreis.
- Die Länge des Weges ist k (= die Anzahl der Kanten, nicht Knoten)
-- Vorsicht: Länge von P4 ist 3.
Johannes Waldmann
2005-01-25