AHL 3.16 (HL)—Graph algorithms

A graph algorithm is a rule for extracting a route, assignment or bound from network data. A heuristic such as nearest neighbour chooses a locally short next edge; it is fast but not generally optimal.

Record the starting vertex and tie rule, then compare the resulting tour with a lower or upper bound when evaluating quality. Deleted-vertex or spanning-tree reasoning can provide a bound without proving the exact optimum.

A nearest-neighbour tour can choose the closest next city and later be forced into one very long final edge. A different early choice may produce a shorter total route, so the first route is a candidate, not a proof.

Greedy does not mean optimal. State the algorithm, its assumptions and whether the conclusion is a route, a bound or a proven minimum.

Algorithm map: an Eulerian trail uses every edge once (exactly two odd vertices) and an Eulerian circuit has all vertices even; Hamiltonian paths or cycles visit every vertex once. Kruskal selects globally smallest non-cycling edges, while Prim grows a minimum spanning tree from a chosen vertex. For a Chinese postman route, pair up to four odd vertices using least-distance paths, duplicate the minimum-total pairing, then take an Eulerian circuit. For a complete weighted travelling-salesman graph, nearest neighbour gives an upper bound and deleted-vertex plus MST reasoning gives a lower bound; complete a least-distance table first when the practical graph is not complete. State and justify the selected algorithm.