1.3 Directed graphs

A directed graph or digraph D is a finite nonempty set of objects called vertices together with a set of ordered pairs of distinct vertices of D called arcs or directed edges.

The vertex set of D and the arc set is denoted by  and , respectively.

Example:   and

             

Figure 2.10. A directed graph

If   is an arc in a directed graph, then

-     if i > j then a is called as forward arc,

-     if i < j then a is called as forward arc.

Let  be an arc of a digraph D. Then a is said to join u and v, or we say that a is incident from u and incident to v, while u is incident to a and v is incident from a. Moreover, u is said to be adjacent to v and v is adjacent from u.

Two vertices u and v are nonadjacent in D, if u is neither adjacent to nor adjacent from v in D.

The outdegree  of a vertex v in D is the number of vertices of D that are adjacent from v.

The indegree  of a vertex v in D is the number of vertices of D that are adjacent to v.

The degree  of a vertex of D is defined by  .

A digraph D1 is isomorphic to a digraph D2 if there exists a one-to-one mapping , called an isomorphism, from  onto  such that   iff  . We denote it by D1 = D2.

A labeled digraph D1 is a subdigraph of a labeled digraph D if  and .

A subdigraph D1 of D is a spanning subdigraph if D1 has the same order as D.

A digraph is called symmetric, if whenever  is an arc of D, then  is also.

A digraph D is called asymmetric digraph or an oriented graph if whenever  is an arc of D, then  is not an arc of D. (So, an oriented graph can be obtained from a graph G by assigning a direction to each edge of G.)

A digraph D is complete if for every two distinct vertices u and v of D, at least one of the arcs  and  is present in D. The complete symmetric digraph of order n has both arcs  and  for every two distinct vertices u and v and is denoted by .

A complete asymmetric digraph is called a tournament.

A digraph D is called r-regular if  for every vertex v of D.

A digraph D is connected (or weakly connected) if the underlying graph of D is connected.

A digraph D is strong (or strongly) connected if for every pair u, v of vertices, D contains both a   path and a  path.

For vertices u and v in a digraph D containing a u-v path, the (directed) distance  from u to v is the length of a shortest  path in D.

The eccentricity  of a vertex u in D is the distance from u to a vertex farthest from u.

The minimum eccentricity of the vertices of D is the radius  of D, while the diameter  is the greatest eccentricity.

If one allows more than one edge (but yet finite number) between the same pair of vertices in a graph, the resulting structure is a multigraph.

The edges between the same pair of vertices are called parallel edges.

If more than one arc in the same direction is permitted to join two vertices in a digraph, it results in a multidigraph.

A loop is an edge (or arc) that joins a vertex to itself.