Answer to Question #141756 in Discrete Mathematics for Asdf

Question

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

Answer 1

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

Let us draw digraph of $R:$

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|=6.$

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

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

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

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

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

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

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

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

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

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

$(5,1), (5,3),(5,5),(6,2),(6,4),(6,6)\}$

Let us draw digraph of $R^* :$