566
Graph Algorithms
S e c t i o n 7 . 1 revieW
tecHniQueS
• Find any two of the adjacency relation, directed
graph, or adjacency matrix representation, given
the third.
• Compute the reachability matrix r for a graph G
(or, equivalently, find the transitive closure of the
adjacency relation on G) by using the formula
r = a ~ a
(2) ~ c~ a
(n)
and by using Warshall’s algorithm.
main iDeaS
• There is a one-to-one correspondence between a directed graph G with no parallel arcs, the adjacency
relation on G, and the adjacency matrix for G (with
respect to some arbitrary ordering of the nodes).
• The reachability matrix of a graph G also represents
the transitive closure of the adjacency relation on G.
• The reachability matrix for a graph can be computed with Θ(n
4
) Boolean and/or operations by
summing powers of the adjacency matrix a or with
Θ(n
3
) Boolean and/or operations by using Warshall’s algorithm.
W
exeRciSeS 7.1
1. Find the adjacency matrix and adjacency relation for the following graph.
3
2
1
2. Find the adjacency matrix and adjacency relation for the following graph.
3
4
1
2
3. Find the corresponding directed graph and adjacency relation for the following adjacency matrix.
a = E
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
0 1 0 0 0
0 0 1 1 0
U