Maths IA · Geometry and trigonometry · topic 65 of 97
The cheapest network: spanning trees and Steiner points · IB Maths IA idea: guide, sample graph and step-by-step plan
add a junction: shorter?To join four towns with the least cable, you might lay a road between neighbours. Add a junction in the middle and the total gets shorter, provided the roads meet at exactly the right angle.
- ✓ you like finding the shortest of something and proving why
- ✓ you are happy mixing algorithms with calculus or vectors
- ✓ you can name a real set of towns, buildings or stations to connect
The big idea
A minimum spanning tree joins every point using the least total length, and simple algorithms (Kruskal, Prim) find it and are provably optimal. Allow extra junctions and you can do better: at a Steiner point the roads meet at 120 degrees. You can prove that angle by minimising a sum of distances, with calculus or with vectors, and then test it on real towns. Gilbert and Pollak conjectured that a Steiner tree is never shorter than about 86.6% of the spanning tree, a ratio of √3/2; it is proved for a few points, and a general proof is still disputed. Graph theory is AI HL content; the calculus and vectors in the Steiner part make this a good fit for AA HL as well. The algorithms are routine. The marks come from the proof and the comparison: why the 120 degree rule holds, and how much a Steiner tree really saves on a real map.
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 →
Build the tree both ways on six or more real points and show that the two trees have the same total length.
→ Two algorithms, one answer. Explain why they agree, and what happens when two edges have equal length.Minimise SA + SB + SC for a triangle by calculus or with vectors and find where the angles are 120 degrees.
→ A multivariable minimisation made simple by unit vectors: they must add to zero. Check the claim numerically.Compare the spanning tree with the Steiner tree for a square and find the saving exactly.
→ An exact answer, 1 + √3 against 3, which you can compare with a numerical minimisation.For many random sets of points, compute the ratio of the Steiner tree to the spanning tree and see how close to √3/2 it gets.
→ A simulation with a conjectured bound. Find which arrangement attains it exactly.Take stations or buildings from a real map and compare the cable lengths with real road distances.
→ Straight lines are not roads. State what 'length' means and how the answer changes.Give each extra junction a fixed cost and find when adding one stops being worth it.
→ A trade-off with a break-even point, which is the part a real planner would care about.Your Maths IA research question: run the check
which towns, which distance?Write your own question first. Then make sure it ticks every box:
- Names the points to connect and where their coordinates come from.
- Says what is minimised (total length, cost) and what counts as a connection.
- States what is proved and what is only computed or tested.
- Compares spanning tree and Steiner tree on the same points, with a measured saving.
- Is narrow enough to prove the three-point case fully and test the rest.
The model
The same three towns joined two ways. Draw your own towns, find the cheapest tree, then try to add a junction and see if the total falls.
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 towns, why a short network matters, and a prediction: roughly how much can an extra junction save?
Vertices, edges, weights and what a spanning tree is, with your points and distances in a table.
Both algorithms run step by step, with a reason why the result is a minimum.
The minimisation for three points, the 120 degree condition, and a numerical check.
The square or a real set of four or five towns, comparing spanning and Steiner tree lengths.
How much a Steiner tree saves across many sets of points, set against the conjectured bound of √3/2.
Back to your aim: the saving on your real towns, with numbers.
Straight lines against real roads, cost of junctions, terrain. Say which assumption weakens the answer most.
Where the coordinates, algorithms and proofs came from.
What your Maths IA graph could look like
ceiling is the worst caseMade-up values to show the form of a strong graph: the saving from adding junctions against the number of towns. Yours will look different. example only
- One point per set of towns, with the number of towns on the horizontal axis.
- The flat line is the conjectured ceiling. Say where its value comes from, cite it, and say what is proved.
- Points should sit below the ceiling. If one does not, you have found a mistake, not a discovery.
- Say how many random sets each point averages over.
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 a spanning tree is. Before any algorithm, guess how much shorter a network can get by adding one extra junction.
- Choose the townsPick 5 to 8 real places with coordinates from a map and decide whether you use straight-line or road distance.
- Build the treeRun Kruskal and Prim on your points. Show every step and check both give the same total length.
- Trial run (1 lesson)Find the Steiner point of an equilateral triangle by hand, then check it numerically. Use that to check your method.
- Prove the 120 degreesMinimise the sum of three distances with unit vectors or partial derivatives. Show that the angles are all 120 degrees.
- Go to four pointsDo the square exactly, then a real set of four towns numerically. Compare spanning and Steiner lengths.
- Go further, with a reasonTest the ratio √3/2 by simulation, or add a cost for each junction. HL: this is where the rigour for criterion E comes from.
- Check against real distancesCompare your straight-line network with actual road lengths and explain the gap.
- Reflect as you goAfter every result write one line on what it means for a real planner and what it assumes. These lines become your evaluation.
- Cut, check, then sendCheck every diagram is labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Spanning trees – Run Kruskal's and Prim's algorithms on a distance table and compare the total lengths.
- Vectors – Write the sum of unit vectors from to each town and show it must be zero at a minimum.
- Optimisation – Minimise using derivatives or a geometric rotation argument, then check second-order behaviour.
- Trigonometry – Find the Steiner point of a square from the 120 degree condition, giving a length of .
- Simulation – Generate random point sets and compute the ratio of Steiner tree to spanning tree to test .
Key equations
Syllabus links
- 3.12Vectors: position, displacement, componentsHL
- 3.13Scalar product and angles between vectorsHL
- 5.14Implicit differentiation, related rates, optimisationHL
- 5.8Maxima, minima, inflexion and optimisation
- 3.14Graph theory: vocabulary and types of graphHL
- 3.16Euler and Hamilton paths, spanning trees, Chinese postman, travelling salesmanHL
- 3.10Vectors: components, magnitude, positionHL
- 5.9Further derivatives; chain, product, quotient rules; related ratesHL
Read up first
Data and sources to start from
Take coordinates of real towns, stations or campus buildings from an online map, convert them to a flat grid, and say which distance you use.
References to cite
- Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.
- Prim, R. C. (1957). Shortest connection networks and some generalizations. Bell System Technical Journal, 36(6), 1389-1401.
- Gilbert, E. N., & Pollak, H. O. (1968). Steiner minimal trees. SIAM Journal on Applied Mathematics, 16(1), 1-29.
- Courant, R., & Robbins, H. (1941). What is mathematics? Oxford University Press.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
120° only inside a triangle- Stopping at the first tree you find. Check with both algorithms, or prove it is a minimum.
- Adding a Steiner point to a triangle with an angle of 120 degrees or more. Then the best tree has no extra junction.
- Quoting the 120 degree rule without proving it, or proving only that it is stationary.
- Mixing straight-line distances and road distances in the same table.
- Assuming the Steiner tree always saves 13.4%. That is the worst case, not the typical case.
- Forgetting that an extra junction has a cost in real life, and ignoring it.
More Maths IA ideas like this
Delivery rounds: the Chinese postman problem●●○
Shortest route: how good is a quick heuristic?●●○
Walk every bridge once: from Königsberg to your city●●○
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.