568
Graph Algorithms
17. The two directed graphs that follow have adjacency relations r and s. Draw the graphs associated with
the relations r c s and r d s.
3
2
1
3
2
1
18. The two directed graphs that follow have adjacency relations r and s. Draw the graphs associated with
the relations r c s and r d s.
1
2
3
4
5
1
2
3
4
5
19. Let a be the matrix
a = £
0 1 1
1 1 1
0 0 1
§
Find the products a
2
and a
(2)
.
20. Let a be the matrix
a = ≥
1 1 0 1
0 0 1 0
1 0 0 1
1 0 1 0
¥
Find the products a
2
and a
(2)
.
21. The definition of a connected graph can be extended to directed graphs. Describe the reachability matrix
r for a connected, directed graph.
22. Describe the directed graph with the following reachability matrix r.
r = F
1 1 1 0 0 0
1 1 1 0 0 0
1 1 1 0 0 0
0 0 0 1 1 1
0 0 0 1 1 1
0 0 0 1 1 1
V