IB Math AI: Algorithms and Graph Theory

Graph theory is the mathematics of connections, providing the language and tools to model everything from social networks and transportation grids to computer circuits and disease spread. For IB Math Applications and Interpretation, mastering its core algorithms transforms you from a passive observer into an active problem-solver, capable of optimizing logistics, designing efficient routes, and building resilient networks in real-world contexts.

Graph Theory Fundamentals: The Language of Networks

At its heart, a graph is a collection of points, called vertices (or nodes), connected by lines, called edges. This simple structure is incredibly powerful for abstraction. A vertex could represent a city, a person, or a computer; an edge could represent a road, a friendship, or a data cable. Graphs can be undirected, where edges have no orientation (like a two-way street), or directed (digraphs), where edges have a direction (like a one-way road). Edges may also have weights assigned to them, representing quantities like distance, cost, or time—these are weighted graphs.

Key properties immediately become relevant for analysis. The degree of a vertex is the number of edges incident to it. A path is a sequence of vertices where each consecutive pair is connected by an edge; a cycle is a path that starts and ends at the same vertex. A graph is connected if there is a path between every pair of vertices. Understanding this vocabulary is essential before applying algorithms, as the type of graph (weighted, unweighted, connected) dictates which tool you should use.

Representing Networks: The Adjacency Matrix

To analyze graphs computationally, we need a way to represent them in a structured format. The adjacency matrix is a square matrix that efficiently encodes connections. For a graph with $n$ vertices labeled $1,2,...,n$, the adjacency matrix $A$ is an $n\times n$ matrix where the entry $a_{ij}$ (row $i$, column $j$) represents the connection from vertex $i$ to vertex $j$.

In an unweighted graph, $a_{ij}=1$ if an edge exists from $i$ to $j$, and $0$ otherwise. For a weighted graph, $a_{ij}$ contains the weight of the edge, often using a special symbol (like $\infty$ or a dash) to denote no direct connection. For undirected graphs, the matrix is symmetric ($a_{ij}=a_{ji}$). Consider a simple network of three cities (A, B, C) with road distances: A to B is 5 km, A to C is 10 km, and B to C is 3 km. Its weighted adjacency matrix (with $\infty$ for no direct link) is:

$$\begin{array}{cccc}& A& B& C\\ A& \infty & 5& 10\\ B& 5& \infty & 3\\ C& 10& 3& \infty \end{array}$$

The power of an adjacency matrix lies in its utility for algorithmic computation. For instance, raising the matrix to the power $k$ ($A^k$) reveals the number of walks (paths allowing repeated vertices) of length $k$ between vertices in an unweighted graph.

Finding the Shortest Path: Dijkstra's Algorithm

A fundamental problem in logistics and routing is finding the shortest path between two vertices in a weighted graph, where all edge weights are non-negative. Dijkstra's algorithm solves this problem efficiently using a greedy approach—it always takes the next step that seems locally optimal.

The algorithm maintains a set of vertices whose shortest distance from the starting vertex (the source) is definitively known. It iteratively selects the unvisited vertex with the smallest tentative distance, updates the distances to its neighbors, and marks it as visited. This process repeats until the target vertex is visited or all reachable vertices are processed.

Step-by-step scenario: Find the shortest path from vertex A to D in the following network: A-B=4, A-C=2, B-C=1, B-D=5, C-D=8.

1. Label A with distance 0. Others get $\infty$.
2. Visit A. Update B to 4 (0+4) and C to 2 (0+2).
3. The smallest unvisited distance is C (2). Visit C. From C, B's current distance is 4, but via C it's 2+1=3. Update B to 3. Update D to 2+8=10.
4. Visit B (distance 3). From B, D's current distance is 10, but via B it's 3+5=8. Update D to 8.
5. Visit D. The shortest path from A to D is 8, and by backtracking, the path is A -> C -> B -> D.

This algorithm is crucial for applications like GPS navigation, network data packet routing, and designing efficient supply chains.

Connecting a Network Efficiently: Minimum Spanning Trees

Often, the goal is not to find a path between two points, but to connect all vertices in a network at the lowest total cost—for example, when laying fiber-optic cable to link a set of buildings. A spanning tree is a subgraph that includes all vertices of the original graph and is a tree (connected with no cycles). The Minimum Spanning Tree (MST) is the spanning tree with the smallest possible total edge weight.

Two primary algorithms find the MST: Kruskal's algorithm and Prim's algorithm. Both are greedy but operate differently.

Kruskal's Algorithm works by sorting all edges in the graph by ascending weight. It then iteratively adds the next smallest edge to the growing MST, but only if adding that edge does not create a cycle. You can manage cycle detection using a data structure that tracks which vertices are already connected. It's like building a network by always choosing the cheapest available connection, provided it doesn't form a redundant loop.

Prim's Algorithm starts from an arbitrary vertex and grows the MST one vertex at a time. At each step, it looks at all edges that connect vertices already in the tree to vertices not yet in the tree, and adds the cheapest such edge. This is similar to Dijkstra's but focused on edge weight to unconnected vertices, not total path distance from a source.

For a network of office buildings needing internet connections, both algorithms will yield an MST with the same minimum total cable length, though the actual set of edges may differ. Kruskal's is often easier to execute by hand for small graphs, while Prim's is more efficient for dense graphs in computational settings.

Common Pitfalls

1. Misapplying Dijkstra's Algorithm: Dijkstra's algorithm only works with non-negative edge weights. If a graph has negative weights (which can represent gains, like in certain financial networks), the algorithm can fail, producing incorrect results. In such cases, other algorithms like the Bellman-Ford algorithm are required. Always check the sign of weights first.

1. Confusing Shortest Path with Minimum Spanning Tree: A common conceptual error is to believe the MST contains the shortest paths between all pairs of vertices. It does not. The MST minimizes the total cost to connect all vertices, but the path between any two specific vertices in the MST may not be the shortest possible path between them in the original graph. They solve different optimization problems.

1. Incorrect Cycle Checking in Kruskal's Algorithm: When adding edges in Kruskal's, students sometimes forget to check for cycles rigorously. Adding an edge between two vertices that are already connected via some path in the current MST will always create a cycle. Systematically tracking connected components (e.g., by "shading" vertices) is essential to avoid this mistake.

1. Overlooking Graph Properties: Attempting to find an MST for a graph that is not connected is impossible, as a tree must connect all vertices. Similarly, applying an algorithm for weighted graphs to an unweighted one (or vice-versa) by incorrectly assuming all weights are 1 can lead to errors. Always state the type of graph you are working with at the outset.

Summary

• Graph theory provides a versatile framework for modeling interconnected systems using vertices and edges, which can be weighted, directed, or connected.
• The adjacency matrix is a powerful tool for representing graphs in a format suitable for computational analysis and for identifying network properties.
• Dijkstra's algorithm is the standard method for finding the single-source shortest path in a graph with non-negative edge weights, with direct applications in routing and logistics.
• The Minimum Spanning Tree (MST) problem is solved by Kruskal's and Prim's algorithms, which greedily select edges to connect all vertices at minimum total cost, crucial for network design and infrastructure planning.
• Success requires carefully matching the algorithm to the problem type (e.g., shortest path vs. MST) and the graph's properties (e.g., non-negative weights, connectivity).