Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 8 Marks

Year: Dec 2014

Let $M_R$ denotes the matrix representation of R. Take $W_0=M_R,$ We have

$W_0=M_R=\begin{pmatrix}1&0&0&1 \\ 0&1&1&0 \\ 0&1&1&0 \\ 1&0&0&1 \end{pmatrix}$ and $n=4$ (As $M_R$ is a $4 \times 4$ matrix)

We compute $W_4$ by using warshall's algorithm.

For k=1. In column 1 of $W_0$, ‘1’ is at position 1, 4. Hence $p_1=1, p_2=4$.

In row 1 of $W_0$ ‘1’ is at position 1, 4. Hence $q_1=1, q_2=4$.

Therefore, to obtain $W_1$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(1, 1), (1, 4), (4, 1), (4 4)\}$. Thus,

$W_1=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

For k=2. In column 2 of $W_1$, ‘1’ is at position 2, 3. Hence $p_1=2, p_2=3$.

In row 2 of $W_1$ ‘1’ is at position 2, 3. Hence $q_1=2, q_2=3$.

Therefore, to obtain $W_2$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(2, 2), (2, 3), (3, 2), (3, 3)\}$. Thus,

$W_2=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

For k=3. In column 3 of $W_2$, ‘1’ is at position 2, 3. Hence $p_1=2, p_2=3$.

In row 3 of $W_2$ ‘1’ is at position 2, 3. Hence $q_1=2, q_2=3$.

Therefore, to obtain $W_3$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(2, 2), (2, 3), (3, 2), (3, 3)\}$. Thus,

$W_3=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1\end{bmatrix}$

For k=4. In column 4 of $W_3$, ‘1’ is at position 1, 4. Hence $p_1=1, p_2=4$.

In row 4 of $W_3$ ‘1’ is at position 1, 4. Hence $q_1=1, q_2=4$.

Therefore, to obtain $W_3$, we put ‘1’ at the position:

$\{(p_1, q_1), (p_1, q_2), (p_2, q_1), (p_2, q_2)=(1, 1), (1, 4), (4, 1), (4 4)\}$. Thus,

$W_4=\begin{bmatrix}1&0&0&1 \\ 0&0&1&1 \\ 1&0&1&1 \\ 0&0&0&1 \end{bmatrix}$

Thus, the transitive clousure of R is given as

R= {(1, 1), (1, 4), (2, 2), (2, 3), (3, 2), (3, 3), (4, 1), (4, 4)}