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

Archangel Macsika

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

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,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)\}


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-3602-qpid-2301