If node n j is reachable from node n i , it is by a path of some length. Such a
path will be shown by a 1 as the i, j entry in a or a
(2)
or a
(3)
and so on, but we
cannot compute an infinite number of matrix products. Fortunately, there is a
limit to how far in this list we have to look. If there are n nodes in the graph, then
any path with n or more arcs, and therefore n + 1 or more nodes, must have a
repeated node. This is a consequence of the pigeonhole principle—there are n
“bins” (distinct nodes) into which we are putting more than n objects (the nodes
in a path with n or more arcs). The section of a path lying between the repeated
nodes is a cycle. If n i ∙ n j , the cycle can be eliminated to make a shorter path;
then if a path exists from n i to n j , there will be such a path of length at most n − 1.
If n i = n j , then the cycle could be the entire path from n i to n i with maximum
length n; although we could eliminate this cycle (noting that any node may be
considered reachable from itself), we will retain it to show that a nontrivial path
does exist from n i to n i .
Consequently, whether n i = n j or n i ∙ n j , we need never look for a path from
n i to n j of length greater than n. Therefore to determine reachability, we need only
consult element i, j in a, a
(2)
, … , a
(n)
. Alternatively, we can define a reachability
matrix r by
r = a ~ a
(2) ~ c ~ a
(n)
Then n j is reachable from n i if and only if entry i, j in r is positive.
We now see how reachability in a graph can be expressed in terms of the adjacency matrix. How is reachability represented in terms of the adjacency relation
that corresponds to the graph?
If r is the adjacency relation for a graph G, we let r
r
denote the binary relation of reachability; that is, (n i , n j ) [ r
r
exactly when there is a path in G from
n i to n j . Then we can show that r
r
is the transitive closure of r. Recall from the
definition of closure of a relation that the transitive closure of r is a relation that is
transitive, contains r, and is a subset of any transitive relation containing r.
To see that r
r
is transitive, let (n i , n j ) and (n j , n k ) belong to r
r
. Then there is
a path in G from n i to n j and a path in G from n j to n k . Therefore there is a path
in G from n i to n k , and (n i , n k ) belongs to r
r
. To see that r
r
contains r, let (n i , n j )
belong to r. Then there is an arc from n i to n j in G, which means there is a path of
length 1 from n i to n j , and (n i , n j ) belongs to r
r
. Finally, suppose s is any transitive relation on the nodes of G that includes r, and let (n i , n j ) belong to r
r
. This
means that there is a path from n i to n j using, say, nodes n i , n x , n y , … , n w , n j . Then
there is an arc from each node in this path to the next, and the ordered pairs (n i , n x ),
(n x , n y ), … , (n w , n j ), all belong to r, and therefore all belong to s. Because s is
praCtiCe 4 From the graph of Figure 7.2, what would you expect for the value of entry 2,1 in a
(4)
?
Compute a
(4)
and check this value.
of length p from n i to n q (by the inductive hypothesis) and there is a path of length 1
from n q to n j , which means there is a path of length p + 1 from n i to n j . End of proof.
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
559
■
path will be shown by a 1 as the i, j entry in a or a
(2)
or a
(3)
and so on, but we
cannot compute an infinite number of matrix products. Fortunately, there is a
limit to how far in this list we have to look. If there are n nodes in the graph, then
any path with n or more arcs, and therefore n + 1 or more nodes, must have a
repeated node. This is a consequence of the pigeonhole principle—there are n
“bins” (distinct nodes) into which we are putting more than n objects (the nodes
in a path with n or more arcs). The section of a path lying between the repeated
nodes is a cycle. If n i ∙ n j , the cycle can be eliminated to make a shorter path;
then if a path exists from n i to n j , there will be such a path of length at most n − 1.
If n i = n j , then the cycle could be the entire path from n i to n i with maximum
length n; although we could eliminate this cycle (noting that any node may be
considered reachable from itself), we will retain it to show that a nontrivial path
does exist from n i to n i .
Consequently, whether n i = n j or n i ∙ n j , we need never look for a path from
n i to n j of length greater than n. Therefore to determine reachability, we need only
consult element i, j in a, a
(2)
, … , a
(n)
. Alternatively, we can define a reachability
matrix r by
r = a ~ a
(2) ~ c ~ a
(n)
Then n j is reachable from n i if and only if entry i, j in r is positive.
We now see how reachability in a graph can be expressed in terms of the adjacency matrix. How is reachability represented in terms of the adjacency relation
that corresponds to the graph?
If r is the adjacency relation for a graph G, we let r
r
denote the binary relation of reachability; that is, (n i , n j ) [ r
r
exactly when there is a path in G from
n i to n j . Then we can show that r
r
is the transitive closure of r. Recall from the
definition of closure of a relation that the transitive closure of r is a relation that is
transitive, contains r, and is a subset of any transitive relation containing r.
To see that r
r
is transitive, let (n i , n j ) and (n j , n k ) belong to r
r
. Then there is
a path in G from n i to n j and a path in G from n j to n k . Therefore there is a path
in G from n i to n k , and (n i , n k ) belongs to r
r
. To see that r
r
contains r, let (n i , n j )
belong to r. Then there is an arc from n i to n j in G, which means there is a path of
length 1 from n i to n j , and (n i , n j ) belongs to r
r
. Finally, suppose s is any transitive relation on the nodes of G that includes r, and let (n i , n j ) belong to r
r
. This
means that there is a path from n i to n j using, say, nodes n i , n x , n y , … , n w , n j . Then
there is an arc from each node in this path to the next, and the ordered pairs (n i , n x ),
(n x , n y ), … , (n w , n j ), all belong to r, and therefore all belong to s. Because s is
praCtiCe 4 From the graph of Figure 7.2, what would you expect for the value of entry 2,1 in a
(4)
?
Compute a
(4)
and check this value.
of length p from n i to n q (by the inductive hypothesis) and there is a path of length 1
from n q to n j , which means there is a path of length p + 1 from n i to n j . End of proof.
Section 7.1 Directed Graphs and Binary Relations; Warshall’s Algorithm
559
■