Answer to Question #141743 in Discrete Mathematics for Asdf

Question

Let A= {1,2,3,4,5,} and R be a relation on A, such that
R = [(1,4), (2,2), (3,4), (3,5), (4,1), (5,2), (5,5)]. Use warshall’s Algorithm to find the matrix of transitive closure of R

Answer 1

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

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 all $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|=5.$

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

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

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

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

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

Thus, the matrix of transitive closure of $R$ is the following:

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

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

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