570
Graph Algorithms
41. The following directed graph represents a binary relation r on the nodes. Draw the directed graph that
would represent the transitive closure of r.
42. The following directed graph represents a binary relation r on the nodes. Draw the directed graph that
would represent the transitive closure of r.
Exercises 43–46 use regular matrix multiplication to obtain information about a graph.
43. Let G be a directed graph, possibly with parallel arcs, and let a be its adjacency matrix. Then a may not
be a Boolean matrix. Prove that the i, j entry of matrix a
2
is the number of paths of length 2 from node i
to node j.
44. Let a be the adjacency matrix of a directed graph G, possibly with parallel arcs. Prove that the i, j entry
of matrix a
n
gives the number of paths of length n from node i to node j.
45. For the following graph, count the number of paths of length 2 from node 1 to node 3. Check by
computing a
2
.
3
4
2
1
46. For the following graph, count the number of paths of length 4 from node 1 to node 5. Check by
computing a
4
.
4
5
2
1
3