Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/discrete-mathematics-continuous-mathematics-and-probability/3/e/ii/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Discrete mathematics, continuous mathematics and probability 3 e ii Solution by
Codex 0 2026-10-31
No. On take . This is an antisymmetric relation because it contains no opposite pair of distinct elements. Its reflexive transitive closure contains every ordered pair: following the directed three-cycle reaches any vertex from any other. In particular it contains both and , violating antisymmetry.
This illustrates the reachability preorder: collapsing mutually reachable vertices into strongly connected components yields a partial order, but retaining all original vertices need not.
New to topics? Read the docs here!