IB Mathematics Applications & Interpretation AHL 3.16—tree and Cycle Algorithms, Chinese Postman, Travelling Salesman Notes

Why These Algorithms Exist: Turning Networks Into Decisions

1. A network is any set of places joined by connections, such as towns joined by roads, computers joined by cables, or delivery stops joined by driving times.
2. Graph theory turns a network into vertices (the places) and edges (the connections), often carrying a weight for distance, time, or cost.
3. Real operators then ask sharp practical questions about these networks, and each question has its own algorithm.
   1. A council gritting lorry must drive down every road in winter and wants the shortest route that does so.
   2. A delivery driver must visit every customer once and wants the shortest round trip back to the depot.
   3. A broadband firm must connect every house to the network using the least total length of cable.
4. So the first skill is reading the question to decide which algorithm applies.
   1. Cover every edge and return is the Chinese postman problem.
   2. Visit every vertex once and return is the travelling salesman problem.
   3. Connect everything as cheaply as possible is the minimum spanning tree.

The Language Of Graphs: Walks, Trails, Paths, Circuits, Cycles

1. A walk is any sequence of vertices where each step moves along an edge, and repeats of edges and vertices are allowed.
2. A trail is a walk that never repeats an edge, though it may revisit a vertex.
3. A path is a walk that never repeats a vertex, which also means it never repeats an edge.
4. A circuit is a closed trail: it starts and ends at the same vertex and repeats no edge.
5. A cycle is a closed path: it starts and ends at the same vertex and repeats no other vertex.

Eulerian Trails And Circuits: Using Every Edge Exactly Once

1. An Eulerian trail is a trail that uses every edge of the graph exactly once.
2. An Eulerian circuit is an Eulerian trail that starts and ends at the same vertex.
3. This is the right idea for the gritting lorry or street sweeper that must drive along every road.
4. The degree of a vertex is the number of edge-ends meeting at it, and this single quantity decides whether these trails exist.
5. An Eulerian circuit exists exactly when the graph is connected and every vertex has even degree.
6. An open Eulerian trail exists exactly when the graph is connected and exactly two vertices have odd degree.
   1. Those two odd vertices must be the start and end of the trail.
   2. A connected graph can never have exactly one odd vertex, because all the degrees add up to an even number.

Hamiltonian Paths And Cycles: Visiting Every Vertex Exactly Once

1. A Hamiltonian path visits every vertex of the graph exactly once.
2. A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex.
3. This is the right idea for a driver who must call at every location once, not for one who must cover every road.
4. There is no simple degree test for whether a Hamiltonian path or cycle exists, unlike the Eulerian case.

Minimum Spanning Tree: Connecting Everything At Least Cost

1. A spanning tree is a set of edges that connects every vertex together with no cycles.
2. A minimum spanning tree (MST) is the spanning tree with the smallest possible total weight.
3. This answers the cabling question: link every house to the network using the least total length of cable.
4. A spanning tree on $n$ vertices always has exactly $n-1$ edges, which tells you when to stop.

Kruskal's Algorithm: Add Cheapest Edges, Skip Cycles

1. List every edge in order of increasing weight.
2. Add the next cheapest edge to your tree, provided it does not create a cycle.
3. If the next edge would create a cycle, reject it and move on.
4. Stop once you have $n-1$ edges, at which point every vertex is connected.

Prim's Algorithm From A Graph: Grow One Tree Outward

1. Start from any chosen vertex, which is your tree so far.
2. Look at every edge joining your tree to a vertex not yet in it.
3. Add the cheapest such edge together with its new vertex.
4. Repeat until all $n$ vertices are in the tree.

Prim's Algorithm From A Distance Matrix

1. A distance matrix stores the same graph as a table, where the entry in row $X$, column $Y$ is the weight of edge $XY$.
2. Prim's runs directly on the matrix by crossing out, which is convenient when a distance table is given.
   1. Choose a starting vertex and cross out its row.
   2. Look down every column whose vertex is already in the tree, over the rows not yet crossed out.
   3. Circle the smallest such entry, add that vertex, and cross out its row.
   4. Repeat until every row is crossed out; the circled entries are the MST edges.

