Digraph models and representations

 

Most graph terminology applies equally well to digraphs,e.g., subgraph, self-loop, bipartite, isomorphic, empty. The definitions below are special to digraphs or take on a somewhat different meaning for digraphs. In context, where it is clear that only digraphs are being discussed, “directedness” is often an implicit attribute of an “edge”, “path”, and other terms.

Definitions:

A directed graph, or digraph, consists of:

• a set V , whose elements are called vertices,

• a set E, whose elements are called directed edges or arcs, and

• an incidence function that assigns to each edge a tail and a head.

The tail of an arc is the vertex it leaves, and the head is the vertex it enters.

A strict digraph has no self-loops or multi-arcs.

The underlying graph of a digraph is the graph obtained from the digraph by replacing every directed edge by an undirected edge.

The out-degree of vertex v, denoted deg-v, is the number of arcs with tail at v.

The in-degree of vertex v, denoted deg+v, is the number of arcs with head at v.

A digraph D is transitive if whenever it contains an arc from u to v and an arc from v to w, it also contains an arc from u to w.

Facts:

1. Strict-digraph terminology: In a context focusing primarily on strict digraphs, there is often a different terminological convention:

• “digraph” refers to a strict digraph;

• a directed graph with multi-arcs is called a multidigraph;

• a directed graph with self-loops is called a pseudodigraph;

• an arc with tail u and head v is designated uv.

2. Alternative “path” terminology: There is an alternative convention in which a (directed) “path” may use vertices and arcs more than once, but an “elementary path” does not repeat arcs, and a “simple path” does not repeat vertices (and, hence, does not repeat arcs either).

3. The incidence structure of a digraph is frequently represented by an arc list, in which each arc is represented by an ordered pair uv, where u is its tail and v is its head. For each arc with tail u and head v, there is a separate entry, so that uv occurs as often as the number of such arcs. A list of the isolated vertices plus such an arc list completely specifies a digraph.

4. Another common specification of a digraph is the lists-of-neighbors representation. For each vertex u, there is a corresponding row, which has as an entry the head of each arc whose tail is u. Thus a vertex v occurs in that row as many times as there are arcs from u to v.

5. The incidence matrix is another common way to represent a digraph. Since all but one or two of the entries in every column are zero, the incidence matrix is a highly inefficient form of representation.

6. The adjacency matrix is also a common way to specify a digraph in some contexts when there is no reason to identify the arcs by name.

7. A digraph can be represented by a 2×|E| incidence table in which the tail and head of each arc e appear in column e. Direction on an arc can be indicated by a convention as to whether tail or head appears in the first row, which requires swapping the two column entries if the direction is changed. Alternatively, direction can be indicated by marking one of the two entries in each column as the head, and then moving the marker if the direction changes.

8. A row-sum in a directed adjacency matrix equals the out-degree of the corresponding vertex. A column-sum equals the in-degree.

9. In any digraph, the sum of the in-degrees, the sum of the out-degrees, and the number of edges are all equal to each other; i.e.,  .

Examples:

1. The following arc list, incidence table, list-of-neighbors, and adjacency matrix all represent the digraph G.

 

 

arc list:

uv, vv, vw, xw, xw, ux, xu

 

incidence table:

e1  e2  e3  e4  e5  e6  e7

u   v   v    x   x   u   x

v   v   w   w  w   x   u

 

lists-of-neighbors:  ; adjacency matrix: .

 

2. Civil Engineering: A road network in which at least some of the roads are oneway can be modeled by a digraph. The nodes are road junctures; each two-way road is represented by a pair of arcs, one in each direction. Loops are allowed, and they may represent “circles” that occur in housing developments and in industrial parks. Similarly, multiarcs may occur.

3. Operations Research: A large project consists of many smaller tasks with a precedence relation – some tasks must be completed before certain others can begin. The vertices represent tasks, and there is an arc from u to v if task u must be completed before v can begin. For instance, in the following figure it is necessary both that food is loaded and the cabin is cleaned before passengers are loaded.

 

4. Sociology and Sociobiology: A business (or army, or society, or ant colony) has a hierarchical dominance structure. The nodes are the employees (soldiers, citizens, ants) and there is an arc from u to v if u dominates v. If the chain of command is unique, with a single leader, and if only arcs representing immediate authority are included, then the result is a rooted tree.

5. Computer Software Design: A large program consists of many subprograms, some of which can invoke others. Let the nodes of D be the subprograms, and let there be an arc from u to v if subprogram u can invoke subprogram v. Then the call graph D encapsulates all possible ways control can flow within the program. Directed cycles represent indirect recursion, and serve as a warning to the designer to ensure against infinite loops. See the following figure, where subprogram 2 can call itself indirectly.

 

 

6. Ecology: A food web is a strict digraph in which nodes represent species and in which there is an arc from u to v if species u eats species v. The following figure shows a small food web.