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/d/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 d Solution by
Codex 0 2026-10-31
Take two directed triangles meeting only at a central vertex . Make entirely black and entirely white. All five vertices lie in one strongly connected component, since every vertex can reach and can be reached from . It contains internal edges of both colours.
Two monochromatic directed triangles sharing one vertex give a mixed closed walk but no mixed simple cycle
. Details. A closed walk can traverse the black triangle and then the white triangle. But a simple cycle using edges from both triangles would have to pass through to change triangles and pass through again to return. It would repeat other than the single start/end identification, contradicting simplicity. Removing separates the two triangles, so no other transition between them is possible. ThereforeThis example avoids self-loops and works even when a directed simple cycle is required to have at least three vertices.
New to topics? Read the docs here!
