Home / IB DP Maths / Application and Interpretation HL / IB Mathematics AI AHL Walks, trails, paths, circuits, cycles MAI Study Notes – New Syllabus

IB Mathematics AI AHL Walks, trails, paths, circuits, cycles MAI Study Notes - New Syllabus

IB Mathematics AI AHL Walks, trails, paths, circuits, cycles MAI Study Notes

LEARNING OBJECTIVE

  • Tree and cycle algorithms with undirected graphs. Walks, trails, paths, circuits, cycles

Key Concepts: 

  • Walks
  • Chinese Postman Problem
  • Travelling Salesman Problem
  • Bounds for Travelling Salesman Problem

MAI HL and SL Notes – All topics

ROUTES ON THE GRAPH

ROUTES ON THE GRAPH

Path: no vertex is revisited: e.g. ABC or AECD
Trail: no edge is revisited: e.g. AEBCED or BECBA
Walk: Walk as you wish, e.g. ABCBEC or ABAE

a path from X to Y looks like

a trail from X to Y looks like

Cycle: derived from a path which closes to the initial vertex e.g. ABEA or EBCDE (only the first vertex is revisited)
Circuit: a trail which closes to the initial vertex, e.g. AEDCEBA

(a walk which closes to the initial vertex is nothing more than a walk which closes to the initial vertex\! e.g. ABABABA)

The number of edges on a path, trail or walk is called length.
For example:

AB is a path of length 1 (just an edge)
ABC is a path of length 2.
AEBCED is a trail of length 5.
ABABABA is a walk of length 6 [one less than the number of vertices listed].

Eulerian Graphs

Eulerian Trail

  • A trail that uses every edge exactly once.
  • May start and end at different vertices.
  • Also known as a semi-Eulerian trail.

Eulerian Circuit

  • A closed trail that uses every edge exactly once and returns to the starting vertex.
  • Also known as a Eulerian cycle.

Procedure to Classify a Graph

The graph is Eulerian if and only if all vertices have even degrees

The graph is semi-Eulerian if and only if all vertices, except two vertices X and Y, have even degrees.
The vertices X and Y have odd degrees (we call them odd vertices) and the trail has to start from X and finish at Y or vice versa

  

In the first graph(Semi-Eulerian Graph), only A and B have odd degrees (odd vertices). That is why the trail has to start from A and finish at B

In the second graph(Semi-Eulerian Graph) all vertices have even degrees.

Hamiltonian Paths and Cycles

Hamiltonian Cycle

  • A cycle that visits every vertex exactly once and returns to the starting vertex.
  • The graph is called Hamiltonian if such a cycle exists.

For the first one a Hamiltonian cycle is ABCEDA
For the second one a Hamiltonian cycle is ADECBFA

Hamiltonian Path

  • A path that visits every vertex exactly once but does not return to the starting vertex.
  • The graph has a Hamiltonian path even if it is not Hamiltonian (i.e., no cycle exists).

The graph is not Hamiltonian  We can visit though all vertices by a path: ECBAD Such a path is called Hamiltonian path.

 Properties

  • A Hamiltonian cycle in a graph with n vertices has length n.
  • Hamiltonian graphs may contain multiple Hamiltonian cycles and paths.

Minimum Spanning Tree (MST)

Minimum Spanning Tree (MST)

  • A spanning tree is a subgraph that includes all vertices of the graph and is a tree (no cycles).
  • A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.
  • There can be more than one MST if multiple trees have the same total weight.
  • Applications include network design (e.g., computer networks, road networks).

Example

If a weighted graph has four spanning trees

▶️Answer/Explanation

Solution:

The MST is the one with total weight = 9

Kruskal’s Algorithm

Kruskal’s algorithm builds the MST by choosing edges in order of increasing weight:

  • Sort all edges in ascending order of weight.
  • Select the smallest edge. Add it to the MST if it doesn’t form a cycle.
  • Repeat step 2 until the MST contains exactly n−1 edges (where n is the number of vertices).

Note:

  • Use a cycle-checking method like Union-Find (Disjoint Set).
  • If multiple edges have the same weight, choose any (randomly or by rule).

Example

Apply Kruskal’s algorithm on the following graph

▶️Answer/Explanation

