Wege

Def. ein Weg in einem Graphen G

• ist eine Folge von (abwechselnd) Knoten und Kanten [v₀, e₀, v₁, e₁,..., e_{k - 1}, v_k],
• so daß für alle 0$\le$i < k gilt: e_i = {v_i, v_{i + 1}} $\in$ E(G)
• und [v₀, v₁,..., v_k1] sind paarweise verschieden sowie [v₁, v₂,..., v_k] sind paarweise verschieden

• Die einzige zugelassene Knoten-Wiederholung ist v₀ = v_k, ein solcher Weg heißt Kreis.
• Die Länge des Weges ist k (= die Anzahl der Kanten, nicht Knoten) -- Vorsicht: Länge von P₄ ist 3.