MST algorithms (prim’s, Kruskal’s), Chinese postman, travelling salesman: notes and practice questions
- Graph Terminology:
- Complete Graph: Each vertex connected to every other.
- Weighted Graph: Edges have numerical values (weights).
- Directed Graph: Edges have direction; in-degree is number of edges leading to a vertex.
- Trail: A walk with no repeated edges.
- Circuit: A trail that begins and ends at the same vertex.
- Path: A walk with no repeated vertices.
- Cycle: A path that starts and ends at the same vertex.
- Spanning Tree: A subgraph that is a tree, contains all vertices, has no cycles, and has `` edges (where `` is the number of vertices).
- Minimum Spanning Tree (MST): A spanning tree with the lowest possible total edge weight.
- Kruskal's Algorithm (MST):
- Sort all edges by increasing weight.
- Select the edge of least weight.
- Select the next least weight edge that does not form a cycle with previously chosen edges.
- Repeat until all vertices are connected.
- Prim's Algorithm (MST - Graph):
- Start at any vertex, choose the least weight edge connected to it.
- Choose the least weight edge incident to any vertex already in the tree, ensuring it does not form a cycle.
- Repeat until all vertices are added to the tree.
- Prim's Algorithm (MST - Matrix):
- Select a starting vertex, cross out its column, label its row '1'.
- Circle the lowest value in the labelled row, add the edge, cross out the column of the new vertex.
- Label the new vertex's row. Circle the lowest value in any currently labelled row, add the edge, cross out the column of the new vertex.
- Repeat until all rows are labelled.
- Chinese Postman Problem (CPP): Find the route of least weight that starts and finishes at the same vertex and traverses every edge at least once.
- All vertices have even degree: The shortest route is the sum of all edge weights.
- Two odd vertices: Find the shortest path between them; add its weight to the total sum of all graph edges.
- Four odd vertices: Consider all three possible pairings of odd vertices. Find the shortest path for each pair. Choose the pairing with the lowest combined repeated distance and add this to the total sum of all graph edges.
- Travelling Salesman Problem (TSP): Find the route of least weight that starts and finishes at the same vertex and visits every other vertex exactly once.
- Nearest Neighbour Algorithm (TSP Upper Bound):
- Choose a starting vertex.
- Follow the edge of least weight from the current vertex to an unvisited adjacent vertex.
- Repeat until all vertices have been visited.
- Add the final edge to return to the starting vertex.
- Deleted Vertex Algorithm (TSP Lower Bound):
- Choose a vertex, delete it and all its incident edges.
- Find the MST of the remaining graph.
- Add the weights of the two shortest edges (from the original graph) that were connected to the deleted vertex to the MST weight.
- The best lower bound is the highest value obtained by deleting different vertices.
- GDC Use: Use for summing edge weights; explicitly write down values for method marks.
- Exam Tips:
- Distinguish between trails/circuits (focus on edges, CPP) and paths/cycles (focus on vertices, TSP).
- State the order in which edges are selected for MST algorithms.
- Look for hidden shorter routes between vertices (indirect paths).
- Do not confuse Prim's (builds a tree, multiple circles in a labelled row possible) with Nearest Neighbour (builds a path, only one circle per column) when using tables.
- Lower bound table entries may represent combinations of edges, not just direct connections.
- Tables for undirected graphs are symmetric along the leading diagonal.
How it is examined
A long-question favourite because it has a natural sequence: identify odd vertices, run an algorithm, state a bound, then interpret. Two constraints define what is legal: no more than four odd vertices for a Chinese postman problem, and a practical travelling salesman problem must be reduced to the classical one via a table of least distances. Note that upper and lower bounds are asked for separately, and the deleted vertex algorithm gives the lower bound, which is the pairing students most often reverse. Students are asked to explain and justify here, not only to compute, so the marks are not all method marks.
- Tree and cycle algorithms with undirected graphs.
- Walks, trails, paths, circuits, cycles.
- Eulerian trails and circuits.
- Hamiltonian paths and cycles.
Linking questions
- Other contexts: using GPS to find the shortest route home; describing current and voltage in circuits as cycles; vehicle routing problems.
- International-mindedness: the "Bridges of Konigsberg" problem. The Chinese postman problem was first posed by the Chinese mathematician Kwan Mei-Ko in 1962.
- TOK: what practical problems can or does mathematics try to solve? Why are problems such as the travelling salesman problem so enduring? What does it mean to say the travelling salesman problem is "NP hard"?
Practice questions
2 questions · 1 medium · 1 hardQuestion 1
MediumPaper 1 · calculator13 marksA team of scientists needs to establish communication links between six remote research outposts (R1, R2, R3, R4, R5, R6) in an arctic region. The cost, in thousands of dollars, to lay a direct cable between any two outposts is shown in the table below.
| From/To | R1 | R2 | R3 | R4 | R5 | R6 |
|---|---|---|---|---|---|---|
| R1 | - | 70 | 85 | 60 | 95 | 110 |
| R2 | 70 | - | 50 | 75 | 40 | 80 |
| R3 | 85 | 50 | - | 35 | 65 | 90 |
| R4 | 60 | 75 | 35 | - | 55 | 70 |
| R5 | 95 | 40 | 65 | 55 | - | 45 |
| R6 | 110 | 80 | 90 | 70 | 45 | - |
The data above can be represented by a graph G.
Use Prim's algorithm to find the weight of the minimum spanning tree of the subgraph of G obtained by deleting R1 and starting at R2. List the order in which the edges are selected.
Hence find a lower bound for the total cost needed to establish a full communication circuit visiting all outposts, starting and finishing at R1.
Describe how an improved lower bound might be found.
Remember to first remove R1 and all its incident edges from the graph. Then, apply Prim's algorithm starting from R2 on the remaining subgraph. Always choose the minimum weight edge that connects a vertex in the current tree to a vertex not yet in the tree.
To find a lower bound for the Travelling Salesperson Problem (TSP) using an MST, you need to add the two shortest edges connected to the deleted vertex (R1) back to the weight of the MST you found in part (a.i).
Consider the effect of which vertex is deleted when applying this method for finding a lower bound.
Question 2
HardPaper 1 · calculator5 marksA data network connects several hubs, represented by vertices A, B, C, D, E. The numbers on the edges represent the cost (in hundreds of dollars) to lay a new fibre optic cable between two hubs. An engineer needs to inspect all existing cables.
Write down the vertices with odd degree.
The total cost of all existing cables is dollars. The engineer wants to traverse every cable in the network, starting and ending at the same hub, while minimizing the total distance travelled. This may involve traversing some cables more than once.
Find two expressions, in terms of , for the minimum total cost (in hundreds of dollars) required to traverse all cables, beginning and ending at the same hub.
Include in your answer the interval of values of for which each expression is valid.
The degree of a vertex is the number of edges connected to it. A vertex has an odd degree if an odd number of edges connect to it.
To traverse all edges starting and ending at the same vertex, all vertices must have an even degree. Identify the odd-degree vertices from part (a). You need to add edges to the graph to make all degrees even. This involves finding the shortest paths between pairs of odd-degree vertices and choosing the pairing that minimizes the sum of these shortest paths. Consider different cases for the value of .
No question on this page matches those filters. Try another difficulty or paper.
Every MST algorithms (prim’s, Kruskal’s), Chinese postman, travelling salesman question, marked for you
Every answer is marked mark by mark, IB-style, and the AI tutor helps when you are stuck.
Where marks are lost
- Leaving an answer in calculator notation. Never accepted in a final answer, and AI's constant calculator use makes this the easiest slip in the whole subject.
