Page 623 - Discrete Mathematics and Its Applications

602 9 / Relations

x i+2

x j–2
x i+1
x j–1

a = x 0 x 1 x 2 x i –1 x = x j x j+1 x = b
m
i
FIGURE 2 Producing a Path with Length Not Exceeding n.

Proof: Suppose there is a path from a to b in R. Let m be the length of the shortest such path.
Suppose that x 0 ,x 1 ,x 2 ,...,x m−1 ,x m , where x 0 = a and x m = b, is such a path.
Suppose that a = b and that m>n, so that m ≥ n + 1. By the pigeonhole principle, because
there are n vertices in A, among the m vertices x 0 ,x 1 ,...,x m−1 , at least two are equal (see
Figure 2).
Suppose that x i = x j with 0 ≤ i< j ≤ m − 1. Then the path contains a circuit from
x i to itself. This circuit can be deleted from the path from a to b, leaving a path, namely,
x 0 ,x 1 ,...,x i ,x j+1 ,...,x m−1 ,x m , from a to b of shorter length. Hence, the path of shortest
length must have length less than or equal to n.
The case where a = b is left as an exercise for the reader.
2
3
From Lemma 1, we see that the transitive closure of R is the union of R, R , R ,...,
n
and R . This follows because there is a path in R between two vertices if and only if there is a
∗
i
path between these vertices in R , for some positive integer i with i ≤ n. Because
2
3
∗
R = R ∪ R ∪ R ∪ ··· ∪ R n
and the zero–one matrix representing a union of relations is the join of the zero–one matrices of
these relations, the zero–one matrix for the transitive closure is the join of the zero–one matrices
of the first n powers of the zero–one matrix of R.

THEOREM 3 Let M R be the zero–one matrix of the relation R on a set with n elements. Then the zero–one
∗
matrix of the transitive closure R is
[n]
M R = M R ∨ M [2] ∨ M [3] ∨ ··· ∨ M .
∗
R R R
EXAMPLE 7 Find the zero–one matrix of the transitive closure of the relation R where
⎡ ⎤
1 0 1
M R = ⎣ 0 1 0 ⎦ .
1 1 0

∗
Solution: By Theorem 3, it follows that the zero–one matrix of R is
[3]
M R = M R ∨ M [2] ∨ M .
∗
R R
Because
⎡ ⎤ ⎡ ⎤
1 1 1 1 1 1
M [2] = ⎣ 0 1 0 ⎦ and M [3] = ⎣ 0 1 0 ⎦ ,
R R
1 1 1 1 1 1