Solution to Let R = {(1,4), (2,1), (2,5),(2,4),(4,3),(5,3),(3,2)} on the set A = {1, 2, 3, 4, … - Sikademy
Author Image

Archangel Macsika

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

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

Let A=\{1,2,3,4,5\} and R be the relation on A such that R= \{(1,4),(2,1),(2,5),(2,4),(4,3),(5,3),(3,2)\}. 


Warshall's Algorithm:


Step 1: put W:=M_R,\ k:=0.


Step 2: put k:=k+1.


Step 3: for all i\ne k such that w_{ik}=1, and for all j put w_{ij}:=w_{ij}\lor w_{kj}.


Step 4: if k=n then STOP else go to the step 2.


Let us find the transitive closure of R by Warshall's Algorithm:


W^{(0)}=M_R=\begin{pmatrix} 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}



W^{(1)}=\begin{pmatrix} 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}


W^{(2)}=\begin{pmatrix} 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 \end{pmatrix}


W^{(3)}=\begin{pmatrix} 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 \end{pmatrix}


W^{(4)}=\begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 \end{pmatrix}


M_{R^*}=W^{(5)}=\begin{pmatrix} 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 \end{pmatrix}


It follows that the transitive closure R^* of R is the following:


R^*=A\times A.

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-1234-qpid-972