Directed Graphs, Paths, and Reachability

Directed Graphs

Definition

A directed graph (or digraph) is a pair $(V, E)$ where:

• $V$ is a set of vertices (or nodes)
• $E \subseteq V \times V$ is a set of edges (or arcs)

Note: A digraph is exactly an endo-relation $E : V \nrightarrow V$.

Visualisation

Draw each vertex as a point. Draw an arrow from $v$ to $w$ iff $(v, w) \in E$.

Paths

Definition

A path (or walk) in a digraph is a sequence $v_0, v_1, \ldots, v_k$ such that $(v_{i-1}, v_i) \in E$ for each $i = 1, \ldots, k$.

• The length of the path is $k$ (the number of edges)
• A simple path visits no vertex twice
• A cycle is a path from a vertex back to itself

Path Relation

The path relation $E^{\circ *}$ relates $v$ to $w$ iff there exists a path from $v$ to $w$:

$E^{\circ *} = \bigcup_{n \geq 0} E^{\circ n}$

where $E^{\circ n}$ is the $n$-fold composite.

Reachability

Definition

Vertex $w$ is reachable from vertex $v$ if there is a path from $v$ to $w$.

Equivalently: $v E^{\circ *} w$.

Computing Reachability

For an $n$-vertex graph, any simple path has length $< n$. Therefore:

$E^{\circ *} = \bigcup_{k=0}^{n-1} E^{\circ k}$

This gives an algorithm: compute $I \cup E \cup E^2 \cup \cdots \cup E^{n-1}$.

Adjacency Matrix Approach

Let $M$ be the adjacency matrix. Compute:

$M^* = I \oplus M \oplus M^2 \oplus \cdots \oplus M^{n-1}$

Then $M^*_{ij} = 1$ iff $j$ is reachable from $i$.

Preorders

Definition

A relation $R$ on $A$ is a preorder if it is:

1. Reflexive: $\forall a. aRa$
2. Transitive: $\forall a, b, c. (aRb \land bRc \Rightarrow aRc)$

A preorder is a partial order if it is also antisymmetric: $(aRb \land bRa) \Rightarrow a = b$.

Examples

Relation	Type
$\leq$ on $\mathbb{R}$	Partial order
$\subseteq$ on $\mathcal{P}(X)$	Partial order
$\mid$ (divisibility) on $\mathbb{Z}^+$	Partial order
$\mid$ on $\mathbb{Z}$	Preorder (not antisymmetric: $-1 \mid 1$ and $1 \mid -1$)
Reachability in a digraph	Preorder

Reflexive-Transitive Closure

Definition

The reflexive-transitive closure of $R$ is the smallest preorder containing $R$:

$R^{\circ *} = \bigcap \{P : R \subseteq P, P \text{ is a preorder}\}$

Examinable Proof: Characterisation

Theorem: $R^{\circ *}$ is the smallest preorder containing $R$.

Proof:

Part 1: $R^{\circ *}$ is a preorder containing $R$.

• $R \subseteq R^{\circ *}$: $R^{\circ 1} = R$, and $R^{\circ *} = \bigcup_{n \geq 0} R^{\circ n}$.
• Reflexivity: $R^{\circ 0} = \text{id} \subseteq R^{\circ *}$.
• Transitivity: If $a R^{\circ *} b$ and $b R^{\circ *} c$, there exist paths from $a$ to $b$ and $b$ to $c$. Concatenating gives a path from $a$ to $c$.

Part 2: $R^{\circ *}$ is the smallest such preorder.

Let $P$ be any preorder with $R \subseteq P$. We show $R^{\circ *} \subseteq P$.

By induction on $n$: $R^{\circ n} \subseteq P$ for all $n$.

• Base ($n = 0$): $R^{\circ 0} = \text{id} \subseteq P$ by reflexivity.
• Step: $R^{\circ (n+1)} = R \circ R^{\circ n} \subseteq P \circ P = P$ by transitivity.

Thus $\bigcup_n R^{\circ n} \subseteq P$.

Transitive Closure

The transitive closure $R^{\circ +} = \bigcup_{n \geq 1} R^{\circ n}$ is the smallest transitive relation containing $R$.

---

Summary

• A digraph $(V, E)$ is an endo-relation $E : V \nrightarrow V$
• Path relation $E^{\circ *}$ relates connected vertices
• $R^{\circ *}$ is the reflexive-transitive closure: smallest preorder containing $R$
• Reachability computed via matrix powers $M^*$ up to $M^{n-1}$