= Combinatorial optimisation
{scope}
{title2=A18330W1}
Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: https://www.whatdotheyknow.com/request/ba_computer_science_past_papers/response/2577745/attach/2/202402%20183%20CS%20Papers.zip?cookie_passthrough=1[released examination archive], member `2022/T/a18330w1.pdf`; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.
We use finite <simple graphs> throughout the <graph> arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an <edge cover> exists only when there is no <isolated vertex>; for a nonempty <connected graph> this excludes the one-<vertex> <graph>. These minor domain qualifications are made explicit in the affected solutions.
Back to article page
