Question

Let R={(1,2),(2,1),(2,3),(3,4),(4,1) } be a relation on the A={1,2,3,4}. Find the transitive closure of R using Warshall’s algorithm.

Answer 1

Consider a relation $R=\{ (1,2),(2,1),(2,3),(3,4),(4,1)\}$ on the set $A=\{1,2,3,4\}$.

Let us state the steps of the Warshall's algorithm:

Step 1. Let $W:=M_R,\ k:=0.$

Step 2. Put $k:=k+1.$

Step 3. For all $i\ne k$ such that $w_{ik}=1$ and for all $j$ let $w_{ij}=w_{ij}\lor w_{kj}.$

Step 4. If $k=n$ then STOP: $W=M_{R^*},$ else go to Step 2.

Let us find transitive closure of the relation $R$ using Warshall's algorithm:

$W^{(0)}=M_R =\begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0 \end{pmatrix}$

$W^{(1)} =\begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 0 & 0 \end{pmatrix}$

$W^{(2)} =\begin{pmatrix} 1 & 1 & 1 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}$

$W^{(3)} =\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 \end{pmatrix}$

$M_{R^*}=W^{(4)} =\begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \end{pmatrix}$

It follows that $R^*=A\times A$ is a universal relation on the set $A.$