ABSTRACT
There are occasions when the symmetric nature of graphs does not provide a desirable structure to represent a situation we may encounter. This leads us to the concept of directed graphs (digraphs).
A directed graph or digraph D is a finite nonempty set of objects called vertices together with a (possibly empty) set of ordered pairs of distinct vertices of D called arcs or directed edges. For vertices u and v in D, an arc (u, v) is sometimes denoted by writing u→ v (or v ← u). As with graphs, the vertex set of D is denoted by V (D) or simply V and the arc set (or directed edge set) of D is denoted by E(D) or E. A digraph D with vertex set V = {u, v, w, x} and arc set E = {(u, v), (v, u), (u,w), (w, v), (w, x)} is shown in Figure 7.1. When a digraph is described by means of a diagram, the “direction” of each arc is indicated by an arrowhead. Observe that in a digraph, it is possible for two arcs to join the same pair of vertices if the arcs are directed oppositely.