Solution:

We have 5 vertices, we need \(n-1 = 4\) edges

The minimum spanning tree is


It has total weight \(28\).

Prim’s Algorithm

Prim’s algorithm builds the MST by growing a tree starting from an arbitrary vertex:

  • Start from any vertex.
  • Add the nearest vertex (with the smallest connecting edge) that is not already in the tree.
  • Repeat step 2 until all vertices are included.

Note:

  • Often implemented efficiently using a priority queue (min-heap).
  • Like Kruskal’s, if there’s a tie, choose any edge.

Example

Apply Prim’s algorithm on the following graph

▶️Answer/Explanation

Solution:

We have 5 vertices; we have to join all of them
Let us start from C. The tree now contains only C

The minimum spanning tree is as in example 1.
Total weight = \(9+7+5+7 = 28\)

Chinese Postman Problem

Chinese Postman Problem

The goal is to find the shortest closed walk that traverses every edge at least once and returns to the starting point on a weighted graph (where):

  • Edges represent roads
  • Vertices represent junctions/crossroads
  • The postman wants to deliver mail by covering all roads with minimum total distance

Case 1: Eulerian Graph

All vertices have even degree.

  • A Eulerian circuit (a closed path visiting every edge exactly once).
  • Minimum cost = Total weight of all edges

 Case 2: Semi-Eulerian Graph (2 Odd Vertices)

Exactly two vertices have odd degree (say, X and Y).

 Find the shortest path from X to Y with weight a.

  • A Eulerian trail from X to Y
  • Plus a shortcut (duplicate) from Y to X along the shortest path
  • Minimum cost = Total weight + a

Case 3: 4 Odd Vertices (X, Y, Z, W)

Choose the best pairing of odd vertices such that the total added weight is minimized.

Compute shortest path weights:

X–Y and Z–W: weights a, b

X–Z and Y–W: weights c, d

X–W and Y–Z: weights e, f

  • Pick the pairing with the smallest total (e.g. a + b)
  • Add duplicate/fake edges for these two paths (X–Y and Z–W)
  • The graph becomes Eulerian
  • Find a Eulerian circuit, and when reaching X or Z, follow the duplicated path

Minimum cost = Total weight + (a + b)

Example

Solve the following Chinese postman problem.

▶️Answer/Explanation

Solution:

All vertices have even degree, so the graph is Eulerian.
Thus, the best solution has
total weight = (sum of weights) $= 45$
If we start from A, a possible route is $\rm{ABCDFEDBEA}$

Example

Solve the following Chinese postman problem.

 

▶️Answer/Explanation

Solution:

There are exactly two odd vertices: E (degree 3) and D (degree 3)
(so the graph is semi-Eulerian).
The shortest path from E to D is EBD of total weight 9.
Thus, the best solution has
$\text{total weight = (sum of weights) + 9 = 41 + 9 = 50}$
If we start from A, a possible route is $\rm{ABCDEBDBEA}$

Nearest Neighbor Algorithm (Upper Bound)

This algorithm builds a tour by always going to the nearest unvisited vertex.

 Steps:

  1. Start from any vertex.
  2. Go to the nearest unvisited vertex.
  3. Repeat step 2 until all vertices are visited.
  4. Return to the starting vertex.

 Result:

  • Gives a Hamiltonian cycle
  • Provides an upper bound on the minimum possible distance

Example:

Start at A
→ Closest vertex: B
→ Next closest: C
→ until all are visited
→ Return to A

Upper Bound = Total distance of this tour

 Deleted Vertex Algorithm (Lower Bound)

This is a way to estimate the minimum possible length of a TSP tour — a lower bound, not an actual tour.

 Steps:

  1. Pick a vertex to delete (commonly the starting vertex).
  2. Find a Minimum Spanning Tree (MST) on the remaining vertices.
  3. Add the two smallest edges connecting the deleted vertex to the rest.
  4. These simulate entering and exiting that vertex.
  5. Lower Bound = Weight of MST + weight of 2 shortest connecting edges

 Why this works:

  • Any valid Hamiltonian cycle must connect the deleted vertex to the rest of the graph at least twice, and contain at least an MST for the rest.
  • So this sum gives a minimum possible total.
Scroll to Top