Q30E On page 102, we defined the bina... [FREE SOLUTION]

91影视

Algorithms

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani

Computer Science

1st Edition 路 333 pages

ISBN: 9780073523408

Chapter 3: Q30E (page 112)

On page 102, we defined the binary relation 鈥渃onnected鈥� on the set of vertices of a directedgraph. Show that this is an equivalence relation(see Exercise 3.29), and conclude that it partitions the vertices into disjoint strongly connected components.

Short Answer

Expert verified

It can be shown that the binary relation 鈥渃onnected鈥� on the set of vertices of a directed graph is an equivalence relation and yes, it partitions the vertices into disjoint strongly connected components.

Step by step solution

Explain the Equivalence relation

A relation is said to be in equivalence only if the relation satisfies reflexive, symmetry, and transitive properties.

Show that the given relation is the equivalence relation

Consider a set $S$ that has the partitions of an undirected graph. Consider any two vertices $x$ and $y$ in the undirected graph.

From the solution of Exercise 3.29, the binary connected relation of the connected relationship satisfies reflexivity, symmetry, and transitivity. So, it is an equivalence relation.

The strongly connected component is the equivalence class corresponding to this relation.

Thus, it partitions the vertices into disjoint strongly connected components.

Therefore, It is shown that the binary relation 鈥渃onnected鈥� on the set of vertices of a directed graph is an equivalence relation and yes, it partitions the vertices into disjoint strongly connected components.