These matrices indicate, for example, that there is a path of length 2 from 2 to 1
because a
(2)
32, 14 = 1 (the path is 2–3–1), and there is a path of length 4 from 5 to
3 because, a
(4)
35, 34 = 1 (the path is 5–3–1–2–3), but there is no path of length 3
from 1 to 3 because a
(3)
31, 34 = 0.
The reachability matrix r is the Boolean sum of a, a
(2)
, a
(3)
, a
(4)
, and a
(5)
:
r = E
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
1 1 1 1 0
U
The 1 values in r indicate that there are paths in G from nodes 1, 2, 3, and 5 to
every node except 5, but no path from node 4 to anywhere, which can be confirmed
by looking at Figure 7.3.
We have proved that the 1 entries in r mark the ordered pairs of nodes that
belong to the transitive closure of r. The transitive closure will therefore be the
following set of ordered pairs:
5(l, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 3), (3, 4), (5, 1), (5, 2), (5, 3), (5, 4)6
Beginning with r and following the ad hoc procedure described in Chapter 5 for
finding the transitive closure of a relation, we see that to obtain transitivity, we must
first add the pairs (1, 3), (2, 1), (2, 4), (3, 2), (5, 2), and (5, 4). Reviewing the new set,
we see that we must also add (1, 1), (1, 4), (2, 2), and (3, 3). The resulting collection
of ordered pairs is transitive (and agrees with what we obtained earlier).
praCtiCe 5 Compute r for the directed graph of Figure 7.2. What information does column 2 convey?
In Chapter 5, we promised a better algorithm to find the transitive closure
of a relation. Here it is. Write the binary relation in adjacency matrix form and
compute
r = a ~ a
(2) ~ c~ a
(n)
How much work is required to carry out this algorithm? The expression for r
indicates that Boolean matrix operations are to be done, but matrix operations in
turn require Boolean and and Boolean or operations on matrix elements. We will
therefore use Boolean and and Boolean or as the measure of work. In Section 5.7,
we noted that ordinary matrix multiplication of two n × n matrices requires
Θ(n
3
) multiplications and additions; by a similar argument, Boolean matrix
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
561
■
because a
(2)
32, 14 = 1 (the path is 2–3–1), and there is a path of length 4 from 5 to
3 because, a
(4)
35, 34 = 1 (the path is 5–3–1–2–3), but there is no path of length 3
from 1 to 3 because a
(3)
31, 34 = 0.
The reachability matrix r is the Boolean sum of a, a
(2)
, a
(3)
, a
(4)
, and a
(5)
:
r = E
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
1 1 1 1 0
U
The 1 values in r indicate that there are paths in G from nodes 1, 2, 3, and 5 to
every node except 5, but no path from node 4 to anywhere, which can be confirmed
by looking at Figure 7.3.
We have proved that the 1 entries in r mark the ordered pairs of nodes that
belong to the transitive closure of r. The transitive closure will therefore be the
following set of ordered pairs:
5(l, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4),
(3, 1), (3, 2), (3, 3), (3, 4), (5, 1), (5, 2), (5, 3), (5, 4)6
Beginning with r and following the ad hoc procedure described in Chapter 5 for
finding the transitive closure of a relation, we see that to obtain transitivity, we must
first add the pairs (1, 3), (2, 1), (2, 4), (3, 2), (5, 2), and (5, 4). Reviewing the new set,
we see that we must also add (1, 1), (1, 4), (2, 2), and (3, 3). The resulting collection
of ordered pairs is transitive (and agrees with what we obtained earlier).
praCtiCe 5 Compute r for the directed graph of Figure 7.2. What information does column 2 convey?
In Chapter 5, we promised a better algorithm to find the transitive closure
of a relation. Here it is. Write the binary relation in adjacency matrix form and
compute
r = a ~ a
(2) ~ c~ a
(n)
How much work is required to carry out this algorithm? The expression for r
indicates that Boolean matrix operations are to be done, but matrix operations in
turn require Boolean and and Boolean or operations on matrix elements. We will
therefore use Boolean and and Boolean or as the measure of work. In Section 5.7,
we noted that ordinary matrix multiplication of two n × n matrices requires
Θ(n
3
) multiplications and additions; by a similar argument, Boolean matrix
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
561
■