Gerichteter Weg, Gerichteter Pfad und Erreichbarkeit

Die Navigation in einem Digraph ist streng an die Einhaltung der vorgegebenen Pfeilrichtungen gebunden.

Gerichteter Weg: Eine alternierende Folge $W = (s_{1}, e_{1}, s_{2}, e_{2}, \dots, s_{k}, e_{k}, s_{k + 1})$ aus Knoten $s_{i} \in V (G)$ und gerichteten Kanten $e_{i} \in E (G)$ , wobei für jede Kante gilt: $e_{i} = (s_{i}, s_{i + 1})$ . Knoten- und Kantenwiederholungen (Schleifen) sind zulässig. Die Anzahl der Kanten $k$ definiert die Länge des Weges.
Gerichteter Pfad: Ein gerichteter Weg $W$ , bei dem alle passierten Knoten zwingend paarweise verschieden sein müssen: $\forall i, j \in {1, \dots, k + 1} : i \neq j ⟹ s_{i} \neq s_{j}$
Erreichbarkeit: Ein Knoten $v$ ist von einem Knoten $u$ aus erreichbar, wenn im Digraph ein valider gerichteter Pfad existiert, der im Startknoten $u$ beginnt und im Zielknoten $v$ endet.