Solution to For the relation R = {(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)} 1.Using warshall algorithm find the transitive … - Sikademy
Author Image

Archangel Macsika

For the relation R = {(p,p) ,(q,p),(q,q),(r,r),(r,s),(s,s) ,(s,m) ,(m,m)} 1.Using warshall algorithm find the transitive closure R* of R 2.write matrix representation of R* 3.Check whether the relation of R* is an equivalence relation or a partial order.

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

Solution:

1.

Warshall's algorithm is used to determine the transitive closure of a directed graph or all paths in a directed graph by using the adjacency matrix. For this, it generates a sequence of n matrices. Where, n is used to describe the number of vertices.

Let's apply this method.

Firstly, the matrix of R is given by:



Now R* will be found using the algorithm as follows:



Now, cross product of rows and columns will give:

R*={(m,m),(p,p),(q,q),(r,r),(s,s),(q,p),(q,r),(q,s),(r,m),(r,p),(r,q),(s,m),(s,q),(s,r)}

2.

Matrix of R* is given by:



3.

As (q,b)\inR* but (p,q)\notinR*, hence R* cannot be equivalence relation.

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-519-qpid-405