# Definition:Reachability Relation/Definition 2

Jump to navigation
Jump to search

## Definition

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

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

That is, $x \mathrel {\mathcal R} y$ if and only if there exists a directed walk from $x$ to $y$.

Then $\mathcal R$ is the **reachability relation** of $G$.