Collection of Maths Problems

Reachability in a directed graph

Task number: 3380

• 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.