560
Graph Algorithms
transitive, (n i , n j ) belongs to s, and r
r
is a subset of s. Therefore r
r
is the transitive
closure of r.
To summarize, corresponding to the three equivalent representations of adjacency relation r, directed graph G, and adjacency matrix a, we have
(n i , n j ) belongs
to the transitive 4
n j is reachable 4
r3i, j 4 = 1where
closure of r
from n i in G
r = a ~ a
(2) ~ c ~ a
(n)
example 5
Let G be the directed graph in Figure 7.3; G has 5 nodes.
2
5
3
1
4
Figure 7.3
The adjacency matrix a for G is
a = E
0 1 0 0 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 0
1 0 1 0 0
U
The adjacency relation r is r = 5(1, 2), (2, 3), (3, 1), (3, 4), (5, 1), (5, 3)6.
The successive powers of a are
a
(2)
= E
0 0 1 0 0
1 0 0 1 0
0 1 0 0 0
0 0 0 0 0
1 1 0 1 0
U
a
(3)
= E
1 0 0 1 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 0
0 1 1 0 0
U
a
(4)
= E
0 1 0 0 0
0 0 1 0 0
1 0 0 1 0
0 0 0 0 0
1 0 1 1 0
U
a
(5)
= E
0 0 1 0 0
1 0 0 1 0
0 1 0 0 0
0 0 0 0 0
1 1 0 1 0
U
ReminDeR
Don’t try to compute
matrix products without
writing the two matrices
side by side; you’ll surely
make a mistake.