Graph theory and network algorithms (HL)

Introduction to Graph Theory

Welcome to one of the most practical chapters in the HL syllabus! While most of geometry is about shapes and angles, Graph Theory is about connections. Think of a map of the London Underground, a social media network, or the routing of your latest Amazon delivery. These are all "graphs." In this chapter, we will learn how to describe these networks and, more importantly, how to use algorithms to find the most efficient way to navigate them.

3.14 The Anatomy of a Graph

Before we can solve complex delivery problems, we need to speak the language of graphs. A graph consists of vertices (points) and edges (lines connecting the points).

Key Definitions:
Adjacency: Two vertices are "adjacent" if they are connected by an edge.
Degree: The number of edges connected to a vertex. For example, if a vertex \( V \) has three lines coming out of it, its degree is \( deg(V) = 3 \).
Simple Graph: A graph with no loops (an edge connecting a vertex to itself) and no multiple edges between the same two vertices.
Complete Graph \( K_n \): A graph where every vertex is connected to every other vertex. If there are \( n \) vertices, it is called \( K_n \).
Weighted Graph: A graph where each edge has a "weight" assigned to it, representing cost, distance, or time.
Subgraphs: A smaller part of a graph (using some of the vertices and edges from the original).
Trees: A very special type of graph that is connected but has no cycles (no loops or closed circuits). If a tree has \( n \) vertices, it must have exactly \( n - 1 \) edges.

Directed Graphs (Digraphs):
Sometimes connections only go one way (like a one-way street). We use arrows instead of lines. In these graphs, we talk about:
In-degree: Number of arrows pointing into the vertex.
Out-degree: Number of arrows pointing out of the vertex.

3.15 Matrices and Walks

We can represent a graph using a table of numbers called an Adjacency Matrix. This allows us to use our GDC to solve network problems quickly!

The Adjacency Matrix \( A \):
In a matrix \( A \), the entry in row \( i \), column \( j \) tells you how many edges connect vertex \( i \) to vertex \( j \). For a simple graph, these entries are either 0 or 1.

Finding Walks with \( A^k \):
A walk is just a sequence of vertices and edges. If you want to know how many different ways you can get from vertex \( i \) to vertex \( j \) using exactly \( k \) edges, you simply calculate the matrix \( A^k \) on your calculator. The value in row \( i \), column \( j \) of the new matrix is your answer!

Did you know? This is how early search engine algorithms started to rank the importance of webpages—by looking at how many "walks" led to a specific page.

Transition Matrices:
In a strongly connected graph (where you can get from any vertex to any other vertex following the arrows), we can create a transition matrix. This links graph theory to Topic 4: Probability and Markov Chains. Each entry represents the probability of moving from one vertex to the next.

3.16 Navigating the Graph: Routes and Cycles

When moving through a graph, the IB uses very specific words. It is vital to learn the difference!

Walk: The most general term. You can repeat edges and vertices.
Trail: A walk where no edges are repeated.
Path: A walk where no vertices are repeated (which means no edges are repeated either).
Circuit: A trail that starts and ends at the same vertex (no edges repeated).
Cycle: A path that starts and ends at the same vertex (no vertices repeated, except the start/end).

Eulerian Trails and Circuits (Focus on EDGES)

Named after Leonhard Euler, who wanted to cross every bridge in a city exactly once.
Eulerian Circuit: Uses every edge exactly once and returns to the start. This is only possible if every vertex has an even degree.
Eulerian Trail: Uses every edge exactly once but starts and ends at different places. This is only possible if exactly two vertices have an odd degree (you start at one odd vertex and end at the other).

Hamiltonian Paths and Cycles (Focus on VERTICES)

Named after William Rowan Hamilton, who wanted to visit every city exactly once.
Hamiltonian Cycle: A cycle that visits every vertex exactly once and returns to the start. Unlike Eulerian circuits, there is no simple rule about degrees to find these; you usually have to find them by inspection (looking at the graph).

Minimum Spanning Trees (MST)

Imagine you want to connect several houses with fiber-optic cable using the minimum amount of cable. You need a Minimum Spanning Tree. There are two main algorithms to find this:

1. Kruskal’s Algorithm (The "Shortest Edge" method):
- List all edges in order of weight (smallest to largest).
- Keep picking the shortest edge available unless it creates a cycle.
- Stop when all vertices are connected.

2. Prim’s Algorithm (The "Growing Tree" method):
- Start at any vertex.
- Look at all edges connected to the vertices you already have.
- Pick the shortest one that connects to a new vertex.
- Repeat until all vertices are in the tree.
Tip: You can do this using a weighted adjacency table by crossing out rows and looking for the minimum in columns!

Optimization Problems

The Chinese Postman Problem (Route Inspection)

A postman must travel along every edge at least once. We want the total weight to be as small as possible.
- If all vertices are even: The answer is just the sum of all edge weights.
- If two vertices are odd: You must repeat the shortest path between those two odd vertices.
- The HL Limit: If there are four odd vertices (the maximum for this syllabus), you must pair them up. If the odd vertices are \( A, B, C, D \), you test three pairings: \( (AB + CD) \), \( (AC + BD) \), and \( (AD + BC) \). Choose the pairing with the smallest total and add that to the sum of all edges.

The Travelling Salesman Problem (TSP)

A salesman wants to visit every vertex and return home, minimizing the distance. This is much harder than the Postman problem! We look for bounds:

Upper Bound (UB): This is a "good enough" route. Use the Nearest Neighbour Algorithm. Start at a vertex, always go to the closest unvisited vertex, and finally return to the start. Note: Different starting vertices might give different Upper Bounds!

Lower Bound (LB): This is a value that the best route cannot be shorter than. It is usually not a valid route itself. Use the Deleted Vertex Algorithm:
1. Delete one vertex and all edges connected to it.
2. Find the MST for the remaining vertices.
3. Add the two shortest edges that were connected to the deleted vertex.
4. The result is your Lower Bound.

Quick Summary:
MST: Connects everyone cheaply (Kruskal/Prim).
Chinese Postman: Covers every street (edges).
TSP: Visits every house (vertices).

Common Mistake: In the Chinese Postman Problem, students often forget to add the original sum of all edges to the "repeated" edges. Don't let that be you!