Directed graph

A directed graph (sometimes abbreviated digraph) is a graph in which each edge is assigned an orientation. Formally, a digraph $D$ is a pair, $D = (V, E) = (V(D), E(D))$ of a (usually finite) set $V$ of vertices together with a multiset $E$ of edges such that for each $e \in E$ we have $e \in V \times V$ .

Every digraph has a natural underlying graph $G(D) = (V(D), E')$ where $E' = \left\{\{v, w\} \mid (v, w) \in E\right\}$ . A digraph is usually drawn by drawing the underlying graph and putting an arrow on each edge to indicate the direction.

Note that our definition allows both loops and multiple edges. In other circumstances, digraphs may be defined to be loopless, simple (that is, with no multiple edges) or both. Note that the "right" convention for digraphs is less obvious than for graphs. In particular, sometimes the word "simple" is meant to allow both the edge $(v, w)$ and the edge $(w, v)$ , so the underlying graph of a simple digraph is not necessarily simple. In any case, one should be sure to provide the definition of these terms before first using them.

Examples of directed graphs

Tournament graph

In a round robin tournament (that is, a tournament in which each team plays every other team exactly once) with no ties, we can associate a tournament graph in which we draw the edge $(A, B)$ if and only if team $A$ beat team $B$ .

Complete digraph

The definition of a complete digraph depends on the particular definition of digraph that we use. The simplest version corresponds to the definition we gave above, for which the complete digraph on a vertex set $V$ is the pair $K(V) = (V, V \times V)$ , i.e. for each vertex $v \in V$ we have an edge $(v, v)$ and for each pair $v, w \in V$ we have both edges $(v, w)$ and $(w, v)$ .

Differences between directed and undirected graphs

Degree

In a directed graph, each vertex $v$ has two associated degrees, the outdegree (the number of edges $(v, w)$ for some $w \in V$ ) and the indegree (the number of edges $(w, v)$ for some $w \in V$ ).

Paths, Cycles and Cycle-free Graphs

A path in a directed graph has the obvious meaning of a sequence of vertices joined by edges that are directed in the appropriate direction. Formally, a path is a sequence $v_0, e_1, v_1, e_2, \ldots, e_n, v_n$ such that $v_i \in V$ $e_i = (v_{i - 1}, v_i) \in E$ for every $i$ . A cycle is a path in which the initial and terminal vertices of the path are the same.

Note that a cycle-free directed graph is not the same as a directed tree: while no directed tree contains a directed cycle, there are many digraphs with no directed cycles whose underlying graphs contain (undirected) cycles, as in the image below:

An image is supposed to go here. You can help us out by creating one and editing it in. Thanks.

In fact, any graph $G = (V, E)$ is the underlying graph of some cycle-free digraph on the same vertex set. We can construct one of these digraphs as follows: list the elements of $V$ in some order, $v_1, v_2, \ldots, v_n$ . Define a set $E'$ of ordered pairs of elements of $V$ by replacing each edge $\{v_i, v_j\} \in E$ with $i < j$ by the directed edge $(v_i, v_j)$ . It is clear that the resulting digraph $D = (V, E')$ contains no directed cycles, regardless of the underlying structure of $G$ .

Page

Toolbox

Search