Let us state the steps of the Warshall's algorithm:
Step 1. Let W:=MR, k:=0.
Step 2. Put k:=k+1.
Step 3. For all i=k such that wik=1 and for all j let wij=wij∨wkj.
Step 4. If k=n then STOP: W=MR∗, else go to Step 2.
Consider a relation R={(1,1),(1,0),(0,2),(2,3),(3,1)} on the set A={0,1,2,3}.
Let us find transitive closure of the relation R using Warshall's algorithm:
W(0)=MR=⎝⎛0100010110000010⎠⎞
W(1)=⎝⎛0100010111000010⎠⎞
W(2)=⎝⎛0101010111010010⎠⎞
W(3)=⎝⎛0101010111011111⎠⎞
MR∗=W(4)=⎝⎛1111111111111111⎠⎞
It follows that R∗=A×A is a universal relation on the set A.
Comments
Leave a comment