23. For the following graph, write the reachability matrix r by simply inspecting the graph.
2
3
4
1
24. For the following graph, write the reachability matrix r by simply inspecting the graph.
5
4
2
1
3
For Exercises 25–30, compute the reachability matrix r by using the formula r = a ~ a
(2) ~ c~ a
(n)
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
569
25. Exercise 1
26. Exercise 2
27. Exercise 3
28. Exercise 4
29. Exercise 5
30. Exercise 6
For Exercises 31–36, compute the reachability matrix r by using Warshall’s algorithm.
31. Exercise 1
32. Exercise 2
33. Exercise 3
34. Exercise 4
35. Exercise 5
36. Exercise 6
37. Given the binary relation r = 5(1, 3), (3, 2), (2, 3)6 on the set 51, 2, 36, use Warshall’s algorithm to find
the transitive closure of r.
38. Given the binary relation r = 5(1, 2), (2, 3), (4, 1)6 on the set 51, 2, 3, 46, use Warshall’s algorithm to
find the transitive closure of r.
39. Use Warshall’s algorithm to find the transitive closure of the following binary relations on the set 51, 2, 36
(see Exercise 23 in Section 5.1).
a. r = 5(1, 3), (3, 3), (3, 1), (2, 2), (2, 3), (1, 1), (1, 2)6
b. r = 5(1, 1), (3, 3), (2, 2)6
c. r = 5(1, 1), (1, 2), (2, 3), (3, 1), (1, 3)6
d. r = 5(1, 1), (1, 2), (2, 3), (1, 3)6
40. Use Warshall’s algorithm to find the transitive closure of the following binary relations on the set
50, 1, 2, 4, 66 (see Exercise 24 in Section 5.1).
a. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)6
b. r = 5(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)6
c. r = 5(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)6
d. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)6
e. r = [
2
3
4
1
24. For the following graph, write the reachability matrix r by simply inspecting the graph.
5
4
2
1
3
For Exercises 25–30, compute the reachability matrix r by using the formula r = a ~ a
(2) ~ c~ a
(n)
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
569
25. Exercise 1
26. Exercise 2
27. Exercise 3
28. Exercise 4
29. Exercise 5
30. Exercise 6
For Exercises 31–36, compute the reachability matrix r by using Warshall’s algorithm.
31. Exercise 1
32. Exercise 2
33. Exercise 3
34. Exercise 4
35. Exercise 5
36. Exercise 6
37. Given the binary relation r = 5(1, 3), (3, 2), (2, 3)6 on the set 51, 2, 36, use Warshall’s algorithm to find
the transitive closure of r.
38. Given the binary relation r = 5(1, 2), (2, 3), (4, 1)6 on the set 51, 2, 3, 46, use Warshall’s algorithm to
find the transitive closure of r.
39. Use Warshall’s algorithm to find the transitive closure of the following binary relations on the set 51, 2, 36
(see Exercise 23 in Section 5.1).
a. r = 5(1, 3), (3, 3), (3, 1), (2, 2), (2, 3), (1, 1), (1, 2)6
b. r = 5(1, 1), (3, 3), (2, 2)6
c. r = 5(1, 1), (1, 2), (2, 3), (3, 1), (1, 3)6
d. r = 5(1, 1), (1, 2), (2, 3), (1, 3)6
40. Use Warshall’s algorithm to find the transitive closure of the following binary relations on the set
50, 1, 2, 4, 66 (see Exercise 24 in Section 5.1).
a. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (0, 1), (1, 2), (2, 4), (4, 6)6
b. r = 5(0, 1), (1, 0), (2, 4), (4, 2), (4, 6), (6, 4)6
c. r = 5(0, 1), (1, 2), (0, 2), (2, 0), (2, 1), (1, 0), (0, 0), (1, 1), (2, 2)6
d. r = 5(0, 0), (1, 1), (2, 2), (4, 4), (6, 6), (4, 6), (6, 4)6
e. r = [