## Reachability in a directed graph

Consider a directed graph $$G$$ and a relation $$R$$ on its vertices defined such that $$xRy$$ exactly when there is some directed path from $$x$$ to $$y$$.

• #### Variant

Show that $$R$$ is a preorder (a relation that is reflexive and transitive, but not necessarily antisymmetric).

• #### Variant

Define the symmetric kernel of the relation as $$R_s=R\cap R^{-1}$$. Prove that $$R_s$$ is an equivalence relation.

• #### Variant

What is the meaning of the equivalence classes of $$R_s$$?

• #### Variant

Let us define the relation $$R_f$$ as $$R$$ factored by $$R_s$$. In other words, $$R_f$$ will be a relation on the equivalence classes of the relation $$R_s$$ defined such that $$A R_f B$$ exactly when for $$a\in A$$ and $$b\in B$$ it is true that $$a R b$$. Prove that this definition is correct, i.e. it does not depend on the choice of the elements $$a$$ and $$b$$.

• #### Variant

Prove that the relation $$R_f$$ is a (partial) order.

• #### Variant

How do graphs appear for which $$R_s$$ is the trivial equivalence relation? (Each vertex is equivalent only to itself.)

• #### Variant

How do graphs appear for which the ordering $$R_f$$ is linear?