Definition:Reachable

Definition

Definition 1

Let $G = \left({V, A}\right)$ be a directed graph.

Let $u, v \in V$.

Then $v$ is reachable from $u$ if and only if there exists a directed walk from $u$ to $v$.

Definition 2

Let $G = \left({V, A}\right)$ be a directed graph.

Let $\mathcal R$ be the reachability relation of $G$.

That is, $\mathcal R$ is the transitive closure of $A$.

Let $u, v \in V$.

Then $v$ is reachable from $u$ if and only if $u \mathrel {\mathcal R} v$.

Also see

• Equivalence of Definitions of Reachable