Directed Graphs

In/out degree, reachability, and DAGs.

The idea

A directed graph, or digraph, is a set of vertices together with a set of edges, each of which is an ordered pair of vertices $(u, v)$, written $u \to v$ and drawn as an arrow from $u$ to $v$. The vertex $u$ is the edge's tail and $v$ is its head, and $u \to v$ and $v \to u$ are different edges. Digraphs model relations that need not run both ways: one-way streets, links between web pages, tasks that must finish before others start.

Each vertex has two degrees. Its out-degree is the number of edges with that vertex as tail, and its in-degree is the number with it as head. Every edge contributes exactly one tail and one head, so the out-degrees sum to $|E|$, the number of edges, and the in-degrees sum to $|E|$ as well.

A directed cycle is a sequence of edges that leads from a vertex back to itself with every step taken in the direction of its arrow. A digraph with no directed cycle is acyclic, and is called a DAG.

Ways to work on it

• Walkthrough. Out-degree, in-degree, and the DAG property.
• Practice. Find an in- or out-degree.
• Hardest. Find the sinks of a DAG, then everything reachable from a vertex.

Not sure where to start? Take the ten-question placement test.