Difference between revisions of "Directed graph"
m (→See Also) |
|||
| Line 11: | Line 11: | ||
===Complete digraph=== | ===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 <math>V</math> is the pair <math>K(V) = (V, V \times V)</math>, i.e. for each vertex <math>v \in V</math> we have an edge <math>(v, v)</math> and for each pair <math>v, w \in V</math> we have both edges <math>(v, w)</math> and <math>(w, v)</math>. | 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 <math>V</math> is the pair <math>K(V) = (V, V \times V)</math>, i.e. for each vertex <math>v \in V</math> we have an edge <math>(v, v)</math> and for each pair <math>v, w \in V</math> we have both edges <math>(v, w)</math> and <math>(w, v)</math>. | ||
| + | |||
| + | ==Differences between directed and undirected graphs== | ||
| + | ===Degree=== | ||
| + | In a directed graph, each vertex <math>v</math> has two associated degrees, the ''outdegree'' (the number of edges <math>(v, w)</math> for some <math>w \in V</math>) and the ''indegree'' (the number of edges <math>(w, v)</math> for some <math>w \in V</math>). | ||
| + | |||
| + | ===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 <math>v_0, e_1, v_1, e_2, \ldots, e_n, v_n</math> such that <math>v_i \in V</math> <math>e_i = (v_{i - 1}, v_i) \in E</math> for every <math>i</math>. 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 (graph theory) | 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: | ||
| + | |||
| + | {{image}} | ||
| + | |||
| + | In fact, any graph <math>G = (V, E)</math> 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 <math>V</math> in some order, <math>v_1, v_2, \ldots, v_n</math>. Define a set <math>E'</math> of ordered pairs of elements of <math>V</math> by replacing each edge <math>\{v_i, v_j\} \in E</math> with <math>i < j</math> by the directed edge <math>(v_i, v_j)</math>. It is clear that the resulting digraph <math>D = (V, E')</math> contains no directed cycles, regardless of the underlying structure of <math>G</math>. | ||
==See Also== | ==See Also== | ||
Latest revision as of 13:58, 11 January 2008
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
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 
.
