Answer to Question #280710 in Discrete Mathematics for Ashwini

Question #280710

Consider a relation R=\ (1,1),(1, ), (0,2), (2,3) (3,1)) on the set A=\ 1,2,3\ Find transitive closure of the relation R using algorithm Warshall's

1
Expert's answer
2021-12-21T18:31:50-0500

Let us state the steps of the Warshall's algorithm:


Step 1. Let W:=MR, k:=0.W:=M_R,\ k:=0.

Step 2. Put k:=k+1.k:=k+1.

Step 3. For all iki\ne k such that wik=1w_{ik}=1 and for all jj let wij=wijwkj.w_{ij}=w_{ij}\lor w_{kj}.

Step 4. If k=nk=n then STOP: W=MR,W=M_{R^*}, else go to Step 2.


Consider a relation R={(1,1),(1,0),(0,2),(2,3),(3,1)}R=\{ (1,1),(1, 0), (0,2), (2,3), (3,1)\} on the set A={0,1,2,3}A=\{0, 1,2,3\}.


Let us find transitive closure of the relation RR using Warshall's algorithm:


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



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


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


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


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


It follows that R=A×AR^*=A\times A is a universal relation on the set A.A.




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!

Leave a comment

LATEST TUTORIALS
New on Blog