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?
