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. 3. 1 .6.) Think of the arcs as strings or wires that can pass over or under each other; n o actual "contact" takes place except at the nodes.

Figure 3.1.6 Directed graph (Problem 92)
Two nodes, i and j, are adjacent if there is an arc from i to j . (The arc from node I to node 3 is distinct from the arc 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 x n matrix A = [aij] defined by

(a) Write out the adjacency matrix for the directed graph in Fig. 3.1.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? 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

Transcribed Image Text:

4 3 5 2 if there is an arc from node i to node j. リ IJ 0 f there isno such arc