Directed Graphs A directed graph is a finite set of points, called nodes, and an associate...

Directed Graphs A directed graph is a finite set of points, called nodes, and an associated set of paths or arcs, each connecting two nodes in a given direction. (See Fig. 6.) Think of the arcs as strings or wires that can pass over or under each other; no actual “contact” takes place except at the nodes.

FIGURE 3.1.6 Directed graph.

Two nodes, i and j, are adjacent if there is an are from i to j. (The are from node 1 to node 3 is distinct from the are from node 3 to node 1; the graph may include one, both, or neither.) If the graph has n nodes, its adjacency matrix is the n × n matrix A = [aij] defined by

(a) Write out the adjacency matrix for the directed graph in Fig. 6.

(b) Calculate the square of the adjacency matrix from part (a). What is the interpretation for the graph of an entry in this matrix? HINT: Two “consecutive” arcs, one from node i to node j, another from node j to node k, together form a “path” of length 2 from node i to node k.