Directed Graphs

Digraphs

A directed graph or a digraph is a graph where each edge has an orientation.

That means each edge begins at a source vertex and ends at a target vertex. We call the source vertex the tail and the target vertex the head of the edge.

We also want our notation to emphasize this notion of directionality. So, we do the obvious and represent an edge as an ordered pair $(u,v)$, where $u$ is the tail and $v$ is the head of the edge.

In the context of a digraph, an edge $(u,v)$ goes from a vertex $u$ to a vertex $v$ and can’t be represented as ...