Solution to Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,1)on the set A … - Sikademy
Author Image

Archangel Macsika

Consider a relation R= {(1, 1) (1, 3), (2, 2), (2,3) (3,1)on the set A = (1,2,3) Find transitive using warshalls algorithm... closure of the relation R consider

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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


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


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

2. Put k:=k+1.

3. For all i\ne k such that w_{ik}=1 and for all j let w_{ij}=w_{ij}\lor w_{kj}.

4. If k=n then stop and W=M_{R^*}, else go to step 2.


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


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


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


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


M_{R^*}=W^{(3)} =\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix}


It follows that R^*=\{ (1,1),(1, 3), (2,1),(2,2), (2,3), (3,1),(3,3)\}.Consider a relation 

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


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


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

2. Put k:=k+1.

3. For all i\ne k such that w_{ik}=1 and for all j let w_{ij}=w_{ij}\lor w_{kj}.

4. If k=n then stop and W=M_{R^*}, else go to step 2.


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


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


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


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


M_{R^*}=W^{(3)} =\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1\\ 1 & 0 & 1 \end{pmatrix}


It follows that R^*=\{ (1,1),(1, 3), (2,1),(2,2), (2,3), (3,1),(3,3)\}.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-509-qpid-395