Question

Use Warshall’s algorithm to find the transitive closure of the relation R = {(1,1),(1,4), (2,5),(2,3),(3,1),(3,5),(3,4),(4,2)} on the set A = {1,2,3,4,5}.

Answer 1

$A=\\\{1,2,3,4,5\}\\ R=\{(1,1),(1,4), (2,5),(2,3),(3,1),(3,5),\\ (3,4),(4,2)\}$

$w_{ij}^{(k)}=\left\{\begin{matrix} w_{ik}^{(k-1)}\lor w_{kj}^{(k-1)}, \quad if \quad w_{kj}^{(k-1)}=1\\ w_{ij}^{(k-1)}, \quad if \quad w_{ik}^{(k-1)}=0 \end{matrix}\right\}$

$W_0=\begin{matrix} &1_{-}&2_{-}&3_{-}&4_{-}&5_{-} \\ 1_{-} & 1&0&0&1&0\\ 2_{-}&0&0&1&0&1\\ 3_{-}&1&0&0&1&1\\ 4_{-}&0&1&0&0&0\\ 5_{-}&0&0&0&0&0 \end{matrix}$

Find $W_1$

$W_1=\begin{matrix} &1_{-}&2_{-}&3_{-}&4_{-}&5_{-} \\ 1_{-} & 1&0&0&1&0\\ 2_{-}&0&0&1&0&1\\ 3_{-}&1&0&0&1&1\\ 4_{-}&0&1&0&0&0\\ 5_{-}&0&0&0&0&0 \end{matrix}$

$W_2=\begin{matrix} &1_{-}&2_{-}&3_{-}&4_{-}&5_{-} \\ 1_{-} & 1&0&0&1&0\\ 2_{-}&0&0&1&0&1\\ 3_{-}&1&0&0&1&1\\ 4_{-}&0&1&1&0&1\\ 5_{-}&0&0&0&0&0 \end{matrix}$

$W_3=\begin{matrix} &1_{-}&2_{-}&3_{-}&4_{-}&5_{-} \\ 1_{-} & 1&0&0&1&0\\ 2_{-}&1&0&1&1&1\\ 3_{-}&1&0&0&1&1\\ 4_{-}&1&1&1&1&1\\ 5_{-}&0&0&0&0&0 \end{matrix}$

$W_4=\begin{matrix} &1_{-}&2_{-}&3_{-}&4_{-}&5_{-} \\ 1_{-} & 1&1&1&1&1\\ 2_{-}&1&1&1&1&1\\ 3_{-}&1&1&1&1&1\\ 4_{-}&1&1&1&1&1\\ 5_{-}&0&0&0&0&0 \end{matrix}$

$W_4=W_5$