3.16 · AHL · HL onlyPaper 1Paper 2Paper 3

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
Check yourself
A has 1111 vertices. How many edges does it have?
Check yourself
In a walk, may an edge be used more than once?

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.

A graph with five vertices A, B, C, D and E. Edges: A to B, B to C, C to D, D to A, B to D, D to E and C to E. A B C D E
Footpaths between five features of a garden.
Worked exampleUse the garden graph. For each route, write down the most specific name: walk, trail, path, circuit or cycle. (a) ADEC (b) ABDCB (c) DABDCED

Try it first, then reveal one step at a time.

  1. (a) ADEC uses the edges AD, DE and EC. No vertex appears twice, so no edge can repeat. It is a path.
Check yourself
In the garden graph, what is the route BDCBDA?
Worked exampleHow many different cycles in the garden graph use the footpath DE? List them.

Try it first, then reveal one step at a time.

  1. Go from D to E. E's only other edge is EC, so every such cycle begins D, E, C.

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.

Worked exampleUse the garden graph. (a) Find the degree of each vertex. (b) Hence decide whether a visitor can walk along every footpath exactly once, and whether they can also finish where they started. (c) Write down an Eulerian trail.

Try it first, then reveal one step at a time.

  1. (a) deg⁡(A)=2\deg(\mathrm{A}) = 2, deg⁡(B)=3\deg(\mathrm{B}) = 3, deg⁡(C)=3\deg(\mathrm{C}) = 3, deg⁡(D)=4\deg(\mathrm{D}) = 4, deg⁡(E)=2\deg(\mathrm{E}) = 2. Check: 2+3+3+4+2=14=2×72 + 3 + 3 + 4 + 2 = 14 = 2 \times 7 edges.
Check yourself
A connected graph has vertex degrees 2,4,3,2,52, 4, 3, 2, 5 and 44. Which statement is true?

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 11 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.

A graph with six vertices A to F. Edges: A to B, A to C, B to C, B to D, B to E, C to E, D to E and D to F. A B C D E F
Doorways between six galleries in a museum.
Worked exampleA visitor to the museum wants to see every gallery exactly once. (a) Explain why there is no Hamiltonian cycle. (b) Find a Hamiltonian path that starts at A.

