Spanning trees, postman and salesman problems
In a minute
Graph algorithms answer route questions: can you cover every road once, how cheaply can you connect every site, and what is the shortest round trip along every road or through every place? You name routes, find , and solve the Chinese postman and .
You'll be able to
- Name a route as a , , , or .
- Decide from the odd vertices whether an or circuit exists, and find and cycles.
- Find a minimum spanning tree with , and Prim's matrix method.
- Solve the with up to four odd vertices, explain why the method works and justify your choice of algorithm.
- Turn a practical travelling salesman problem into a , and bound the best tour with the nearest neighbour and .
Before you start2 quick questions on what this builds on
Revise first: 1.6 Rounding, bounds and percentage error, 3.14 Graph theory basics and 3.15 Adjacency matrices and walks
Walks, trails, paths, circuits and cycles
In 3.15 a walk was any sequence of edges, each starting where the last one finished. Adding a rule, such as never reusing a road, gives the route a new name.
So every path is a trail, and every cycle is a circuit, but not the other way round. Name a route by its vertices in order: ABDA is closed, because it finishes where it starts.
Try it first, then reveal one step at a time.
- (a) ADEC uses the edges AD, DE and EC. No vertex appears twice, so no edge can repeat. It is a path.
- (b) ABDCB uses four different edges, but B appears twice. It is a trail, not a path, and it is not closed.
- (c) DABDCED uses six different edges and finishes at its start, D, so it is a circuit. D also appears in the middle, so it is not a cycle.
- (a) path, (b) trail, (c) circuit
Try it first, then reveal one step at a time.
- Go from D to E. E's only other edge is EC, so every such cycle begins D, E, C.
- From C, return to D without repeating a vertex: along CD, via B, or via B and A.
- So the cycles are DECD, DECBD and DECBAD. Always starting D, E stops you counting a cycle twice, once in each direction.
Eulerian and Hamiltonian routes
Can you travel every edge exactly once (Euler)? Can you visit every vertex exactly once (Hamilton)?
A vertex with odd degree is an . A route passing through a vertex uses two of its edges, one in and one out.
The degrees add up to twice the number of edges, so every graph has an even number of odd vertices.
Try it first, then reveal one step at a time.
- (a) , , , , . Check: edges.
- (b) The graph is connected with exactly two odd vertices, B and C. So there is an Eulerian trail between B and C, but no Eulerian circuit: the visitor can walk every footpath once, but can't finish where they started.
- (c) Start at B and finish at C: BA, AD, DB, BC, CD, DE, EC uses all edges once.
There is no simple test like the odd-vertex rule. Find a Hamiltonian path or cycle by trying; rule one out with a reason. For example, a vertex of degree rules out a Hamiltonian cycle, which must enter and leave every vertex by different edges.
Eulerian: every edge once, vertices may repeat. Hamiltonian: every vertex once, edges may go unused.
Try it first, then reveal one step at a time.
- (a) F has degree (only DF). A cycle needs two different edges at F, so there is no Hamiltonian cycle: the visitor can't see every gallery once and return to the start.
- (b) A path from A must finish at F, so it ends D, F.
- Try A, C, E, B, D, F: AC, CE, EB, BD and DF are all edges, and each gallery appears once.
Minimum spanning trees: Kruskal's and Prim's algorithms
With positive weights, the cheapest network joining every site has no cycle, since one of its edges could go. So it is a tree.
Recall from 3.14: a tree with vertices has edges.
Kruskal's algorithm builds the tree cheapest edge first:
1. List the edges in order of weight, smallest first.
2. Take each edge in turn. Add it, unless it would make a cycle with the edges already chosen; then reject it.
3. Stop when you have edges.
Try it first, then reveal one step at a time.
- There are vertices, so the tree needs edges.
- In order of weight: BC , CE , AB , CD , DE , AC , EF , and so on.
- Add BC, CE, AB and CD. None of them makes a cycle.
- Reject DE (): it would make the cycle C–D–E. Reject AC (): it would make A–B–C.
- Add EF (). That makes edges, so stop.
- Cost , so the least cost is $42\,000.
Prim's algorithm grows one tree from a starting vertex:
1. Choose a start vertex.
2. Add the least-weight edge that joins a vertex already in the tree to a vertex not yet in it.
3. Repeat until every vertex is in the tree. Each edge reaches a new vertex, so no cycle can form.
When the weights are given in a table, run Prim's algorithm on the table itself. This is the matrix method:
1. Choose a start vertex. Cross out its row and number its column .
2. In the numbered columns, find the smallest entry not crossed out. It is the next edge; its row is the next vertex.
3. Cross out the new vertex's row and give its column the next number.
4. Repeat until every column has a number.
Try it first, then reveal one step at a time.
- Cross out row V; number column V as . Its smallest entry is (row X): add VX.
- Cross out row X; number column X as . Columns V and X now show and . Smallest: (row W). Add XW.
- Cross out row W; number column W as . Rows Y and Z remain; columns V, X and W show ; ; . Smallest: (row Y). Add XY.
- Cross out row Y; number column Y as . Row Z shows . Smallest: . Add YZ.
- Order V, X, W, Y, Z. Total m. The last edge is the shortest: Prim's adds edges as they reach new vertices, not by weight.
The Chinese postman problem
A machine must paint the centre line of every street and return to its depot. Now every edge must be covered, with as little extra distance as possible.
If every vertex is even, an Eulerian circuit is the answer: its weight is the total weight of the graph.
1. Find the odd vertices.
2. List every way to pair them up. Find the shortest route for each pair; it may pass through other vertices.
3. Choose the pairing with the least total, and repeat those routes.
4. Least weight total weight of all the edges weight of the repeated routes.
Four odd vertices A, B, C, D give three pairings: AB with CD, AC with BD, AD with BC.
Try it first, then reveal one step at a time.
- Degrees: A , B , C , D , E . The odd vertices are B and D.
- Shortest B to D: direct BD is m, but B–C–D is m.
- Total length of all streets: m.
- Repeat BC and CD. Least distance m.
- One such route is ABCDBCDECA: edges, the streets plus BC and CD a second time.
Try it first, then reveal one step at a time.
- Degrees: A , B , C , D , E , F . The odd vertices are A, B, D and F.
- Shortest routes: AB is direct, but A–C–B is . AD . AF: A–D–F . BD: B–C–D . BF: B–E–F . DF .
- Pairings: AB, DF: . AD, BF: . AF, BD: . The least is .
- All corridors: m.
- Least distance m, walking AC, CB and DF twice. Starting at C changes nothing: a closed route can start anywhere on it.
Travelling salesman: least distances and an upper bound
A piano tuner visits each client once and drives home. Now every vertex must be visited, as quickly as possible.
In the classical problem every pair of vertices is joined, and no detour beats a direct edge. On real maps some pairs have no direct road, and some detours are quicker.
This table turns a practical problem into the classical one. A tour using an entry may really drive past other vertices, which is fine: each client is still visited once.
Try it first, then reveal one step at a time.
- HP: direct minutes, but H–Q–P takes . Use .
- HR: no direct road. H–S–R takes ; H–Q–R takes . Use .
- PS: no direct road. P–R–S takes ; P–Q–S takes . Use .
- Every other pair keeps its direct time (QR: direct, via S). The table is
The builds a tour quickly:
1. Start at the given vertex.
2. Go to the nearest vertex you have not yet visited.
3. When every vertex has been visited, return to the start.
Try it first, then reveal one step at a time.
- From H the nearest client is Q ().
- From Q: P , R , S . Go to S. From S: P , R . Go to R.
- From R only P is left (). Return P to H ().
- HQSRPH: , so the best tour takes at most minutes. The last leg is really the drive P–Q–H, passing Q without visiting.
A lower bound: the deleted vertex algorithm
An upper bound says the best tour is no worse; a says no tour can do better.
The deleted vertex algorithm:
1. Delete one vertex and every edge joined to it.
2. Find a minimum spanning tree of the vertices that remain.
3. Add the two least-weight edges that joined the deleted vertex to the others. The total is a lower bound.
Keep the largest lower bound and the smallest upper bound.
Try it first, then reveal one step at a time.
- Delete H. Kruskal's on P, Q, R, S: RS , QS , PQ , which is edges of weight .
- The two least-weight edges from H are HQ and HS .
- Lower bound minutes.
- With the upper bound from H: , where minutes is the least driving time.
Try it first, then reveal one step at a time.
- (a) Delete P. Kruskal's on H, Q, R, S: RS , HQ , HS , weight .
- Add the two least edges from P, PQ and PR : lower bound minutes, better than .
- (b) A real tour takes minutes, so , giving . The tour H, S, R, P, Q, H is optimal: no order of visits needs less driving.
Common mistakes
- Listing Kruskal's edges in any order, or finding the tree by eye. Write edges in the order considered, with the rejected ones.
- Giving an open Eulerian trail when the route must return to its start. A closed route repeats the shortest routes between odd vertices.
- Running a travelling salesman algorithm on the road map itself, so missing roads and quicker detours are missed. Complete the least distances table first.
- In the deleted vertex algorithm, putting the deleted vertex in the spanning tree, or adding the two lightest edges in the whole graph instead of at the deleted vertex.
- Calling a nearest neighbour total a lower bound. It is a real tour's weight, so it is an upper bound.
Exam tips
- “Use Kruskal's / Prim's algorithm”: show the edges, or Prim's vertices, in the order added, and state that edges are needed. A tree with no order shown loses marks.
- “Explain why” the Chinese postman method works: edges are used in pairs at each vertex, so odd vertices force repeats, and repeating the least-weight pairing makes every vertex even.
- “Justify your choice of algorithm”: every edge at least once is the Chinese postman problem; every vertex once and back is the travelling salesman problem; connecting everything cheaply is a minimum spanning tree.
Key takeaways
Practise this
13 past-paper questions on Minimum spanning trees in the AI HL bank, each with a mark scheme and a worked explanation.
Also: Chinese postman problem (7) · Travelling salesman problem (12)