Definition:Reachability Relation

From ProofWiki
Jump to navigation Jump to search

Definition

Definition 1

Let $G = \struct {V, A}$ be a digraph.


Then the reachability relation of $G$ is the transitive closure of $A$.


Definition 2

Let $G = \struct {V, A}$ be a digraph.


Let $\RR$ be the relation on $V$ defined by letting $x \mathrel \RR y$ if and only if $y$ is reachable from $x$.

That is, $x \mathrel \RR y$ if and only if there exists a directed walk from $x$ to $y$.


Then $\RR$ is the reachability relation of $G$.


Also see