Try it first, then reveal one step at a time.

  1. (a) F has degree 11 (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.
Check yourself
Which route is a Hamiltonian cycle of the garden graph?

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 nn vertices has n−1n - 1 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 n−1n - 1 edges.

A weighted graph with six vertices A to F. Edges and weights: A to B 8, A to C 11, A to F 15, B to C 6, B to D 13, C to D 9, C to E 7, D to E 10, D to F 17, E to F 12. 8 11 15 6 13 9 7 10 17 12 B D A F C E
Cost, in thousands of dollars, of laying a pipe between two fields. Not to scale.
Worked exampleA farm will lay irrigation pipes so that all six fields A to F are connected. Use Kruskal's algorithm to find a minimum spanning tree, listing the edges in the order you consider them. Hence find the least cost.

Try it first, then reveal one step at a time.

  1. There are 66 vertices, so the tree needs 6−1=56 - 1 = 5 edges.

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.

Check yourself
Use Prim's algorithm on the fields graph, starting at F. Which edge is added third?

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 11.

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.

Worked exampleA hospital plans pneumatic tubes to send samples between five departments, V, W, X, Y and Z. The table gives the tube length, in metres, for each pair. VWXYZV−52416245W52−335768X4133−4454Y625744−36Z45685436−\begin{array}{c|ccccc} & \mathrm{V} & \mathrm{W} & \mathrm{X} & \mathrm{Y} & \mathrm{Z} \\ \hline \mathrm{V} & - & 52 & 41 & 62 & 45 \\ \mathrm{W} & 52 & - & 33 & 57 & 68 \\ \mathrm{X} & 41 & 33 & - & 44 & 54 \\ \mathrm{Y} & 62 & 57 & 44 & - & 36 \\ \mathrm{Z} & 45 & 68 & 54 & 36 & - \end{array} Use Prim's algorithm on the table, starting at V, to find the least total length of tube. State the order in which the departments join the tree.

Try it first, then reveal one step at a time.

  1. Cross out row V; number column V as 11. Its smallest entry is 4141 (row X): add VX.
Check yourself
Cable lengths, in metres, between four kiosks are AB 4343, AC 3636, AD 5757, BC 3939, BD 3232 and CD 4949. Find the total length of a minimum spanning tree.
Check yourself
Distances between 2020 towns are given in a table. Which algorithm suits a minimum spanning tree best, and why?

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.

A weighted graph with five vertices A to E. Edges and lengths in metres: A to B 380, A to C 650, B to C 270, B to D 720, C to D 410, C to E 820, D to E 230. 380 650 270 720 410 820 230 A B C D E
Streets in a housing estate, lengths in metres. The depot is at A. Not to scale.
Worked exampleThe painting machine starts and finishes at the depot A and must paint every street in the estate. Find the least distance it travels.

Try it first, then reveal one step at a time.

  1. Degrees: A 22, B 33, C 44, D 33, E 22. The odd vertices are B and D.
Check yourself
In the estate example, which streets does the machine travel twice?
A weighted graph with six vertices A to F. Edges and lengths in metres: A to B 61, A to C 31, A to D 55, B to C 26, B to E 47, C to D 38, C to F 64, D to F 29, E to F 33. 61 31 55 26 47 38 64 29 33 A B C D E F
Corridors in a warehouse, lengths in metres. Not to scale.
Worked exampleA security guard must walk along every corridor of the warehouse at least once, starting and finishing at the office at C. Find the least distance the guard walks.

Try it first, then reveal one step at a time.

  1. Degrees: A 33, B 33, C 44, D 33, E 22, F 33. The odd vertices are A, B, D and F.
Check yourself
The guard may now start and finish at any two different places. Find the least distance needed to walk along every corridor.
Check yourself
Why must a closed route covering every edge repeat an edge at an odd vertex?

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.

A weighted graph with five vertices H, P, Q, R and S. Edges and times in minutes: H to P 84, H to Q 30, H to S 33, P to Q 48, P to R 51, Q to R 63, Q to S 45, R to S 24. There is no direct road from H to R or from P to S. 84 30 33 48 51 63 45 24 H P Q S R
Driving times, in minutes, between a piano tuner's home H and four clients P, Q, R and S. Not to scale.
Worked exampleComplete the table of least distances for the tuner's graph. Write down every entry that is not simply a direct road.

Try it first, then reveal one step at a time.

  1. HP: direct 8484 minutes, but H–Q–P takes 30+48=7830 + 48 = 78. Use 7878.

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.

Worked exampleStarting at H, use the nearest neighbour algorithm on the table of least distances to bound the tuner's driving time from above.

Try it first, then reveal one step at a time.

  1. From H the nearest client is Q (3030).
Check yourself
Use the nearest neighbour algorithm on the same table, but start at P. Find the weight of the tour, in minutes.

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.

Worked exampleUse the deleted vertex algorithm, deleting H, to find a lower bound for the tuner's driving time. Use the table of least distances.

Try it first, then reveal one step at a time.

  1. Delete H. Kruskal's on P, Q, R, S: RS 2424, QS 4545, PQ 4848, which is 33 edges of weight 117117.
Worked example(a) Delete P instead to find another lower bound for the tuner's driving time. (b) Hence, using the 186186-minute tour found by starting at P, find the least driving time.

Try it first, then reveal one step at a time.

  1. (a) Delete P. Kruskal's on H, Q, R, S: RS 2424, HQ 3030, HS 3333, weight 8787.
Check yourself
The tuner's least driving time is 186186 minutes. They also spend 5050 minutes with each of the 44 clients. Find the total time, in minutes, from leaving home to getting back.
Check yourself
For one travelling salesman problem, deleting different vertices gives lower bounds of 412412, 437437 and 425425 km. Two nearest neighbour tours weigh 468468 and 451451 km. Which interval for the least tour length TT km is best?

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 n−1n - 1 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

Learn thisTrail: no repeated edge. Path: no repeated vertex. Circuit: a closed trail. Cycle: a circuit with no repeated vertex except the start, which is also the end.
Learn thisConnected graph: all vertices even gives an Eulerian circuit; exactly two odd vertices gives an Eulerian trail between them, but no circuit; more than two odd gives no Eulerian trail.
Learn thisHamiltonian path or cycle: every vertex exactly once. No degree test; find one by trying, or give a reason none exists (a vertex of degree 11 rules out a cycle).
Learn thisAn MST of a connected weighted graph with nn vertices has n−1n - 1 edges. Kruskal's: cheapest edges first, rejecting cycles. Prim's: grow from one vertex by the cheapest edge to a new vertex; it runs on a table.
Learn thisChinese postman (closed route, every edge, connected graph): least weight == total edge weight ++ least total of shortest routes over the pairings of the odd vertices.
Learn thisTravelling salesman: use the table of least distances. Nearest neighbour gives an upper bound; deleted vertex (MST of the rest plus the two lightest edges at the deleted vertex) gives a lower bound. Keep the largest lower and smallest upper bound.

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)

Practise Minimum spanning trees →