Preview
IB DP Mathematics: Applications and Interpretation | SL & HL | Geometry and Trigonometry — Graph Algorithms | Topic 3.16
📋 Learning Intentions
- Identify whether a graph is Eulerian or semi-Eulerian and state the conditions required for each.
- Apply the Chinese Postman algorithm to find the minimum weight closed walk that traverses every edge of a weighted graph at least once.
- Apply the nearest-neighbour algorithm to find an upper bound for the Travelling Salesman Problem.
- Apply the deleted vertex algorithm to find a lower bound for the Travelling Salesman Problem.
- Interpret upper and lower bounds to determine how close a solution is to the optimal Hamiltonian cycle.
- Justify which algorithm is appropriate for a given routing or optimisation problem.
Real-World Introduction
A postal worker must deliver letters along every street in a neighbourhood and return to the sorting office. A refuse truck must collect bins from every road in a district. In both cases, the question is the same: what is the shortest possible route that covers every edge of the road network? This is the Chinese Postman Problem — named after the Chinese mathematician Mei-Ko Kwan who formalised it in 1962.
A different but related question arises for a sales representative who must visit a fixed set of cities and return home, travelling each road at most once. The goal is to minimise total distance. This is the Travelling Salesman Problem (TSP) — one of the most famous unsolved optimisation problems in mathematics. For large networks, no efficient exact algorithm is known, so IB students learn to find bounds that bracket the optimal solution.
🌍 Why This Matters Logistics companies such as UPS and FedEx use variants of these algorithms to plan delivery routes, saving millions of litres of fuel annually. Google Maps route optimisation, circuit board drilling paths, and DNA sequencing all reduce to graph traversal problems of this type.
Core Concepts & Definitions
Before applying either algorithm, it is essential to understand the structure of the graph being analysed. A weighted graph assigns a numerical value (distance, time, cost) to each edge. The degree of a vertex is the number of edges meeting at that vertex. These two ideas — edge weights and vertex degrees — drive both algorithms.
🔑 Key Definition — Eulerian and Semi-Eulerian Graphs
- A graph is Eulerian if it contains a closed trail (Eulerian circuit) that uses every edge exactly once. Condition: every vertex has even degree.
- A graph is semi-Eulerian if it contains an open trail (Eulerian path) that uses every edge exactly once. Condition: exactly two vertices have odd degree (the start and end of the trail).
- A graph that is neither Eulerian nor semi-Eulerian has more than two odd-degree