Wege in Graphen

gerichteter Graph G = (V, E), d. h. E⊆V²

• Knotenfolge [v₀, v₁,…, v_n] heißt Weg in G,
  falls ∀0≤i < n : (v_i, v_i+1)∈E.

• Die Länge diese Weges ist n (= die Anzahl der Kanten)

• es existiert Weg der Länge ≥1 von x nach y in G
  $\iff$ (x, y)∈E⁺ (das heißt ∃n : n≥1∧(x, y)∈Eⁿ)