2.4. 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 .

Theorem 2.13. If D is a digraph of order n and size m with then

Proof. Trivial.

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.