The Chinese Postman Problem: Cover Every Road And Return

1. The Chinese postman problem asks for the shortest closed route that travels along every edge at least once and returns to the start.
2. It is exactly the gritting lorry, mail round, or bin lorry problem, where every road must be serviced.
3. If every vertex already has even degree, an Eulerian circuit exists and its length equals the total of all edge weights, which is the best possible.
4. If some vertices have odd degree, the route must repeat some edges, and the algorithm finds the cheapest repeats.
   1. Find every odd-degree vertex, noting there is always an even number of them.
   2. List all the ways to pair the odd vertices together.
   3. For each pairing, find the shortest path in the graph between the two vertices of each pair.
   4. Choose the pairing whose shortest paths have the smallest total, and repeat (duplicate) those paths.
   5. The shortest route length is the total of all edge weights plus that smallest repeat total.
      1. With two odd vertices there is only one pairing; with four odd vertices there are three possible pairings to compare.

Example question

The graph shown has edges $AB=4$, $AC=2$, $BC=3$, $BD=5$, $CD=3$, $CE=6$, $DE=4$. A road inspector must drive along every road and return to the start. Find the length of the shortest such route.

Solution

• Find the degrees $A:2$, $B:3$, $C:4$, $D:3$, $E:2$, so the odd-degree vertices are $B$ and $D$.
• With two odd vertices there is only one pairing, $(B,D)$.
• The shortest $B$ to $D$ path is the direct edge $BD=5$ (shorter than $B\to C\to D = 3+3 = 6$), so repeat $BD$.
• Total of all edge weights: $4+2+3+5+3+6+4=27$.
• Shortest route $= 27 + 5 = 32$.

Show answerHide answer

The Travelling Salesman Problem: The Shortest Round Trip Visiting All

1. The travelling salesman problem (TSP) asks for the shortest Hamiltonian cycle: a round trip that visits every vertex once and returns to the start.
2. This is the driver visiting every customer, or a machine drilling every hole on a board in the least time.
3. The classical problem assumes a complete graph, so you may travel directly between any two vertices.
4. The practical problem starts from a real network that may not be complete, and is first converted to a complete table of shortest distances before the algorithms are applied.
5. No efficient method is known to find the exact shortest cycle for large graphs, so instead the IB traps the true answer between two bounds.
   1. The nearest-neighbour algorithm gives an upper bound: a real route that can be beaten but is never shorter than the optimum.
   2. The deleted-vertex algorithm gives a lower bound: a value the optimum can never fall below.

Nearest-Neighbour Algorithm: An Upper Bound

1. Start at the given vertex.
2. Travel to the nearest unvisited vertex.
3. Repeat until every vertex has been visited.
4. Return directly to the starting vertex, then add up the edges used.
   1. The total is an upper bound because it is one genuine round trip, and the true optimum cannot be longer than an actual route.

Deleted-Vertex Algorithm: A Lower Bound

1. Delete one vertex and every edge attached to it.
2. Find a minimum spanning tree of the remaining vertices.
3. Add back the two cheapest edges from the deleted vertex to the rest.
4. The total weight of this MST plus two edges is a lower bound.
   1. It is a lower bound because any round trip, with one vertex removed, contains a spanning tree of the rest plus two edges back to the deleted vertex.

Reading The Question And Staying In Scope

1. Decide the problem type from the wording before choosing an algorithm.
   1. Every road, returning to start means Chinese postman.
   2. Every place once, returning to start, shortest means travelling salesman, so find both bounds.
   3. Connect everything cheapest means minimum spanning tree, using Kruskal's or Prim's.
2. State the certificate, not just the number: the edge order for an MST, the pairing for the postman, and the tour for the salesman.
3. Weights carry units, so round any final decimal answer to three significant figures and keep money to two decimal places.
4. Dijkstra's algorithm and the Floyd–Warshall algorithm are NOT part of the IB Mathematics AI guide, so treat them as enrichment only and never rely on them in an AI exam.
   1. The examinable algorithms here are Kruskal's, Prim's, the Chinese postman method, and the nearest-neighbour and deleted-vertex bounds for the travelling salesman.