Difference between revisions of "Directed graph"
(New page: A '''directed graph''' (sometimes abbreviated ''digraph'') is a graph in which each edge is assigned an orientation. Formally, a digraph <math>D</math> is a pair, <math>D = (V, E)...) |
m (→Common examples of directed graphs) |
||
| Line 5: | Line 5: | ||
Note that our definition allows both [[loop]]s 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 <math>(v, w)</math> and the edge <math>(w, v)</math>, 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. | Note that our definition allows both [[loop]]s 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 <math>(v, w)</math> and the edge <math>(w, v)</math>, 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=== | ===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 <math>(A, B)</math> if and only if team <math>A</math> beat team <math>B</math>. | 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 <math>(A, B)</math> if and only if team <math>A</math> beat team <math>B</math>. | ||
| 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>. | ||
| − | |||
==See Also== | ==See Also== | ||
Revision as of 14:16, 7 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.
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 .
