• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q33E

Expert-verified
Found in: Page 607

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Adapt Algorithm 1 to find the reflexive closure of the transitive closure of a relation on a set with $$n$$ elements.

procedure reflexive closure of transitive closure ( $${M_R}:$$ zero-one $$n*n$$ matrix)

We first determine the transitive closure, which is thus identical to the Warshall algorithm.

$$A: = {M_R}$$

$$B = A$$

fori: $$= 2$$ to $$n$$

$$A: = A \supseteq {M_R}$$

$$B: = B \vee A$$

forj: $$= 1$$ to $$n$$

$${W_{ij}}: = 1$$

return

See the step by step solution

## Step 1: Given data

Reflexive closure of the transitive closure of a relation on a set with $$n$$ elements. The shortest path between two vertices in a directed graph.

## Step 2: Concept used of algorithm

Algorithms are used as specifications for performing calculations and data processing.

## Step 3: Find the reflexive closures

There are two ways to go.

One approach is to take the output of Algorithm as it stands and then make sure that all the pairs (a, a) are included by forming the join with the identity matrix

$$\left( {} \right.$$specifically $$\left. {{\mathop{\rm set}\nolimits} {\bf{B}}: = {\bf{B}} \vee {{\bf{I}}_n}} \right)$$.

The other approach is to insure the reflexivity at the beginning by initializing $${\bf{A}}: = {M_r} \vee {{\bf{I}}_n}$$; if we do this, then only paths of length strictly less than $$n$$ need to be looked at, so we can change the $$n$$ in the loop to $$n - 1$$.