This chapter gives the basic introduction to directed graphs (digraphs) and their pertinent concepts, elements, and frameworks. From a general point of view, the most majority of concepts of digraphs have similar characteristics with networks structures. Therefore, in conjunction with networks chapter, this chapter not only emphasizes some aspect of digraphs, but also addresses the basic terminology and terms that have been widely applied in literature. Regarding this premise, the first section presents the basic definitions, and the second section classifies the most important and applicable types of digraphs extensively addressed in the literature. Moreover, one of the main concepts of digraphs (reachability and connectivity) is discussed in the third section. In addition, the fourth section briefly discusses a few application cases of digraphs, and the fifth section finally presents the conclusion of this chapter.
TopDigraphs And Basic Definitions
From a general point of view, networks are interrelated with digraphs, in which each edge is attributed by a weight. Therefore, digraphs can be discussed and followed up similarly. A digraph is a directed graph GD = (V,E) with two main elements: a finite set of vertices V, and a finite set of edges E. Each digraph has some basic definitions and characteristics to be explained as follows (Bang-Jensen & Gutin, 2007; Bondy & Murty, 2008; Cormen et al., 2009; Donato et al., 2007; Gross & Yellen, 2003):
- •
Order (size): The number of vertices in GD that is denoted by |V|.
- •
Tail, head, adjacency, and incidence: For each given edge (i,j)ÎV, i and j are called the head and tail of that edge, respectively. These head and tail vertices are also called end-vertices of the linking edge. Moreover, both of two vertices linked via a single edge are called adjacent. In addition, two vertices, connected by the corresponding edge, is said to be the incident of that edge.
- •
Dominance: Provided that such relationship is created between two vertices (i and j), j is called to be dominated by i. Furthermore, the in-neighbors vertices of any given vertex refer to those vertices dominating this vertex. Similarly, out-neighbors of a vertex correspond to those vertices dominated by that vertex.
- •
Loops/parallel edges: If there are more than one edge between two specific vertices (e.g. an edge connects i to j, and another edge connects j to i in the reversed direction), these edges, called parallel edges, can make a loop in the corresponding digraph.
- •
Distance: Provided that there is a shortest path between each pair of vertices in a digraph, the distance between each pair of vertices is defined in terms of the number of edges contained in that path. Similarly, the number of edges in this path can be interpreted as the length of that path.
- •
Eccentricity: The farthest distance of any vertex from a given vertex v is considered as the eccentricity of that vertex e(v).
- •
In-degree and out-degree: For any subset of vertices (VSÍV), the in-degree of VS is the number of edges whose heads are in VS and tails are in V-VS. Conversely, the out-degree of VS is the number of edges whose heads are in V-VS and tails are in VS.
Regarding the basic structure of digraphs, it should be noted that they are totally affected by the structures of graphs and networks (called underlying graphs). As a matter of fact, it can be stated that many of concepts that have been proposed for graphs and networks can be similarly adapted for digraphs such as connectivity, paths and trees, bipartite structures, the degree of vertices, cuts, shortest path structures, etc.
TopClassification Of Digraphs
In this section, some types of digraphs are addressed. Even though several kinds of digraphs have been addressed in the literature, the most important types of digraphs such as strong digraph, tournament digraph, acyclic digraph, Eulerian digraph, k-partite digraphs, and transitive and quasi-transitive digraph will be pointed out in this section.