Page 277, Exercise 2 (a)
| 0 | 1 | 2 | 3 | 4 | 5 | Out-Degree | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 | 2 |
| 2 | 0 | 1 | 0 | 0 | 0 | 1 | 2 |
| 3 | 0 | 0 | 1 | 0 | 1 | 1 | 3 |
| 4 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 5 | 1 | 1 | 0 | 0 | 1 | 0 | 3 |
| In-Degree | 3 | 2 | 1 | 1 | 2 | 2 |
2(b) Adjacency list
Vertex 0 NULL Vertex 1 -> 0 -> 3 -> NULL Vertex 2 -> 1 -> 5 -> NULL Vertex 3 -> 2 -> 4 -> 5 -> NULL Vertex 4 -> 0 -> NULL Vertext 5 -> 0 -> 1 -> 4 -> NULL2(C) ADJACENCY MULTII-LIST
HeadNodes Multilist Nodes
______________________________________________________________________________________________
0 NULL N1 -> 1 ->0 ->N2 ->NULL edge (1,0)
1 -> N1 N2 -> 1 ->3 ->NULL ->N5 edge(1,3)
2 -> N3 N3 -> 2 ->1 ->N4 ->NULL edge(2,1)
3 -> N5 N4 -> 2 ->5 ->NULL ->N9 edge(2,5)
4 -> N8 N5 -> 3 ->2 ->N6 ->NULL edge(3,2)
5 -> N9 N6 -> 3 ->4 ->N7 ->N8 edge(3,4)
N7 -> 3 ->5 ->NULL ->N9 edge(3,5)
N8 -> 4 ->0 ->NULL ->NULL edge(4,0)
N9 -> 5 ->0 ->N10 ->NULL edge(5,0)
N10 -> 5 ->1 ->N11 ->NULL edge(5,1)
N11 -> 5 ->4 ->NULL ->NULL edge(5,4)
The lists are:
vertex 0: NULL
vertex 1: N1 N2
vertex 2: N3 N4
vertex 3: N5 N6 N7
vertex 4: N8
vertex 5: N9 N10 N11
(e)
Since node 0 has an out-degree of 0, it is not strongly
connected. Similarly, since node 4's only outward node is adjacent to node 0, it is not strongly connected. The remaining
nodes are all strongly connected as the table below illustrates.
V i V j v i ->v j v j -> v i
1 2 <1,3><3,2> <1,2>
1 3 <1,3> <3,2><2,1>
1 5 <1,3><3,5> <5,1>
2 3 <2,1><1,3> <3,2>
2 5 <2,5> <5,1><1,3><3,2>
3 5 <3,5> <5,1><1,3>