4. Find the corresponding directed graph and adjacency relation for the following adjacency matrix.
A = E
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0
U
5. Given the adjacency relation r = 5(1, 4), (1, 5), (1, 6), (6, 2), (6, 3), (6, 5)6 on the set N = 51, 2, 3, 4, 5, 66,
find the corresponding directed graph and adjacency matrix.
6. Given the adjacency relation r = 5(2, 1), (3, 2), (3, 3), (3, 4), (4, 5), (6, 3), (6, 6)6 on the set N = 51, 2, 3,
4, 5, 66, find the corresponding directed graph and adjacency matrix.
7. Let r be a binary relation defined on the set 50, 1, 2, 3, 4, 5, 66 by x r y 4 y = x + 2. Draw the associated directed graph.
8. Let r be a binary relation defined on the set 50, ±1, ±2, ±4, ±166 by x r y 4 y = x
2
. Draw the associated
directed graph.
9. Describe a property of a directed graph whose adjacency matrix is symmetric.
10. Describe the directed graph whose adjacency matrix has all 0s on the main diagonal and 1s everywhere
else.
11. Describe the directed graph whose adjacency matrix has all 1s in row 1 and column 1, and 0s elsewhere.
12. Describe the directed graph whose adjacency matrix has 1s in positions (i, i + 1) for 1 ≤ i ≤ n − 1, a
1 in position (n, 1), and 0s elsewhere.
13. Describe a property of a directed graph whose adjacency relation is irreflexive (see Exercise 26,
Section 5.1).
14. Describe a property of the adjacency matrix of a graph whose adjacency relation is antisymmetric.
15. Adjacency relations r and s have the following associated adjacency matrices R and S. Find the adjacency matrices associated with the relations r c s and r d s.
R = £
1 0 1
1 1 0
0 0 1
§ S = £
1 0 0
1 0 1
0 0 1
§
16. Adjacency relations r and s have the following associated adjacency matrices R and S. Find the adjacency matrices associated with the relations r c s and r d s.
R = ≥
0 1 1 0
0 0 0 1
1 1 0 0
1 0 0 1
¥ S = ≥
0 1 0 0
0 0 1 0
1 0 0 1
1 0 0 0
¥
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
567
A = E
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0
0 1 0 0 0
0 0 0 1 0
U
5. Given the adjacency relation r = 5(1, 4), (1, 5), (1, 6), (6, 2), (6, 3), (6, 5)6 on the set N = 51, 2, 3, 4, 5, 66,
find the corresponding directed graph and adjacency matrix.
6. Given the adjacency relation r = 5(2, 1), (3, 2), (3, 3), (3, 4), (4, 5), (6, 3), (6, 6)6 on the set N = 51, 2, 3,
4, 5, 66, find the corresponding directed graph and adjacency matrix.
7. Let r be a binary relation defined on the set 50, 1, 2, 3, 4, 5, 66 by x r y 4 y = x + 2. Draw the associated directed graph.
8. Let r be a binary relation defined on the set 50, ±1, ±2, ±4, ±166 by x r y 4 y = x
2
. Draw the associated
directed graph.
9. Describe a property of a directed graph whose adjacency matrix is symmetric.
10. Describe the directed graph whose adjacency matrix has all 0s on the main diagonal and 1s everywhere
else.
11. Describe the directed graph whose adjacency matrix has all 1s in row 1 and column 1, and 0s elsewhere.
12. Describe the directed graph whose adjacency matrix has 1s in positions (i, i + 1) for 1 ≤ i ≤ n − 1, a
1 in position (n, 1), and 0s elsewhere.
13. Describe a property of a directed graph whose adjacency relation is irreflexive (see Exercise 26,
Section 5.1).
14. Describe a property of the adjacency matrix of a graph whose adjacency relation is antisymmetric.
15. Adjacency relations r and s have the following associated adjacency matrices R and S. Find the adjacency matrices associated with the relations r c s and r d s.
R = £
1 0 1
1 1 0
0 0 1
§ S = £
1 0 0
1 0 1
0 0 1
§
16. Adjacency relations r and s have the following associated adjacency matrices R and S. Find the adjacency matrices associated with the relations r c s and r d s.
R = ≥
0 1 1 0
0 0 0 1
1 1 0 0
1 0 0 1
¥ S = ≥
0 1 0 0
0 0 1 0
1 0 0 1
1 0 0 0
¥
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
567