Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Alireza Boloori (Wayne State University, USA) and Monirehalsadat Mahmoudi (Amirkabir University of Technology, Iran)

Source Title: Graph Theory for Operations Research and Management: Applications in Industrial Engineering

Copyright: © 2013
|Pages: 8
DOI: 10.4018/978-1-4666-2661-4.ch011

Chapter Preview

TopFrom 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 *G _{D}* = (

*•***Order (size):**The number of vertices in*G*that is denoted by |_{D}*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 (*V*Í_{S}*V*), the in-degree of*V*is the number of edges whose heads are in_{S}*V*and tails are in_{S}*V*-*V*. Conversely, the out-degree of_{S}*V*is the number of edges whose heads are in_{S}*V*-*V*and tails are in_{S}*V*._{S}

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.

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

Search this Book:

Reset