Answer to Question #307874 in Discrete Mathematics for Anil

Question

Q.2- 1) For the given relation R = {(1,1), (1,2), (2,3), (3,1), (3,2)} defined on set A = {1,2,3}, find its transitive closure, R* using Warshall’s algorithm *

Answer 1

R->$M=\begin{matrix} 1 & 0&1 \\ 1 & 0&1\\ 0&1&0 \end{matrix}$

We are only interested in the zeros of the matrix, since only they can change (which means that we have found the path from one vertex to another)

$\begin{matrix} a & b &a\&b\\ 0 & 0&0\\ 0 & 1&0\\ 1 & 0&0\\ 1 & 1&1 \end{matrix}$

1$\in A$

M1[1,2]=M[1,1]&M[1,2]=0

M1[2,2]=M[2,1]&M[1,2]=0

M1[3,1]=M[3,1]&M[1,1]=0

M1[3,3]=M[3,1]&M[1,3]=0

M1=M

2$\in A$

M2[1,2]=M1[1,2]&M1[2,2]=0

M2[2,2]=M1[2,2]&M1[2,2]=0

M2[3,1]=M1[3,2]&M1[2,1]=1

M2[3,3]=M1[3,2]&M1[2,3]=1

$M2=\begin{matrix} 1 & 0&1 \\ 1 & 0&1\\ 1&1&1 \end{matrix}$

3$\in A$

M3[1,2]=M2[1,3]&M2[3,2]=1

M3[2,2]=M2[2,3]&M2[3,2]=1

$M3=\begin{matrix} 1 & 1&1 \\ 1 & 1&1\\ 1&1&1 \end{matrix}$

in the result

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