Maths IA · Modelling · topic 82 of 97
Delivery rounds: the Chinese postman problem · IB Maths IA idea: guide, sample graph and step-by-step plan
total weight + cheapest pairingA newspaper round, a gritting lorry and a street sweeper all have to drive every street, and nobody wants to repeat more than they must. You're going to find the fewest wasted kilometres and prove you cannot do better.
- ✓ you like a puzzle that a real delivery or cleaning round has to solve
- ✓ you want a method you can prove is best, not only a good guess
- ✓ you can get a small map with distances or times
The big idea
Model the streets as a weighted graph: junctions are vertices, roads are edges, and each weight is a distance or a time. A round that uses every road exactly once exists only if every vertex has even degree. When some do not, the junctions of odd degree must be paired up, and the shortest path between each pair is driven twice. The shortest round is the total weight plus the cheapest pairing. With four odd vertices there are only three pairings, so you can check them all. Graph theory is AI HL content; on AA this is a self-taught extension. The routine part is the method. The marks come from why it is optimal, what happens with six or more odd vertices, and how the answer changes when the round need not end where it began.
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
List all pairings of the odd vertices, find the shortest path for each pair with Dijkstra's method, and total each pairing.
→ A short exhaustive check. For four odd vertices there are 3 pairings, for six there are 15, and you can show the pattern 1, 3, 15, 105.Let the round begin and end at two different junctions, such as a depot and a final drop.
→ Two odd vertices become the endpoints, so only the others need pairing. Compare the cost with the closed round.Argue that any round must repeat edges so that all degrees become even, and that the cheapest way is a pairing of shortest paths.
→ A proof, not just a recipe. The key step is that each odd vertex needs an odd number of extra visits.Use road lengths or travel times from an online map for a real round, and say which you chose and why.
→ Distance and time can give different best rounds. Explain what a driver would care about.Make some roads one way and see why the same pairing method no longer applies.
→ A directed graph needs in-degree to equal out-degree, which is a harder problem. Explain what breaks.Plan the round by eye, then compare its length with your optimal round.
→ A percentage over the best round is a measurable result. Repeat for several rounds to see how far off intuition is.Your Maths IA research question: run the check
distance or time?Write your own question first. Then make sure it ticks every box:
- Names the area or round and says what the weights measure: distance, time or cost.
- Gives the number of junctions, roads and odd vertices, so the reader knows the size of the problem.
- Says what is compared: all the pairings, an open and a closed round, or a guess against the optimum.
- Says how you will show the answer is best, not only good.
- States what the model leaves out: one-way streets, turn penalties, traffic.
The model
A weighted street graph with its odd junctions marked, and the four steps of the method. Draw the streets of your own round and mark the odd vertices.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
Which round, why it matters, and a prediction: how much longer than the total of the roads will the best round be?
Vertices, edges, weights and degrees, with every choice about what to include.
Why odd vertices must be paired, and all pairings listed for your graph.
Dijkstra's method worked out for each pair, in a table you can check.
The best pairing, the edges repeated, the route written out, and a proof that nothing shorter exists.
A different start and finish, or your own measured weights, compared with the closed round.
Back to your aim: the length of the best round and how much it cost to be fully covered.
One-way streets, turns, traffic and whether weights are really fixed. Say which matters most to the driver.
Where the map, the weights and the method came from.
What your Maths IA graph could look like
zero odd vertices: easy caseMade-up values to show the form of a strong graph: the extra distance a round needs as the number of odd vertices grows. Yours will look different. example only
- One point per round you tested, with units on both axes.
- A trend line is a claim, so say what it assumes and where it breaks.
- Mark the point with zero odd vertices: a round with no repeated roads.
- Say whether more odd vertices always means more extra distance, and test it.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictFind out what the Chinese postman problem asks. Before any method, guess how much longer the best round is than the total of the roads.
- Choose the roundPick a real area with 6 to 10 junctions, such as a delivery round or a housing estate, and say what each weight means.
- Draw the graphMark vertices, edges and weights, count every degree and mark the odd vertices on the drawing.
- Trial run (1 lesson)Find the best round on a graph with exactly two odd vertices, then four. Check by trying every pairing.
- Shortest pathsFind the shortest path between every pair of odd vertices with Dijkstra's method. Show your table.
- Choose the pairingTotal every pairing and pick the cheapest. Write the route out in order and check every road is covered.
- Go further, with a reasonTry an open round, one-way streets, or six odd vertices. HL: this is where the rigour for criterion E comes from.
- Prove it is bestExplain why any round must repeat edges to make all degrees even, so no round beats the cheapest pairing.
- Reflect as you goAfter every result write one line on what it means for the driver and what it assumes. These lines become your evaluation.
- Cut, check, then sendCheck every graph is labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Degree parity – Count the degrees and show that an Euler circuit needs every degree even, so odd vertices must be paired.
- Shortest paths – Use Dijkstra's method to find for every pair of odd vertices and tabulate the results.
- Counting pairings – Show that odd vertices have pairings and list them for .
- Route length formula – Show that the shortest closed round has length equal to the total weight plus the minimum pairing cost.
- Proof of optimality – Prove that any covering round gives an Eulerian multigraph, so repeated paths must pair the odd vertices.
Key equations
Syllabus links
- No codes for this course.
- 3.14Graph theory: vocabulary and types of graphHL
- 3.15Adjacency matrices, walks and transition matricesHL
- 3.16Euler and Hamilton paths, spanning trees, Chinese postman, travelling salesmanHL
- 1.14Matrices, determinants and inversesHL
- 4.3Averages and spread
Read up first
Data and sources to start from
Use road lengths or travel times read from an online map for a real round, and state the map date and the weight you chose.
References to cite
- Kwan, M.-K. (1962). Graphic programming using odd or even points. Chinese Mathematics, 1, 273-277.
- Edmonds, J., & Johnson, E. L. (1973). Matching, Euler tours and the Chinese postman. Mathematical Programming, 5(1), 88-124.
- Wilson, R. J. (2010). Introduction to graph theory (5th ed.). Pearson.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
shortest path, not direct road- Pairing odd vertices by direct roads only. Use the shortest path between them, which may pass through other junctions.
- Forgetting that the number of odd vertices is always even, so a graph with three odd vertices is a mistake in your count.
- Using the total weight as the length of the round. The round also drives the repeated paths.
- Assuming the round must start where the best pairing is cheapest. A closed round can start anywhere.
- Applying the method to one-way streets without saying it no longer works.
- Calling a heuristic result optimal without checking every pairing.
More Maths IA ideas like this
Walk every bridge once: from Königsberg to your city●●○
Shortest route: how good is a quick heuristic?●●○
The cheapest network: spanning trees and Steiner points●●●
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.