Question

Find the Transitive closure by using Warshall’s Algorithm where A= {1, 2, 3,
4, 5, 6} and R= {(x,y)| (x-y)=2}

Answer 1

Here the 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 $A= \{1, 2, 3,4, 5, 6\}$ and $R= \{(x,y)\ |\ x-y=2\}$.

So $n=6$ and $R=\{(3,1),(4,2),(5,3),(6,4)\}$.

$W^{(0)}=M_R=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]$

$W^{(1)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]$

$W^{(2)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]$

$W^{(3)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]$

$W^{(4)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]$

$W^{(5)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]$

$M_{R^*}=W^{(6)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]$

$R^*=\{(3,1),(4,2),(5,1), (5,3),(6,2),(6,4)\}$.