Solution to Let A= {1,2,3,4,5,6} and R be a relation on A, such that R = [(x, … - Sikademy
Author Image

Archangel Macsika

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

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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^* :



Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3601-qpid-2300