Answer to Question #280882 in Discrete Mathematics for Ashwini

Question

Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,123 on the set A = {1,2,37 Find transitive using warshalls algorithm... closure of the relation R consider

Answer 1

the transitive closure of a binary relation R on a set X is the smallest relation on X that contains R and is transitive

 steps of Warshall’s Algorithm:

Step 1: Execute $W:=M_R, k:=0$

Step 2: Execute $k:=k+1$

Step 3: For all $i\ne k$ such that $w_{ik}=1$, and for all $j$ execute the operation $w_{ij}:=w_{ij}\lor w_{kj}$

Step 4: If $k=n$, then stop: the solution is $W=M_{R^*}$, else go to step 2.

in our case:

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

k = 1:

$w_{31}=1$

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

k =3:

$w_{13}=1$

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

$w_{23}=1$

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

transitive closure:

$R^*=\{(1, 1) (1, 3), (2, 2), (2,3), (3,1),(2,1),(3,3)\}$