This note covers three classic network problems on weighted graphs: joining every vertex as cheaply as possible (minimum spanning trees), travelling along every edge at least once and returning to the start (the Chinese postman problem), and visiting every vertex once and returning (the travelling salesman problem). Each has a clear algorithm, and the last needs bounds because it has no quick exact method.
Key ideas
Minimum spanning tree (MST). A spanning tree joins all vertices using no cycles. If the edges have weights, the MST is the spanning tree of smallest total weight. A network with \( n \) vertices always gives a tree with \( n-1 \) edges. Two algorithms find it:
- Kruskal's algorithm. List the edges in order of increasing weight. Take each edge in turn and accept it unless it would form a cycle. Stop when you have \( n-1 \) edges.
- Prim's algorithm. Start at any vertex. Repeatedly add the shortest edge that joins a vertex already in the tree to one that is not. Stop when all vertices are included.
Both give a tree of the same total weight. If several edges have the same weight, different trees with the same total are possible.
Eulerian trails and circuits. An Eulerian trail uses every edge exactly once. An Eulerian circuit does the same and returns to the start. In a connected graph:
- all vertices of even degree means an Eulerian circuit exists;
- exactly two vertices of odd degree means an Eulerian trail exists, starting at one odd vertex and ending at the other;
- more than two odd vertices means neither exists.
Chinese postman problem. Find the shortest closed route that travels along every edge at least once, such as a delivery or gritting route. If every vertex has even degree, the answer is simply the total weight of all edges. Otherwise some edges must be repeated:
- Find the odd-degree vertices (there is always an even number of them).
- Pair them up in every possible way. For each pair, use the shortest path between the two vertices (this may be several edges, not necessarily the direct edge).
- Choose the pairing with the smallest total. Repeat those paths.
- Route length = total weight of the graph + the repeated paths.
Travelling salesman problem (TSP). Find the shortest closed route that visits every vertex exactly once and returns to the start (a Hamiltonian cycle of least weight) in a complete weighted graph. No fast algorithm is known that always finds the exact answer, so we find bounds:
- Upper bound. Any valid tour gives one, because the best tour cannot be longer than it. The nearest neighbour method builds a tour by moving from the current vertex to the nearest unvisited vertex, and finally back to the start. Try several starting vertices and keep the smallest.
- Lower bound (deleted vertex method). Delete one vertex and find the MST of the remaining vertices. Add the lengths of the two shortest edges from the deleted vertex. The result cannot be more than the best tour. Repeat for different deleted vertices and keep the largest lower bound.
The optimal tour length lies between the best lower bound and the best upper bound. When a real problem lets a vertex be visited more than once, first build a complete table of shortest distances between every pair of vertices, then apply the method to that table.
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| Spanning tree | Tree containing every vertex; has \( n-1 \) edges. |
| Kruskal / Prim | Algorithms for the minimum spanning tree. |
| Eulerian circuit | Uses every edge once and returns to start; needs all vertices even. |
| Eulerian trail | Uses every edge once; needs exactly two odd vertices. |
| Chinese postman length | Total weight of all edges + weight of the cheapest repeated paths joining odd vertices in pairs. |
| Hamiltonian cycle | Cycle visiting every vertex exactly once. |
| Upper bound (TSP) | Length of any tour, such as from nearest neighbour. |
| Lower bound (TSP) | MST of remaining vertices + two shortest edges at the deleted vertex. |
Worked examples
Example 1 Six villages \( A\text{–}F \) are to be linked by cable. Possible links and their costs (in thousands of euros): \( AB\,7,\ AC\,4,\ BC\,3,\ BD\,5,\ CD\,8,\ CE\,6,\ DE\,2,\ DF\,9,\ EF\,5 \). Use Kruskal's algorithm to find the cheapest network and its cost.
Order the edges: \( DE\,2,\ BC\,3,\ AC\,4,\ BD\,5,\ EF\,5,\ CE\,6,\ AB\,7,\ CD\,8,\ DF\,9 \).
Accept \( DE \) (2), \( BC \) (3), \( AC \) (4). Accept \( BD \) (5): it joins \( \{A,B,C\} \) to \( \{D,E\} \). Accept \( EF \) (5): it brings in \( F \).
That is 5 edges for 6 vertices, so we stop. (Rejected: \( CE \) would make the cycle \( C, B, D, E \); \( AB \) would make the cycle \( A, B, C \).)
Cost \( = 2 + 3 + 4 + 5 + 5 = 19 \).
Check with Prim from \( A \): \( AC\,4 \), then \( BC\,3 \), then \( BD\,5 \), then \( DE\,2 \), then \( EF\,5 \). The same tree and total.
Answer: edges \( DE, BC, AC, BD, EF \); minimum cost 19 thousand euros.
Example 2 A street-sweeper must cover every road in a district and return to the depot. Four junctions \( A, B, C, D \) are joined by six roads with lengths in km: \( AB\,3,\ AC\,5,\ AD\,4,\ BC\,6,\ BD\,2,\ CD\,7 \). Find the length of the shortest route.
Every junction has 3 roads, so all four have odd degree. No Eulerian circuit exists, and some roads must be repeated.
Total of all roads: \( 3 + 5 + 4 + 6 + 2 + 7 = 27 \) km.
Pair the odd vertices in the three possible ways. Each shortest path here is the direct road (for example, \( A \) to \( C \): direct 5, via \( B \) 9, via \( D \) 11).
\( AB + CD = 3 + 7 = 10 \).
\( AC + BD = 5 + 2 = 7 \).
\( AD + BC = 4 + 6 = 10 \).
The smallest is 7, so repeat roads \( AC \) and \( BD \).
Route length \( = 27 + 7 = 34 \) km.
Answer: 34 km.
Example 3 A courier must visit towns \( A, B, C, D, E \) once each and return. Distances (km): \( AB\,12,\ AC\,10,\ AD\,19,\ AE\,8,\ BC\,3,\ BD\,7,\ BE\,14,\ CD\,6,\ CE\,15,\ DE\,9 \). Find an upper bound using nearest neighbour from \( A \), and a lower bound by deleting \( A \).
Upper bound. From \( A \), the nearest town is \( E \) (8). From \( E \), the nearest unvisited is \( D \) (9). From \( D \), the nearest unvisited is \( C \) (6). Then \( B \) (3). Return \( B \) to \( A \) (12).
Tour \( A\,E\,D\,C\,B\,A \): \( 8 + 9 + 6 + 3 + 12 = 38 \) km. So the best tour is at most 38 km.
Lower bound. Delete \( A \). The remaining towns \( B, C, D, E \) have distances \( BC\,3,\ CD\,6,\ BD\,7,\ DE\,9,\ BE\,14,\ CE\,15 \).
Kruskal: accept \( BC\,3 \), accept \( CD\,6 \), reject \( BD\,7 \) (cycle), accept \( DE\,9 \). MST weight \( = 3 + 6 + 9 = 18 \).
The two shortest edges at \( A \) are \( AE\,8 \) and \( AC\,10 \), adding 18 + 8 + 10 = 36.
So the best tour is at least 36 km.
Answer: upper bound 38 km, lower bound 36 km, so the shortest tour is between 36 and 38 km.
Common errors
- Common error: in Kruskal's algorithm, accepting an edge that creates a cycle. Always check before adding.
- Common error: in the Chinese postman problem, repeating the direct edge between two odd vertices when a shorter path through other vertices exists.
- Common error: forgetting to add the repeated paths to the total weight of the graph, or repeating paths for graphs where all degrees are already even.
- Common error: treating the nearest neighbour tour as the optimal tour. It is only an upper bound.
- Common error: in the deleted vertex method, adding the two longest edges at the deleted vertex instead of the two shortest, or leaving the deleted vertex in the MST.
Exam tip: Show the order in which you consider edges and state clearly which ones you reject and why. For bounds, say "upper bound" or "lower bound" in your answer, and give the final interval for the optimal tour.
Check yourself
- How many edges does a minimum spanning tree of a connected graph with 7 vertices have?
Answer
A tree on \( n \) vertices has \( n - 1 \) edges, so 6. - A connected graph has vertex degrees \( 2, 4, 3, 3, 2 \). Does it have an Eulerian circuit? An Eulerian trail?
Answer
There are exactly two odd vertices (the two of degree 3). So there is no Eulerian circuit, but there is an Eulerian trail that starts at one degree-3 vertex and ends at the other. - A hexagonal ring road has sections \( AB\,3,\ BC\,4,\ CD\,5,\ DE\,2,\ EF\,6,\ FA\,4 \) (km) and a link road \( BE\,12 \). Find the shortest route that covers every road and returns to the start.
Answer
Total weight \( = 3+4+5+2+6+4+12 = 36 \). Odd vertices: \( B \) and \( E \) (degree 3). Shortest path from \( B \) to \( E \): via \( C, D \) is \( 4+5+2 = 11 \), better than the direct 12 or via \( A, F \) (13). Route length \( = 36 + 11 = 47 \) km. - Using the distances in Example 3, find the lower bound given by deleting \( D \).
Answer
Towns \( A, B, C, E \): \( BC\,3,\ AE\,8,\ AC\,10,\ AB\,12,\ BE\,14,\ CE\,15 \). MST: \( BC\,3,\ AE\,8,\ AC\,10 \) (joins the two parts), total 21. Two shortest edges at \( D \): \( CD\,6 \) and \( BD\,7 \), total 13. Lower bound \( = 21 + 13 = 34 \) km.