Applied Discrete Structures

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{.}\)

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

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

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

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

For example, if \(n = 3\text{,}\) \(R^+ = R(I + R(I + R))\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 = R + R^2 + \cdots + R^k\text{.}\) Then

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 \(R^+\) as follows.

1.0. S = R
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 T = R
2.0 for k = 1 to n:
     for i = 1 to n:
      for j = 1 to n:
        T[i,j]= T[i,j] + T[i,k] * T[k,j]
3.0 Return T