Difference between revisions of "Directed graph"
m (→Common examples of directed graphs) |
|||
(One intermediate revision by the same user not shown) | |||
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== | ||
− | + | * [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=162646 A thread on the AoPS forums concerning tournament graphs] | |
[[Category:Graph theory]] | [[Category:Graph theory]] |
Latest revision as of 14: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
.