Question

Let R be the relation on the set A = {a, b, c, d, e, f} and
R = {(a,c), (b,d), (c,a), (c,e), (d,b), (d,f), (e,c), (f,d)}
Find the transitive closure pf R using Warshall’s algorithm.

Answer 1

$R = \{(a,c), (b,d), (c,a), (c,e), (d,b), (d,f), (e,c), (f,d)\}$

Here are the steps of the Warshall’s algorithm:

Step 1. Assign initial values $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 $j$ execute the operation $w_{ij}=w_{ij}\lor w_{kj}.$

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

$n=|A|=6.$

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

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

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

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

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

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

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

Therefore, the transitive closure of $R$ is the following:

$R^* = \{(a,a),(a,c),(a,e), (b,b),(b,d),(b,f), (c,a),(c,c), (c,e), (d,b),(d,d),$

$(d,f),(e,a), (e,c),(e,e),(f,b), (f,d),(f,f) \}$