12.2 Paths, cycles and connectivity

Once a graph records connections, we can ask whether one vertex can be reached from another. A route may stop at a target, return to its start, or fail because an arrow points the wrong way. These distinctions matter in travel networks, task dependencies, and information flow.

This is foundational to intermediate graph theory. Read graph representations first. MIT OpenCourseWare's Mathematics for Computer Science has chapters on undirected and directed graphs.

A basic idea: follow the arrows

Suppose the graph has $A\to B$, $B\to C$, $C\to A$, and $C\to D$. From $A$ you can reach $D$ along $A\to B\to C\to D$. From $D$ you cannot return: it has no outgoing edge. The first three vertices form a directed cycle, but $D$ is outside it.

A quick tour of route words

A walk follows adjacent edges and may repeat vertices. In this module, a path is a walk with no repeated vertices. A cycle starts and ends at the same vertex and otherwise does not repeat vertices. A length-zero path lets a vertex reach itself. Stating these conventions matters because textbooks sometimes use “path” more broadly.

In an undirected graph, vertices are connected if a path joins them; the graph is connected if every pair is connected. A connected component is a largest connected group. In a directed graph, reachability is ordered: $u$ may reach $v$ even when $v$ cannot reach $u$. Two vertices are strongly connected if each reaches the other. If we ignore arrow directions and the graph becomes connected, it is weakly connected.

Cycles can be helpful or harmful depending on the meaning of the edges. A road loop offers another route. A cycle of “must finish before” prerequisites is impossible to satisfy without changing the rules. Module 12.5 groups mutually reachable vertices into strongly connected components.

Application 1: prerequisites

Tasks have arrows $A\to B$, $B\to C$, and $A\to D$, meaning the task at the arrow's tail must precede the one at its head. Can $A$ lead to $C$? Can $C$ lead back to $A$?

1. Trace forward. $A\to B\to C$ is a path, so $C$ is reachable from $A$.
2. Check reverse edges. No edge leaves $C$, so $A$ is not reachable from $C$.
3. Check for cycles. This graph has none. Adding $C\to A$ would create $A\to B\to C\to A$, a contradictory prerequisite loop.

Application 2: disconnected roads

Two-way roads join $P$ to $Q$ and $Q$ to $R$. Town $S$ has no road. How many connected components are there, and what changes if a road joins $R$ and $S$?

1. Group reachable towns. $P,Q,R$ reach one another through roads; $S$ reaches only itself.
2. Count components. There are two: $\{P,Q,R\}$ and $\{S\}$.
3. Add the new road. $R$–$S$ connects the groups, leaving one connected component.

Because these roads are two-way, a route works in reverse as well.