Question #255706
Let A={1,2,3,4,5} and R be the relation on A such that R={(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)}. Find the transitive closure of R by Warshall's Algorithm
1
Expert's answer
2021-10-25T16:23:26-0400

Let A={1,2,3,4,5}A=\{1,2,3,4,5\} and RR be the relation on AA such that R={(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)}.R=\{(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)\}. Let us find the transitive closure of RR by Warshall's Algorithm:


W(0)=MR=(1001001000000111000001001)W^{(0)}=M_R=\begin{pmatrix} 1 & 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{pmatrix}



W(1)=(1001001000000111001001001)W^{(1)}=\begin{pmatrix} 1 & 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{pmatrix}


W(2)=(1001001000000111001001001)W^{(2)}=\begin{pmatrix} 1 & 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{pmatrix}


W(3)=(1001001000000111001001001)W^{(3)}=\begin{pmatrix} 1 & 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{pmatrix}


W(4)=(1001001000100111001001001)W^{(4)}=\begin{pmatrix} 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{pmatrix}


MR=W(5)=(1001001000110111001001001)M_{R^*}=W^{(5)}=\begin{pmatrix} 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{pmatrix}


It follows that the transitive closure RR^* of RR 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)}.R^*=\{(1,1),(1,4),(2,2),(3,1),(3,2),(3,4),(3,5),(4,1),(4,4),(5,2),(5,5)\}.



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS