Page 625 - Discrete Mathematics and Its Applications

604 9 / Relations

are c, d, f, g, h, and b. The interior vertices of a, c, d, a, f, b are c, d, a, and f . (Note that the
first vertex in the path is not an interior vertex unless it is visited again by the path, except as
the last vertex. Similarly, the last vertex in the path is not an interior vertex unless it was visited
previously by the path, except as the first vertex.)
Warshall’s algorithm is based on the construction of a sequence of zero–one matrices. These
matrices are W 0 , W 1 ,..., W n , where W 0 = M R is the zero–one matrix of this relation, and
(k) (k)
W k =[w ], where w = 1 if there is a path from v i to v j such that all the interior vertices of
ij ij
this path are in the set {v 1 , v 2 ,..., v k } (the first k vertices in the list) and is 0 otherwise. (The
first and last vertices in the path may be outside the set of the first k vertices in the list.) Note
∗
∗
that W n = M R , because the (i, j)th entry of M R is 1 if and only if there is a path from v i
to v j , with all interior vertices in the set {v 1 , v 2 ,..., v n } (but these are the only vertices in the
directed graph). Example 8 illustrates what the matrix W k represents.
EXAMPLE 8 Let R be the relation with directed graph shown in Figure 3. Let a, b, c, d be a listing of the
elements of the set. Find the matrices W 0 , W 1 , W 2 , W 3 , and W 4 . The matrix W 4 is the transitive
a b closure of R.

Solution: Let v 1 = a, v 2 = b, v 3 = c, and v 4 = d. W 0 is the matrix of the relation. Hence,
⎡ ⎤
0 0 0 1
⎢ 1 0 1 0 ⎥
d c W 0 = ⎢ ⎥ .
⎣ 1 0 0 1 ⎦
0 0 1 0
FIGURE 3
The Directed W 1 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 as an interior
Graph of the vertex. Note that all paths of length one can still be used because they have no interior vertices.
Relation R.
Also, there is now an allowable path from b to d, namely, b, a, d. Hence,

⎡ ⎤
0 0 0 1
⎢ 1 0 1 1 ⎥
W 1 = ⎢ ⎥ .
1 0 0 1
⎣ ⎦
0 0 1 0
W 2 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 and/or v 2 = b
as its interior vertices, if any. Because there are no edges that have b as a terminal vertex, no
new paths are obtained when we permit b to be an interior vertex. Hence, W 2 = W 1 .

STEPHEN WARSHALL (1935–2006) Stephen Warshall, born in New York City, went to public school in
Brooklyn. He attended Harvard University, receiving his degree in mathematics in 1956. He never received an
advanced degree, because at that time no programs were available in his areas of interest. However, he took
graduate courses at several different universities and contributed to the development of computer science and
software engineering.
After graduating from Harvard, Warshall worked at ORO (Operation Research Office), which was set
up by Johns Hopkins to do research and development for the U.S. Army. In 1958 he left ORO to take a
position at a company called Technical Operations, where he helped build a research and development labo-
ratory for military software projects. In 1961 he left Technical Operations to found Massachusetts Computer
Associates. Later, this company became part of Applied Data Research (ADR). After the merger, Warshall sat on the board of
directors of ADR and managed a variety of projects and organizations. He retired from ADR in 1982.
During his career Warshall carried out research and development in operating systems, compiler design, language design, and
operations research. In the 1971–1972 academic year he presented lectures on software engineering at French universities. There is
an interesting anecdote about his proof that the transitive closure algorithm, now known as Warshall’s algorithm, is correct. He and
a colleague at Technical Operations bet a bottle of rum on who first could determine whether this algorithm always works. Warshall
came up with his proof overnight, winning the bet and the rum, which he shared with the loser of the bet. Because Warshall did not
like sitting at a desk, he did much of his creative work in unconventional places, such as on a sailboat in the Indian Ocean or in a
Greek lemon orchard.