Answer to Question #280692 in Discrete Mathematics for Priya

Question

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.

Answer 1

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)$\in$R* but (p,q)$\notin$R*, hence R* cannot be equivalence relation.