Answer to Question #257399 in Discrete Mathematics for tushar

Question

Q1 Let R = {(1,4),(2,1),(2,5),(2,4),(4,3),(5,3),(3,2)}. Use warshall’s algorithm to find the matrix of transitive closure where A = {1, 2, 3, 4, 5}

Answer 1

Let $A=\{1,2,3,4,5\}$ and $R$ be the relation on $A$ such that $R= \{(1,4),(2,1),(2,5),(2,4),(4,3),(5,3),(3,2)\}.$ 

Warshall's Algorithm:

Step 1: put $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$ put $w_{ij}:=w_{ij}\lor w_{kj}.$

Step 4: if $k=n$ then STOP else go to the step 2.

Let us find the transitive closure of $R$ by Warshall's Algorithm:

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

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

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

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

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

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

It follows that the transitive closure $R^*$ of $R$ is the following:

$R^*=A\times A.$