558
Graph Algorithms
be undesirable to have some node be unreachable from some other node. Thus the
ability to test reachability has very practical applications.
The adjacency matrix a of a directed graph G with n nodes and no parallel
arcs will have a 1 in position i, j if there is an arc from n i to n j . This would be a
path of length 1 from n i to n j . The adjacency matrix by itself therefore tells us
about a limited form of reachability, via length-1 paths. However, let us perform
the Boolean matrix multiplication a × a. We’ll denote this product by a
(2)
to
distinguish it from a
2
, the result of a # a using ordinary matrix multiplication.
Recalling from Section 5.7 the definition of Boolean matrix multiplication, the
i, j entry of a
(2)
is given by
a
(2)
3i, j 4 = ~
n
k=1
(a ik ` a kj )
(4)
If a term such as a i2 ` a 2j in this sum is 0, then either a i2 = 0 or a 2j = 0 (or
both), and there is either no path of length 1 from n i to n 2 or no path of length 1
from n 2 to n j (or both). Thus there are no paths of length 2 from n i to n j passing
through n 2 . If a i2 ` a 2j is not 0, then both a i2 = 1 and a 2j = 1. Then there is a path
of length 1 from n i to n 2 and a path of length 1 from n 2 to n j , so there is a path of
length 2 from n i to n j passing through n 2 . A path of length 2 from n i to n j will exist
if and only if there is a path of length 2 passing through at least one of the nodes
from 1 to n, that is, if and only if at least one of the terms in the sum (4) is 1 and
therefore a
(2)
3i, j 4 = 1. Therefore the entries in a
(2)
tell us about reachability via
length-2 paths.
ReminDeR
To compute A
(2) [i, j] write
two copies of A side by
side. Run a left-hand
finger along row i of the
left copy and a right-hand
finger down column j of
the right copy. The value
is 1 if and only if both
fingers hit a 1 at the same
time.
praCtiCe 3 Find a for the graph of Figure 7.2 and compute a
(2)
. What does the 2,1 entry indicate?
The matrix a
(2)
indicates the presence or absence of length-2 paths. We might
surmise that this result holds for arbitrary powers and path lengths.
tHeoRem oN BooleAN ADjAceNcy MAtRices AND ReAchABility
If a is the Boolean adjacency matrix for a directed graph G with n nodes and no
parallel arcs, then a
(m)
3i, j 4 = 1 if and only if there is a path of length m from
node n i to node n j .
Proof: A proof by induction on m is called for. We have already shown the result
true for m = 1 (and m = 2). Suppose that a
( p)
3i, j 4 = 1 if and only if there is a
path of length p from n i to n j . We know that
a
( p+1)
3i, j 4 = ~
n
k=1
(a
( p)
3i, k 4 ` a kj )
which will equal 1 if and only if at least one term, say a
( p)
3i, q4 ` a q j = 1, or
a
(p)
3i, q4 = 1 and a q j = 1. This condition will be true if and only if there is a path
■
Graph Algorithms
be undesirable to have some node be unreachable from some other node. Thus the
ability to test reachability has very practical applications.
The adjacency matrix a of a directed graph G with n nodes and no parallel
arcs will have a 1 in position i, j if there is an arc from n i to n j . This would be a
path of length 1 from n i to n j . The adjacency matrix by itself therefore tells us
about a limited form of reachability, via length-1 paths. However, let us perform
the Boolean matrix multiplication a × a. We’ll denote this product by a
(2)
to
distinguish it from a
2
, the result of a # a using ordinary matrix multiplication.
Recalling from Section 5.7 the definition of Boolean matrix multiplication, the
i, j entry of a
(2)
is given by
a
(2)
3i, j 4 = ~
n
k=1
(a ik ` a kj )
(4)
If a term such as a i2 ` a 2j in this sum is 0, then either a i2 = 0 or a 2j = 0 (or
both), and there is either no path of length 1 from n i to n 2 or no path of length 1
from n 2 to n j (or both). Thus there are no paths of length 2 from n i to n j passing
through n 2 . If a i2 ` a 2j is not 0, then both a i2 = 1 and a 2j = 1. Then there is a path
of length 1 from n i to n 2 and a path of length 1 from n 2 to n j , so there is a path of
length 2 from n i to n j passing through n 2 . A path of length 2 from n i to n j will exist
if and only if there is a path of length 2 passing through at least one of the nodes
from 1 to n, that is, if and only if at least one of the terms in the sum (4) is 1 and
therefore a
(2)
3i, j 4 = 1. Therefore the entries in a
(2)
tell us about reachability via
length-2 paths.
ReminDeR
To compute A
(2) [i, j] write
two copies of A side by
side. Run a left-hand
finger along row i of the
left copy and a right-hand
finger down column j of
the right copy. The value
is 1 if and only if both
fingers hit a 1 at the same
time.
praCtiCe 3 Find a for the graph of Figure 7.2 and compute a
(2)
. What does the 2,1 entry indicate?
The matrix a
(2)
indicates the presence or absence of length-2 paths. We might
surmise that this result holds for arbitrary powers and path lengths.
tHeoRem oN BooleAN ADjAceNcy MAtRices AND ReAchABility
If a is the Boolean adjacency matrix for a directed graph G with n nodes and no
parallel arcs, then a
(m)
3i, j 4 = 1 if and only if there is a path of length m from
node n i to node n j .
Proof: A proof by induction on m is called for. We have already shown the result
true for m = 1 (and m = 2). Suppose that a
( p)
3i, j 4 = 1 if and only if there is a
path of length p from n i to n j . We know that
a
( p+1)
3i, j 4 = ~
n
k=1
(a
( p)
3i, k 4 ` a kj )
which will equal 1 if and only if at least one term, say a
( p)
3i, q4 ` a q j = 1, or
a
(p)
3i, q4 = 1 and a q j = 1. This condition will be true if and only if there is a path
■