|
A directed graph or digraph is a pair  where  is a set of vertices and  is a subset of
 called edges or arcs.
If  is symmetric (i.e.,
 if and only if
 ), then the digraph is isomorphic to an ordinary (that is, undirected) graph.
Digraphs are generally drawn in a similar manner to graphs with arrows on the edges to indicate a sense of direction. For example, the digraph
may be drawn as
Since the graph is directed, one has the concept of the number of edges originating or terminating at a given vertex  . The out-degree,
 of a vertex  is the number of edges having  as their originating vertex; similarly, the in-degree,
 is the number of edges having  as their terminating vertex.
If the graph has a finite number of vertices, say
 , then obviously
A directed path in a digraph  is a sequence of edges
 such that the end vertex of  is the start vertex of  for
 . Such a path is called a directed circuit if, in addition, the end vertex of  is the start vertex of  .
A digraph is connected (or, sometimes, strongly connected) if for every pair of vertices  and  there is a directed path from  to  . In addition, a digraph  is said to have a root
 if every vertex  is reachable from  , i.e. if there is a directed path from  to  .
A digraph is called a directed tree if it has a root and if the underlying (undirected) graph is a tree. That is, it must morphologically look like a tree, and the structure imposed by the directional arrows must flow “away” from the root.
If  is a subgraph of a digraph  , then  is said to be a directed spanning tree of  if  is a directed tree and  contains all
vertices of  . This is a direct analog of the concept of spanning trees for undirected graphs. Note that if  is the root of  , then  is clearly a root of  . Also, if  is any root of  , it is possible to construct a directed spanning tree of  with root  : construct  edge by edge starting from  . At each vertex, add any edge from  whose terminus is a vertex not yet in  . Since  is a root of  , this process is guaranteed to include each vertex in  ; since we are choosing at each step only vertices not yet visited, we are guaranteed to end up with a tree.
| 
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & a \ar[r] & b \ar[d] \ar[dl] \ & c \ar[ur] \ar[r] \ar@(dr,dl)[] & d \ & & \ } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1702/l2h/img9.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ & a \ar[r] & b \ar[d] \ar[dl] \ & c \ar[ur] \ar[r] \ar@(dr,dl)[] & d \ & & \ } } \end{xy}$")
