Graph algorithms AI HL

IB Mathematics: Applications and Interpretation HL · Unit 3

Lesson 3.16 · Graph Algorithms

Use graph algorithms to find routes, test whether journeys are possible, and design efficient networks.

Praising God for his saving work

Psalm 9:1 — “I will give thanks to the Lord with my whole heart; I will recount all of your wonderful deeds.”

Psalm 66:16 — “Come and hear, all you who fear God, and I will tell what he has done for my soul.”

Psalm 116:13 — “I will lift up the cup of salvation and praise the LORD’s name for saving me.”

As we finish this chapter, we praise God for the wonderful work he has done to bring the lost to himself. Jesus Christ died for our sins, and through his blood we are forgiven and welcomed as God’s children. Salvation is a gift of grace. May we remember what the Lord has done for our souls and share this good news with gratitude.

Learning objectives

By the end of this lesson, you should be able to:

distinguish between walks, trails, paths, circuits and cycles;
use vertex degrees to decide whether an Eulerian trail or circuit exists;
recognise Eulerian and Hamiltonian paths and cycles;
apply Kruskal’s and Prim’s algorithms to find a minimum spanning tree;
explain how to solve the Chinese postman problem; and
use nearest neighbour and deleted vertex methods for the travelling salesperson problem.

1. Trees, cycles and route vocabulary

A tree is a connected graph with no cycles. A tree with n vertices has exactly n − 1 edges. A spanning tree connects every vertex of a graph without creating a cycle.

A cycle is a closed path: it starts and finishes at the same vertex, with no other vertex repeated.

Term	Meaning	Can vertices repeat?	Can edges repeat?
Walk	A sequence of vertices joined by edges	Yes	Yes
Trail	A walk with no repeated edges	Yes	No
Path	A walk with no repeated vertices	No	No
Circuit	A closed trail	Yes, the start is also the end	No
Cycle	A closed path	Only the start/end vertex repeats	No

Remember: A tree connects all its vertices without a cycle. A cycle is a closed route with no repeated vertices apart from the start/end.

2. Eulerian trails and circuits

An Eulerian trail uses every edge exactly once. An Eulerian circuit uses every edge exactly once and returns to its starting vertex.

The degree of a vertex is the number of edges meeting at that vertex. For a connected graph:

if every vertex has even degree, an Eulerian circuit exists;
if exactly two vertices have odd degree, an Eulerian trail exists, starting at one odd-degree vertex and ending at the other;
if more than two vertices have odd degree, there is no Eulerian trail.

Worked example · Testing for an Eulerian trail

A connected graph has vertex degrees 2, 4, 3, 3 and 2. Decide whether it has an Eulerian trail or circuit.

There are exactly two odd-degree vertices, both of degree 3. Therefore the graph has an Eulerian trail, but no Eulerian circuit. The trail must start at one odd-degree vertex and end at the other.

Check: The number of odd-degree vertices in a graph is always even. For an Eulerian route, all vertices connected by edges must belong to one connected component.

3. Hamiltonian paths and cycles

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to its starting vertex.

Eulerian routes focus on edges; Hamiltonian routes focus on vertices. There is no simple degree test that determines whether every graph has a Hamiltonian cycle, so possible routes may need to be checked systematically.

$\boxed{\text{Euler: every edge once}} \qquad \boxed{\text{Hamilton: every vertex once}}$

4. Minimum spanning trees

A minimum spanning tree (MST) connects all vertices with the least possible total edge weight. It has exactly n − 1 edges. MSTs model low-cost networks such as power lines, roads or communication links.

An MST minimises the cost of the network. It does not necessarily give the shortest route between two particular vertices.

Kruskal’s algorithm

List all edges in increasing order of weight.
Select the smallest edge that does not create a cycle.
Continue until all vertices are connected by n − 1 edges.

Worked example · Kruskal’s algorithm

Consider a graph with the following weighted edges:

Edge	AB	BC	AC	CD	BD	DE	CE
Weight	1	2	3	4	5	6	7

Select AB (1) and BC (2). Skip AC (3), because it would form the cycle A–B–C–A. Select CD (4), skip BD (5) because it would create a cycle, and select DE (6).

$\text{MST weight}=1+2+4+6=\boxed{13}$

Prim’s algorithm

Start at the given vertex.
Choose the smallest-weight edge joining a vertex in the growing tree to a vertex outside it.
Repeat until all vertices are included.

