Graph theory in HL AI: trees, paths and the Chinese postman problem

Graph theory in HL AI: trees, paths and the Chinese postman problem

My students in HL AI often find graph theory a fresh challenge. It is a topic that feels different from calculus or algebra, and for good reason. It’s a branch of discrete mathematics focused on relationships between objects. We use graphs to model connections: cities linked by roads, computers in a network, or tasks in a project. For HL AI students, graph theory is fundamental because it underpins many real-world optimization problems, decision-making algorithms, and even AI itself. Understanding how to build and analyze these models is a core skill I emphasize in my classroom.

In this article, I will explain some key graph theory concepts relevant to the IB HL AI course, focusing on trees, paths, and a classic problem: the Chinese Postman Problem. We will look at how these concepts are defined, how they are applied, and what you need to master for your exams. This is not just abstract math; these are tools you will use to solve practical problems.

What is a Graph? The Basics for HL AI

Before diving into specifics, let's establish what a graph is in this context. A graph $G = (V, E)$ consists of a set of vertices (or nodes) $V$ and a set of edges (or arcs) $E$ connecting pairs of vertices. In HL AI, we often deal with weighted graphs, where each edge has a numerical value, representing distance, time, cost, or capacity. We also distinguish between directed and undirected graphs. In an undirected graph, an edge between $A$ and $B$ means you can travel both ways. In a directed graph, an edge from $A$ to $B$ only allows travel from $A$ to $B$. For many problems in HL AI, like those involving shortest paths or minimum spanning trees, we primarily work with undirected graphs, though directed graphs come into play for flow problems or project management.

Understanding the terminology is crucial. A path is a sequence of distinct vertices connected by edges. The length of a path is the number of edges it contains, or its total weight if the graph is weighted. A cycle is a path that starts and ends at the same vertex, without repeating any other vertices. Connectivity is another key idea: a graph is connected if there is a path between every pair of vertices. These basic definitions form the bedrock of everything else we do in graph theory.

Trees and Minimum Spanning Trees

A tree is a specific type of graph that is connected and contains no cycles. Think of a branching structure, like a family tree or a decision tree. Each pair of vertices in a tree is connected by exactly one path. Trees are incredibly important in computer science and optimization. For example, they are used to model hierarchical structures, data storage, and network designs.

In HL AI, one of the most significant applications of trees is the concept of a Minimum Spanning Tree (MST). Given a weighted, connected graph, an MST is a subgraph that is a tree, connects all the vertices, and has the minimum possible total edge weight. Imagine you need to connect several towns with new fiber optic cables. You want to ensure every town is connected to the network, but you also want to minimize the total length (and thus cost) of the cables. This is precisely where an MST comes in.

My students learn two primary algorithms for finding an MST: Prim's algorithm and Kruskal's algorithm. Both are greedy algorithms, meaning they make the locally optimal choice at each step hoping to find a global optimum. For Prim's algorithm, you start from an arbitrary vertex and iteratively add the cheapest edge that connects a vertex in your growing tree to a vertex not yet in your tree, without forming a cycle. Kruskal's algorithm, on the other hand, sorts all edges by weight in ascending order and iteratively adds the next cheapest edge, as long as it does not form a cycle with the edges already chosen. Both algorithms guarantee finding an MST, and understanding their mechanics is essential for Paper 3 in HL AI.

Shortest Path Algorithms: Dijkstra and Bellman-Ford

Finding the shortest path between two vertices is a ubiquitous problem in graph theory. Think about GPS navigation, network routing, or even project scheduling. In HL AI, we focus on algorithms that efficiently solve this problem. The most famous is Dijkstra's algorithm. It finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. Dijkstra's algorithm works by maintaining a set of visited vertices and, at each step, selecting the unvisited vertex with the smallest known distance from the source, then updating the distances to its neighbors.

When edge weights can be negative, Dijkstra's algorithm fails. This is where the Bellman-Ford algorithm becomes necessary. While slower than Dijkstra's, Bellman-Ford can handle negative edge weights and can also detect negative cycles. A negative cycle is a cycle where the sum of its edge weights is negative. If a negative cycle is reachable from the source, the shortest path becomes undefined because you could traverse the cycle infinitely to decrease the total path length. My students need to understand both algorithms, their conditions for use, and their computational complexity.

The Chinese Postman Problem (CPP)

The Chinese Postman Problem, also known as the Route Inspection Problem, is a classic problem in graph theory that often appears in HL AI. It asks for the shortest closed walk (a path that starts and ends at the same vertex and can repeat edges and vertices) that traverses every edge of a connected graph at least once. Imagine a postman needing to deliver mail along every street in a neighborhood, starting and ending at the post office, minimizing the total distance walked. Or a snowplow needing to clear every road in a city.

The solution strategy for the CPP depends on the characteristics of the graph. If a graph is Eulerian (meaning all its vertices have an even degree), then an Eulerian circuit exists, and the shortest closed walk that traverses every edge exactly once is simply an Eulerian circuit. The total length is the sum of all edge weights. This is an ideal scenario.

However, real-world graphs rarely have all even degrees. If a graph has vertices with odd degrees, these must be "evened out." The key insight is that any optimal tour must traverse each odd-degree edge at least twice. To minimize the extra distance, we need to find pairs of odd-degree vertices and add "virtual" edges between them, which are duplicates of the shortest paths between those pairs. The sum of the weights of these shortest paths must be minimized. The problem then becomes finding a minimum weight perfect matching on the odd-degree vertices. This sounds complex, but it boils down to identifying all odd-degree vertices, finding the shortest path between all possible pairs of these odd vertices using an algorithm like Dijkstra's, and then finding a pairing of these odd vertices such that the sum of the shortest path weights is minimized. The final tour length is the sum of all original edge weights plus the sum of the weights of these added shortest paths.

This problem beautifully combines several graph theory concepts: identifying degrees, shortest path algorithms, and optimization. It's a challenging but rewarding problem to master for your HL AI revision.

Preparing for Graph Theory in IB HL AI

Graph theory demands precision and a systematic approach. For the IB HL AI exams, you need to not just know the definitions but also understand the algorithms inside out. This means being able to trace the steps of Prim's, Kruskal's, Dijkstra's, and Bellman-Ford on a given graph. Practice is paramount. Work through problems from past papers and textbook examples. Pay attention to graph representations (adjacency matrices vs. adjacency lists) and how they impact algorithm efficiency, though you typically won't be implementing them yourself in the exam.

My advice is to make sure you can explain why each algorithm works and under what conditions. For instance, why does Dijkstra's algorithm fail with negative weights? Why does Kruskal's algorithm work with disconnected components initially? These conceptual understandings often differentiate top scores. Graph theory is a practical field, so relate these problems back to real-world scenarios to solidify your understanding. It's not just about getting the right number; it's about the process and the underlying logic.

Graph theory, particularly for HL AI, is a significant topic that bridges mathematical theory with real-world applications in optimization and decision science. By focusing on the core definitions of graphs, understanding the properties of trees, mastering algorithms like Prim's, Kruskal's, Dijkstra's, and Bellman-Ford, and tackling complex problems like the Chinese Postman Problem, you will build a strong foundation. This area of mathematics not only prepares you for your IB exams but also equips you with powerful tools applicable in various fields, from logistics to network design. Keep practicing, drawing graphs, and critically analyzing each step of the algorithms.