Answer to Question #280270 in Discrete Mathematics for Ashwini

Question

Consider a relation R=\ (1,1),(1, ), (0,2), (2,3) (3,1)) on the set A=\ 1,2,3\ Find transitive closure of the relation R using algorithm Warshall's

Answer 1

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

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

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

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

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

$W^{(3)} =\begin{pmatrix} 0 & 0 & 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.$