Definition:Reachable

From ProofWiki
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$.


Also see