Page 626 - Discrete Mathematics and Its Applications

9.4 Closures of Relations 605

W 3 has 1 as its (i, j)th entry if there is a path from v i to v j that has only v 1 = a, v 2 = b,
and/or v 3 = c as its interior vertices, if any. We now have paths from d to a, namely, d, c, a,
and from d to d, namely, d, c, d. Hence,

⎡ ⎤
0 0 0 1
1 0 1 1
⎢ ⎥
W 3 = ⎢ ⎥ .
⎣ 1 0 0 1 ⎦
1 0 1 1

Finally, W 4 has 1 as its (i, j)th entry if there is a path from v i to v j that has v 1 = a, v 2 = b,
v 3 = c, and/or v 4 = d as interior vertices, if any. Because these are all the vertices of the graph,
this entry is 1 if and only if there is a path from v i to v j . Hence,

⎡ ⎤
10 11
⎢ 10 11 ⎥
W 4 = ⎢ ⎥ .
10 11
⎣ ⎦
10 11

This last matrix, W 4 , is the matrix of the transitive closure. ▲

Warshall’s algorithm computes M R by efficiently computing W 0 = M R , W 1 , W 2 ,...,
∗
W n = M R . This observation shows that we can compute W k directly from W k−1 : There is a
∗
path from v i to v j with no vertices other than v 1 , v 2 ,..., v k as interior vertices if and only if
either there is a path from v i to v j with its interior vertices among the first k − 1 vertices in the
list, or there are paths from v i to v k and from v k to v j that have interior vertices only among the
first k − 1 vertices in the list. That is, either a path from v i to v j already existed before v k was
permitted as an interior vertex, or allowing v k as an interior vertex produces a path that goes
from v i to v k and then from v k to v j . These two cases are shown in Figure 4.
The first type of path exists if and only if w [k−1] = 1, and the second type of path exists if
ij
and only if both w [k−1] and w [k−1] are 1. Hence, w [k] is 1 if and only if either w [k−1] is 1 or both
ik kj ij ij
w [k−1] and w [k−1] are 1. This gives us Lemma 2.
ik kj

Case 1
v i v j

All interior vertices
in {v ,v , . . . , v k–1 }
1 2
v k

Case 2

v i All interior vertices v j
}
k
1 2
in {v ,v , . . . , v –1
FIGURE 4 Adding v k to the Set of
Allowable Interior Vertices.