Directed graph

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

Every digraph has a natural underlying graph where . 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 and the edge , 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 if and only if team beat team .

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 is the pair , i.e. for each vertex we have an edge and for each pair we have both edges and .

See Also

• A thread on the AoPS forums concerning tournament graphs