Mathematics: Applications and Interpretation · Topic 3: Geometry and trigonometry

AHL3.16 — Tree, cycle and route algorithms

Mathematics: Applications and Interpretation · SL / HL · syllabus-mapped notes

1. AIAHL3.16.1

   Walks, trails, paths and cycles

   Name the ways of moving through a graph, and Eulerian and Hamiltonian routes.

2. AIAHL3.16.2

   Minimum spanning trees: Kruskal and Prim

   Connect all vertices at least total cost with no cycle.

3. AIAHL3.16.3

   The Chinese postman problem

   Find the shortest closed route using every edge at least once.

4. AIAHL3.16.4

   The travelling salesman problem

   Find a least-weight cycle visiting every vertex, with bounds.