R = \{(1,3), (2,4), (3,1), (3,5), (4,2), (4,6), (5,3),(6,4)\} R = {( 1 , 3 ) , ( 2 , 4 ) , ( 3 , 1 ) , ( 3 , 5 ) , ( 4 , 2 ) , ( 4 , 6 ) , ( 5 , 3 ) , ( 6 , 4 )}
Let us draw digraph of R: R :
Here are the steps of the Warshall’s algorithm:
Step 1. Assign initial values W=M_R, k=0 W = M R , k = 0 .
Step 2. Execute k:=k+1. k := k + 1.
Step 3. For all i\ne k i = k such that w_{ik}=1 w ik = 1 , and for all j j execute the operation w_{ij}=w_{ij}\lor w_{kj}. w ij = w ij ∨ w kj .
Step 4. If k=n k = n , then stop: we have the solution W=M_{R^*} W = M R ∗ , else go to the step 2.
n=|A|=6. n = ∣ A ∣ = 6.
W^{(0)}=M_R=\left(\begin{array} {cccccc} 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0\end{array}\right) W ( 0 ) = M R = ⎝ ⎛ 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 ⎠ ⎞
W^{(1)}=\left(\begin{array} {cccccc} 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0\end{array}\right) W ( 1 ) = ⎝ ⎛ 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 ⎠ ⎞
W^{(2)}=\left(\begin{array} {cccccc} 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0\end{array}\right) W ( 2 ) = ⎝ ⎛ 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 ⎠ ⎞
W^{(3)}=\left(\begin{array} {cccccc} 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0\end{array}\right) W ( 3 ) = ⎝ ⎛ 1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1 0 0 ⎠ ⎞
W^{(4)}=\left(\begin{array} {cccccc} 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1\end{array}\right) W ( 4 ) = ⎝ ⎛ 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ⎠ ⎞
W^{(5)}=\left(\begin{array} {cccccc} 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1\end{array}\right) W ( 5 ) = ⎝ ⎛ 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ⎠ ⎞
Thus, the matrix of transitive closure of R R is the following:
M_{R^*}=W^{(6)}=\left(\begin{array} {cccccc} 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1\end{array}\right) M R ∗ = W ( 6 ) = ⎝ ⎛ 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 ⎠ ⎞
Therefore, the transitive closure of R R is the following:
R^* = \{(1,1),(1,3),(1,5),(2,2), (2,4),(2,6), (3,1),(3,3), (3,5), (4,2),(4,4), (4,6), R ∗ = {( 1 , 1 ) , ( 1 , 3 ) , ( 1 , 5 ) , ( 2 , 2 ) , ( 2 , 4 ) , ( 2 , 6 ) , ( 3 , 1 ) , ( 3 , 3 ) , ( 3 , 5 ) , ( 4 , 2 ) , ( 4 , 4 ) , ( 4 , 6 ) ,
(5,1), (5,3),(5,5),(6,2),(6,4),(6,6)\} ( 5 , 1 ) , ( 5 , 3 ) , ( 5 , 5 ) , ( 6 , 2 ) , ( 6 , 4 ) , ( 6 , 6 )}
Let us draw digraph of R^* : R ∗ :