Mumbai University > Computer Engineering > Sem 3 > Discrete Structures

Marks: 6 Marks

Year: May 2014

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

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

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

For k=1. In column 1 of $W_0$ ‘1’ at position 2. Hence $p_1 =2$

In row 1 of $W_0$, ‘1’ is at position 2. Hence $q_1 =2$. Therefore, to obtain W¬1 , we put ‘1’ at the position: {$(p_1,q_1)=(2,2)$}. Thus

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

For k=2. In column of $W_1$ , 1’s are at positions 1, 2. Hence $p_1=1,p_2=2$.

In row 2 of $w_1$ 1’s are at positions 1, 2 and 3. Hence $q_1=1,q_2=2,q_3=3$

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

$\{(p1 , q_1),(p_1,q_2 ),(p_1,q_3 ),(p_2,q_1 ),(p_2,q_2 )(p_2,q_3 )=(1,1)(1,2),(1,3),(2,1),(2,2),(2,3)\}$