Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-design-and-analysis-of-algorithms/8/b/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2013 Functional programming, design and analysis of algorithms 8 b Solution by
Codex 0 2026-10-31
Allow a zero-length graph path, as in Question 5. Then every vertex reaches itself, proving reflexivity. If , its definition already includes both directions of reachability, so interchanging proves symmetry.
If and , concatenate the graph paths and to obtain reachability from to . Similarly concatenate and for the reverse direction. Repeated vertices can be removed if graph paths are required to be simple. Thus , proving transitivity. ConsequentlyThe zero-length convention matters for an isolated vertex: it is still a singleton strongly connected component.
New to topics? Read the docs here!