Syllabus concepts to know

• Tree and cycle algorithms with undirected graphs. (HL)
• Walks, trails, paths, circuits, cycles. (HL)
• Eulerian trails and circuits. (HL)
• Hamiltonian paths and cycles. (HL)
• Minimum spanning tree (MST) graph algorithms: Kruskal’s and Prim’s algorithms for finding minimum spanning trees. (HL)
• Chinese postman problem and algorithm for solution, to determine the shortest route around a weighted graph with up to four odd vertices, going along each edge at least once. (HL)
• Travelling salesman problem to determine the Hamiltonian cycle of least weight in a weighted complete graph. (HL)
• Nearest neighbour algorithm for determining an upper bound for the travelling salesman problem. (HL)
• Deleted vertex algorithm for determining a lower bound for the travelling salesman problem. (HL)