Discrete Mathematics for Computer Science

Subsection 10.5.1 Transitive Closure

Consider a telephone network in which the main office \(a\) is connected to, and can communicate to, individuals \(b\) and \(c\text{.}\) Both \(b\) and \(c\) can communicate to another person, \(d\text{;}\) however, the main office cannot communicate with \(d\text{.}\) Assume communication is only one way, as indicated. This situation can be described by the relation \(R = \{(a, b), (a, c), (b, d), (c, d)\}\text{.}\) We would like to change the system so that the main office \(a\) can communicate with person \(d\) and still maintain the previous system. We, of course, want the most economical system.

This can be rephrased as follows; Find the smallest relation \(R^{+ }\) which contains \(R\) as a subset and which is transitive; \(R^+ =\{(a, b), (a, c), (b, d), (c, d), (a, d)\}\text{.}\)

Let \(A = \{1, 2, 3, 4\}\text{,}\) and let \(\mathcal{S} = \{(1, 2), (2, 3), (3, 4)\}\) be a relation on \(A\text{.}\) This relation is called the successor relation on \(A\) since each element is related to its successor. How do we compute \(\mathcal{S}^+\text{?}\) By inspection we note that \((1, 3)\) must be in \(\mathcal{S}^+\) . Let's analyze why. This is so because \((1,2) \in \mathcal{S}\) and \((2, 3) \in \mathcal{S}\text{,}\) and the transitive property forces \((1,3)\) to be in \(\mathcal{S}^+\text{.}\)

In general, it follows that if \((a, b) \in \mathcal{S}\) and \((b, c) \in S,\) then \((a, c) \in \mathcal{S}^+ \text{.}\) This condition is exactly the membership requirement for the pair \((a, c)\) to be in the composition \(\mathcal{S}\mathcal{S} = \mathcal{S}^2\text{.}\) So every element in \(\mathcal{S}^2\) must be an element in \(\mathcal{S}^+\) . So we now know that, \(\mathcal{S}^+\) contains at least \(\mathcal{S} \cup \mathcal{S}^2\) . In particular, for this example, since \(\mathcal{S} = \{(1, 2), (2, 3), (3, 4)\}\) and \(\mathcal{S}^2 = \{(1, 3), (2, 4)\}\text{,}\) we have

Is the relation \(\mathcal{S} \cup \mathcal{S}^2\) transitive? Again, by inspection, \((1, 4)\) is not an element of \(\mathcal{S} \cup \mathcal{S}^2\text{,}\) but \((1,3) \in \mathcal{S}^2\) and \((3, 4) \in \mathcal{S}\text{.}\) Therefore, the composition \(\mathcal{S}^2 \mathcal{S} = \mathcal{S}^3\) produces \((1, 4)\text{,}\) and it must be an element of \(\mathcal{S}^+\) since \((1,3)\) and \((3, 4)\) are required to be in \(\mathcal{S}^+\text{.}\) This shows that \(\mathcal{S}^3 \subseteq \mathcal{S}^+\text{.}\) This process must be continued until the resulting relation is transitive. If \(A\) is finite, as is true in this example, the transitive closure will be obtained in a finite number of steps. For this example,

Let's now consider the matrix analogue of the transitive closure.

Consider the relation

on the set \(A = \{1,2, 3, 4, 5\}\text{.}\) The matrix of \(R\) is

Recall that \(R^2, R^3, \ldots\) can be determined through computing the matrix powers \(M^2, M^3, \ldots\text{.}\) For our example,

How do we relate \(\underset{i=1}{\overset{5}{\cup }}R^i\) to the powers of \(M\text{?}\)

Using this theorem, we find \(M^+\) is the \(5\times 5\) matrix consisting of all \(1's\text{,}\) thus, \(R^+\) is all of \(A \times A\text{.}\)

Subsection 10.5.2 Algorithms for computing transitive closure

Let \(R\) be a relation on the set \(\{1, 2, \dots , n\}\) with relation matrix \(M\text{.}\) The matrix of the transitive closure \(M^+\text{,}\) can be computed by the equation \(M^+ = M + M ^2 + \cdots + M^n\text{.}\) By using ordinary polynomial evaluation methods, you can compute \(M^+\) with \(n -1\) matrix multiplications:

For example, if \(n = 3\text{,}\) \(M^+ = M(I + M(I + M))\text{.}\)

We can make use of the fact that if \(T\) is a relation matrix, \(T + T = T\) due to the fact that \(1 + 1 = 1\) in Boolean arithmetic. Let \(S_k = M + M^2 + \cdots + M^k\text{.}\) Then

Similarly,

and by induction we can prove

Notice how each matrix multiplication doubles the number of terms that have been added to the sum that you currently have computed. In algorithmic form, we can compute \(M^+\) as follows.

1.0. S = M
2.0  T= S*(I+S)
3.0 While T != S
		3.1 S = T
		3.2 T= S*(I+S) // using Boolean arithmetic
4.0 Return T

A second algorithm, Warshall's Algorithm, reduces computation time to the time that it takes to multiply two square matrices with the same order as the relation matrix in question.

1.0 W = M
2.0 for k = 1 to n:
     for i = 1 to n:
      for j = 1 to n:
        W[i,j]= W[i,j] + W[i,k] * W[k,j]
3.0 Return W