Worked example · Prim’s algorithm

Using the same graph, start at A. Choose AB (1), then BC (2), then CD (4), and finally DE (6). The MST has total weight 13.

Do not select an edge joining two vertices already in the tree, since that would create a cycle.

5. The Chinese postman problem

The Chinese postman problem asks for the shortest closed route that traverses every edge of a connected weighted graph at least once. It can represent a postal route, street sweeping or snowploughing.

If every vertex has even degree, use an Eulerian circuit. Every edge is traversed once.
If there are odd-degree vertices, find the shortest paths between them.
Pair the odd vertices so that the total weight of the paths selected is as small as possible.
Repeat the edges in those paths. The resulting graph has even degrees, so an Eulerian circuit can be used.

Worked example · Why repeat edges?

A connected network has four odd-degree vertices. To make a closed route covering every edge, pair the odd vertices using shortest paths. Choose the pairing with the smallest combined path length, then repeat those path edges.

Repeating the selected edges changes the odd degrees to even degrees. The route can then travel every edge and return to its starting point.

6. The travelling salesperson problem

The travelling salesperson problem (TSP) asks for the minimum-weight Hamiltonian cycle in a weighted complete graph: visit every vertex once, return to the start, and minimise the total weight.

Nearest neighbour algorithm · Upper bound

Choose a starting vertex.
Travel to the nearest unvisited vertex.
Repeat until every vertex has been visited.
Return to the starting vertex.

The route found is a valid Hamiltonian cycle, so its length is an upper bound for the optimal TSP route. The answer can depend on the starting vertex, so try different starting points when asked for the best nearest-neighbour route.

Deleted vertex algorithm · Lower bound

Delete one vertex and all its incident edges.
Find a minimum spanning tree for the remaining vertices.
Add the two smallest edges that connect the deleted vertex to the remaining graph.
The total gives a lower bound for the shortest Hamiltonian cycle.

Every TSP cycle must connect the deleted vertex to the rest of the graph twice. Once that vertex is removed, the remaining edges must still connect all the other vertices, so their total weight cannot be less than the MST weight.

Worked example · Interpreting TSP bounds

Suppose the deleted vertex method gives a lower bound of 18, and a nearest-neighbour route has length 21. Then the optimal route length, $L$ , satisfies:

$\boxed{18\leq L\leq21}$

The optimal cycle is at least 18 units long and no longer than the valid 21-unit route.

7. Which algorithm should I use?

Problem	Method	What is being considered?
Use every edge exactly once	Eulerian trail/circuit test	Edges
Visit every vertex once	Hamiltonian path/cycle	Vertices
Connect all vertices at minimum cost	Kruskal’s or Prim’s algorithm	Network edges
Shortest closed route covering every edge	Chinese postman algorithm	Every edge at least once
Shortest round trip visiting every vertex once	TSP algorithms	Hamiltonian cycles

IB-style practice

A connected graph has six vertices of even degree and two vertices of odd degree. State whether it has an Eulerian trail, an Eulerian circuit, both or neither. [2 marks]
Explain the difference between an Eulerian circuit and a Hamiltonian cycle. [2 marks]
In Kruskal’s algorithm, why might you reject the next smallest edge? [2 marks]
A nearest-neighbour TSP route has length 42 km. State what this tells you about the optimal route length. [2 marks]
Explain why edges are repeated in the Chinese postman problem when a graph has odd-degree vertices. [3 marks]

Show suggested answers

It has an Eulerian trail but not an Eulerian circuit. There are exactly two odd-degree vertices.
An Eulerian circuit uses every edge exactly once and returns to its start. A Hamiltonian cycle visits every vertex exactly once and returns to its start.
Reject the edge if it creates a cycle among vertices already connected in the growing tree.
The optimal TSP route is at most 42 km, so 42 km is an upper bound.
Repeating selected shortest-path edges changes all odd-degree vertices to even degree, allowing a closed Eulerian circuit to traverse every edge.

Reflection · Remembering what God has done

As we complete this chapter, let us praise God with our whole hearts for his wonderful deeds. Through the death of Jesus Christ, God has made a way for the lost to be brought near. Jesus died for our sins, and through his blood we are forgiven and made his children. This is the great work of salvation that we remember with thankfulness.

May we tell others what God has done for our souls and lift up the cup of salvation with praise. As we have studied paths and connections in graph theory, may we remember with gratitude the way God has opened for us through Jesus Christ.