Answer to Question #234233 in Discrete Mathematics for anson

Question

Find the transitive closure A={1,2,3,4,5}

R={ (2,3),(3,5),((1,2),(2,5),(1,3),(4,5),(5,2)} by using Warshall’s Algorithm.

Answer 1

M(R)=$\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$ matrix of relation R

Step 1: k=1

previous: $\begin{pmatrix} \bar 0 & \bar 1 & \bar 1 & \bar0 & \bar0 \\ \bar 0 & 0 & 1 & 0 & 1 \\ \bar0 & 0 & 0 & 0 & 1 \\ \bar0 & 0 & 0 & 0 & 1 \\ \bar0 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$ next : $\begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ \end{pmatrix}$

Matrix unchanged

Step 2: k=2

previous:$\begin{pmatrix} 0 & \bar1 & 1 & 0 &> 0 \\ \bar0 &\bar 0 & \bar1 & \bar0 & \bar1 \\ 0 & \bar0 & 0 & 0 & 1 \\ 0 & \bar0 & 0 & 0 & 1 \\ 0 & \bar1 & >0 & 0& >0 \\ \end{pmatrix}$ next: $\begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0& 1 \\ \end{pmatrix}$

Thee edges have added.

Step 3: k=3

previous:$\begin{pmatrix} 0 & 1 & \bar 1 & 0 & 1 \\ 0 & 0 & \bar 1 & 0 & 1 \\ \bar0 & \bar 0 & \bar0 & \bar0 & \bar 1\\ 0 & 0 & \bar0 & 0 & 1 \\ 0 & 1 & \bar1 & 0& 1 \\ \end{pmatrix}$ next: $\begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0& 1 \\ \end{pmatrix}$

Matrix is unchanged

Step 4: k=4 Matrix will not change because fourth column is zeros.

Step 5: k=5

$previous:\begin{pmatrix} 0 & 1 & 1 & 0 & \bar1 \\ 0 & >0 & 1 & 0 & \bar1 \\ 0 & > 0 & >0 & 0 & \bar1\\ 0 & >0 &> 0 & 0 & \bar1 \\ \bar0 & \bar1 & \bar1 &\bar 0& \bar1 \\ \end{pmatrix}$

final: $\begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 0 & 1& 1 & 0 & 1 \\ 0 & 1 & 1& 0 & 1\\ 0 & 1 &1 & 0 & 1 \\ 0 & 1 & 1 & 0& 1 \\ \end{pmatrix}$ - matrix of transitive closure

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