Answer to Question #146577 in Discrete Mathematics for Brij Raj Singh

Question #146577
Find the Transitive closure by using Warshall’s Algorithm where A= {1, 2, 3,
4, 5, 6} and R= {(x,y)| (x-y)=2}
1
Expert's answer
2020-11-25T15:57:30-0500

Here the steps of Warshall’s Algorithm:


Step 1: Execute W:=MR,k:=0W:=M_R, k:=0


Step 2: Execute k:=k+1k:=k+1


Step 3: For all iki\ne k such that wik=1w_{ik}=1, and for all jj execute the operation wij:=wijwkjw_{ij}:=w_{ij}\lor w_{kj}


Step 4: If k=nk=n, then stop: the solution is W=MRW=M_{R^*}, else go to step 2.


In our case A={1,2,3,4,5,6}A= \{1, 2, 3,4, 5, 6\} and R={(x,y)  xy=2}R= \{(x,y)\ |\ x-y=2\}.


So n=6n=6 and R={(3,1),(4,2),(5,3),(6,4)}R=\{(3,1),(4,2),(5,3),(6,4)\}.



W(0)=MR=[000000000000100000010000001000000100]W^{(0)}=M_R=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]


W(1)=[000000000000100000010000001000000100]W^{(1)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]


W(2)=[000000000000100000010000001000000100]W^{(2)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]


W(3)=[000000000000100000010000101000000100]W^{(3)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]


W(4)=[000000000000100000010000101000010100]W^{(4)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]


W(5)=[000000000000100000010000101000010100]W^{(5)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]


MR=W(6)=[000000000000100000010000101000010100]M_{R^*}=W^{(6)}=\left[\begin{array}{cccccc} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 1 & 0 & 0 \end{array}\right]


R={(3,1),(4,2),(5,1),(5,3),(6,2),(6,4)}R^*=\{(3,1),(4,2),(5,1), (5,3),(6,2),(6,4)\}.





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