Question #117152
Find the transitive closure of the relation using Warshall’s algorithm R={(1,2),(2,1),(2,3),(3,4),(4,1)} on the set {1,2,3,4}.
1
Expert's answer
2020-06-10T18:56:05-0400

Let MR denotes the matrix representation of R. Take W0=MR, we have

W0=MR=(0100101000011000).W_0=M_R=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ \end{pmatrix}.

As MR is 4x4 matrix, we have n=4 and we need to compute W4.

For k=1. In column 1 of W0 '1' are at positions 2 and 4, hence p1=2, p2=4.

In row 1 of W0 1's is at position 2, hence q1=2.

Thus, we put 1 at positions (p1, q1)=(2, 2) and (p2, q1)=(4, 2).

W1=(0100111000011100).W_1=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ \end{pmatrix}.

For k=2. In column 2 of W1 1's are at positions 1, 2 and 4, hence p1=1, p2=2, p3=4.

In row 2 of W1 1's are at positions 1, 2, 3, hence q1=1, q2=2, q3=3,.

Thus, we put 1 at positions (p1, q1)=(1, 1), (p1, q2)=(1, 2), (p1, q3)=(1, 3),

(p2, q1)=(2, 1), (p2, q2)=(2, 2), (p2, q3)=(2, 3), (p3, q1)=(4, 1), (p3, q2)=(4, 2), (p3, q3)=(4, 3).

W2=(1110111000011110).W_2=\begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ \end{pmatrix}.

For k=3. In column 3 of W2 '1' are at positions 1, 2 and 4, hence p1=1, p2=2, p3=4.

In row 3 of W2 1's is at position 4, hence q1=4.

Thus, we put 1 at positions (p1, q1)=(1, 4), (p2, q1)=(2, 4), (p3, q1)=(4, 4).

W3=(1111111100011111).W_3=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix}.

For k=4. In column 4 of W3 '1' are at positions 1, 2, 3 and 4, hence p1=1, p2=2, p3=3, p4=4.

In row 4 of W3 1's are at positions 1, 2, 3 and 4, hence q1=1, q2=2, q3=3, q4=4.

Thus, we put 1 at positions (p1, q1)=(1, 1), (p1, q2)=(1, 2), (p1, q3)=(1, 3), (p1, q4)=(1, 4),

(p2, q1)=(2, 1), (p2, q2)=(2, 2), (p2, q3)=(2, 3), (p2, q4)=(2, 4),

(p3, q1)=(3, 1), (p3, q2)=(3, 2), (p3, q3)=(3, 3), (p3, q4)=(3, 4),

(p4, q1)=(4, 1), (p4, q2)=(4, 2), (p4, q3)=(4, 3), (p4, q4)=(4, 4).

MR=W4=(1111111111111111).M_R^{\infty}=W_4= \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ \end{pmatrix}.

All positions in W4 are 1, thus, the transitive closure of R is given as

R={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}.R^{\infty}=\{(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3) ,(2,4),\\ (3,1), (3,2), (3,3), (3,4), (4,1),(4,2),(4,3),(4,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!
LATEST TUTORIALS
APPROVED BY CLIENTS