Reachability in a directed graph

Task number: 3380

Consider a directed graph $G$ and a relation $R$ on its vertices defined such that $uRv$ if and only if $v$ can be reached from $u$ by a directed path.

Variant
Show that $R$ is a preorder (a relation that is reflexive and transitive, but not necessarily antisymmetric).
Solution
The zero-length paths correspond to the reflexive pairs $uRu$ .

The concatenation of oriented paths from $u$ to $v$ and from $v$ to $w$ is an oriented walk from $u$ to $w$ . By omitting the segments between two occurrences of the same vertex, an oriented path from $u$ to $w$ can be obtained. The relation $R$ is therefore transitive.
Variant
Define the symmetric kernel of the relation as $R_s=R\cap R^{-1}$ . Prove that $R_s$ is an equivalence relation.
Solution
Both $R$ and $R^{-1}$ are reflexive, so $R_s$ is also reflexive.
For transitivity, if $uR_sv$ and $vR_sw$ , then $uRv \land vRw\land uR^{-1}v\land vR^{-1}v$ and hence the transitivity of $R$ and $R^{-1}$ implies $uRw$ and $uR^{-1}w$ , thus $uR_sw$ and therefore $R_s$ is transitive.

When $uR_sv$ , then $uRv \land uR^{-1}v$ which corresponds to $vR^{-1}v\land vRu$ , so $vR_su$ , and hence $R_s$ is symmetric.
Variant
What is the meaning of the equivalence classes of $R_s$ ?
Solution
Equivalence classes have the meaning of strongly connected components, or they contain vertices such that oriented paths lead between them in both directions.
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$ .
Solution
If $a,a'\in A$ and $b'\in B$ , and also $AR_fB$ because $aRb$ , then concatenating the path from $a'$ to $a$ with the path from $a$ to $b$ , and omitting the segments between the repeating vertices, we get a path from $a'$ to $b$ . In other words, the relation $R_f$ does not depend on the selection of an element from the equivalence class $a$ .

An analogous argument can be made for the choice of an element from $B$ .
Variant
Prove that the relation $R_f$ is a (partial) order.
Solution
Reflexivity: equivalence classes are non-empty, so for $A$ there exists $a$ and a zero-length path from $a$ to $a$ which yields $AR_fA$ .

Transitivity: if $AR_fB \land BR_fC$ , then there exist $a \in A, b \in B$ and $c \in C$ such that $aRb \land bRc \Rightarrow aRc \Rightarrow AR_fC$ .

Antisymmetry: if $AR_fB\land BR_fA$ , then there exist $a\in A$ and $b\in B$ such that $aRb \land bRa \Rightarrow b\in A \Rightarrow A=B$ .
Variant
How can be desribed graphs, for which $R_s$ is the trivial equivalence relation? (Each vertex is equivalent only to itself.)
Solution
These graphs do not contain any directed cycle of length at least 2, since the vertices on the cycle would belong to a non-trivial equivalence class.
Variant
How can be desribed graphs, for which the ordering $R_f$ is linear?
Solution
These are graphs where there is an oriented path between every pair of vertices in at least one direction. If the ordering was not linear, then for vertices $a$ and $b$ , where classes $A$ and $B$ are incomparable in $R_f$ , no such path can exist.