IB Maths AI HL 3.16 - Tree and Cycle Algorithms Notes

IB Maths AI HL 3.16 Notes – Tree and Cycle Algorithms

This IB Maths AI HL 3.16 resource introduces tree and cycle algorithms in graph theory, and is fully aligned with the IB Applications and Interpretation HL syllabus.

Students begin by reviewing essential graph language, including walks, trails, paths, circuits, and cycles. The notes clearly distinguish between repeated edges and repeated vertices, helping students understand the difference between Eulerian and Hamiltonian problems.

The resource then develops Eulerian ideas, including Eulerian trails and Eulerian circuits. Students learn how vertex degree determines whether a connected graph contains an Eulerian circuit or an Eulerian trail, and why Eulerian questions focus on edges rather than vertices.

Hamiltonian paths and cycles are introduced next, with a focus on visiting every vertex exactly once. The notes explain why a graph may be Hamiltonian without being Eulerian, or Eulerian without being Hamiltonian, giving students a strong conceptual foundation for later route problems.

Students then learn how to find minimum spanning trees using Kruskal’s Algorithm and Prim’s Algorithm. Structured practice guides students through selecting edges from a weighted graph or distance table, avoiding cycles, and finding the minimum total length needed to connect all vertices.

The notes also cover the Chinese Postman Problem, also known as route inspection. Students learn how to identify odd vertices, pair them efficiently, and calculate the shortest closed route that crosses every edge at least once.

The resource finishes with the Travelling Salesman Problem, including exact TSP search, nearest neighbor upper bounds, and deleted vertex lower bounds. Students practise interpreting distance tables, constructing routes, and finding a final range for the optimal TSP route.

Ideal for IB Maths AI HL teachers teaching graph theory, minimum spanning trees, Kruskal’s Algorithm, Prim’s Algorithm, route inspection, the Chinese Postman Problem, and the Travelling Salesman Problem.

This pairs great with our slidedeck!