Definition:Reachable
Jump to navigation
Jump to search
Definition
Definition 1
Let $G = \struct {V, A}$ be a digraph.
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 = \struct {V, A}$ be a digraph.
Let $\RR$ be the reachability relation of $G$.
That is, $\RR$ is the transitive closure of $A$.
Let $u, v \in V$.
Then $v$ is reachable from $u$ if and only if $u \mathrel \RR v$.