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.
Contents
[hide]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 .
Differences between directed and undirected graphs
Degree
In a directed graph, each vertex has two associated degrees, the outdegree (the number of edges for some ) and the indegree (the number of edges for some ).
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 such that for every . 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 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 in some order, . Define a set of ordered pairs of elements of by replacing each edge with by the directed edge . It is clear that the resulting digraph contains no directed cycles, regardless of the underlying structure of .