## Reachability in a directed graph

### Task number: 3380

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?