Semi-reachability in a graph
Task number: 4511
For an oriented graph, let us define a relation \(R\) on the vertex set such that \(uRv\) just if there exists a path from \(u\) to \(v\) or from \(v\) to \(u\). Verify whether this relation is reflexive, symmetric, transitive.
Solution
The relation is reflexive because there is always a zero-length path from a vertex to the same vertex.
The symmetry of the relation follows directly from the definition.
A relation is not transitive. Consider a graph with vertices 1, 2, 3 and edges \((1{,}2)\) and \((3{,}2)\). There is a path between 1 and 2, and between 2 and 3, but there is no path in either direction.
