Advanced Mathematics

5.2Directed Graphs

Purpose of Section

We introduce the directed graph and its corresponding adjacency matrix and show how directed graphs arise in modern society, including social networks, tournaments, the Google Page Rank system, and the optimization technique of dynamic programming.

5.2.1 Introduction

Thus far in our discussion of graphs, we have not associated a “direction” with the edges of the graph. In many models, however, such as hyperlinks connecting webpages, traffic flow problems, we impose a direction on the edges. A directed graph (or digraph) is defined as a graph whose edges are “directed” from one vertex to another. We call these types of edges directed edges (or arcs). If a directed edge goes from vertex u to vertex v, then u is called the head (or source) and v is called the tail (or sink) of the edge, and v is said to be the direct successor of u and u is the direct predecessor of v. See Figure 5.30.

Figure 5.30 A directed graph with directed edges.

The applications of directed graphs range from transportation problems in which traffic flow is restricted to one direction and one‐way communication problems, to asymmetric social interactions, athletic tournaments, and even the World‐Wide Web. Before talking about applications, however, we introduce the concept of the adjacency matrix of a directed graph.

Definition

The adjacency matrix of a directed ...