IB AI: Network and Graph Theory

Network and graph theory is the mathematical backbone behind everything from GPS navigation and social media connections to logistics and circuit design. In IB AI, you learn to model messy real-world systems as clean mathematical structures, unlocking the power to solve complex optimization problems—finding the cheapest, fastest, or most efficient routes through interconnected systems.

Foundational Concepts: The Language of Graphs

At its core, a graph is a collection of points and lines connecting them. The points are called vertices (or nodes), and the lines are called edges (or arcs). This simple structure is incredibly powerful for modeling relationships. For instance, vertices could represent cities, and edges could represent roads between them.

The degree of a vertex is the number of edges incident to it. In a graph modeling a social network, a person's degree represents their number of direct friends. A key tool for representing graphs computationally is the adjacency matrix. This is a square matrix where the entry in row $i$ and column $j$ is 1 if there is an edge from vertex $i$ to vertex $j$, and 0 otherwise. For an undirected graph, this matrix will be symmetrical.

Many real-world problems require more detail than simple connections. A weighted graph assigns a numerical value (a weight) to each edge. These weights can represent distance, cost, time, or capacity. The graph of cities and roads becomes a weighted graph when we label each road with its travel time or distance, which is essential for optimization.

Optimization Algorithms: Finding the Best Paths and Trees

Given a connected weighted graph, a common problem is to find the minimum spanning tree (MST). This is a subset of the edges that connects all vertices together without any cycles and with the minimum possible total edge weight. Imagine you're an engineer tasked with connecting all houses in a new neighborhood to the electrical grid using the least amount of cable; you need an MST.

Two primary algorithms solve this:

• Kruskal's Algorithm: This is a "greedy" algorithm. You start by sorting all edges from lowest to highest weight. Then, you add edges one by one to the growing MST, but you skip any edge that would create a cycle. You continue until all vertices are connected.
• Prim's Algorithm: Also greedy, this algorithm grows the MST from a single starting vertex. At each step, you look at all edges that connect a vertex in the growing tree to a vertex not yet in it, and you add the cheapest such edge. This repeats until the tree spans all vertices.

For finding the shortest path between two specific vertices, you use Dijkstra's algorithm. This algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph (with non-negative weights). It works by iteratively selecting the unvisited vertex with the smallest known distance from the source, updating the distances to its neighbors, and marking it as visited. If you only need the path to one target, you can stop once that vertex is marked as visited. This is precisely how digital mapping software calculates your fastest driving route.

Classic Routing Problems: The Chinese Postman and Traveling Salesman

Some of the most famous problems in graph theory involve designing efficient routes. These are categorized as Chinese postman and traveling salesman problems.

The Chinese Postman Problem (CPP), or Route Inspection Problem, asks: "Starting and ending at the same vertex, what is the shortest closed route that traverses every edge in the graph at least once?" This models a postal worker delivering mail to every street. The solution involves finding a way to pair up vertices of odd degree (by duplicating existing edges) so that the graph becomes Eulerian (all vertices have even degree, allowing a single closed trail that uses every edge exactly once). The total weight of the edges you duplicate must be minimized.

In contrast, the Traveling Salesman Problem (TSP) asks: "Starting and ending at the same vertex, what is the shortest closed route that visits every vertex in the graph exactly once?" This models a salesperson visiting a list of cities. The TSP is notoriously difficult (NP-hard). For the IB, you typically encounter it in its Hamiltonian cycle form on small graphs, where you might find the minimum weight cycle by inspection or simple algorithms, or apply a nearest-neighbor heuristic for larger problems—a greedy approach that is fast but doesn't guarantee the optimal solution.

Common Pitfalls

1. Confusing Edges for Paths: An edge is a direct connection. A path is a sequence of edges. A common mistake is to assume you can travel directly between any two vertices. Always check the adjacency matrix or graph diagram to see if a direct edge exists.
2. Misapplying Dijkstra's Algorithm: Dijkstra's algorithm fails if the graph has negative edge weights, as it can trap the algorithm in a cycle that appears to lower the cost indefinitely. For graphs with possible negative weights, other algorithms like Bellman-Ford are required.
3. Mixing Up MST and Shortest Path: The minimum spanning tree minimizes the total cost to connect all vertices, but the path between two specific vertices within the MST is not necessarily the shortest path between them in the original graph. These are different optimization goals.
4. Overlooking Graph Type in Routing Problems: Applying TSP logic to a CPP scenario, or vice versa, is a critical error. Remember: Postman = cover every edge. Salesman = visit every vertex.

Summary

• Graphs model relationships using vertices and edges. An adjacency matrix provides a computational representation, and weighted graphs assign values to edges for modeling real-world costs.
• Kruskal's and Prim's algorithms find the Minimum Spanning Tree—the cheapest way to connect all vertices in a network without cycles.
• Dijkstra's algorithm efficiently finds the shortest path from a single source vertex to all others in a graph with non-negative weights.
• The Chinese Postman Problem seeks the shortest route covering every edge, solved by making the graph Eulerian. The Traveling Salesman Problem seeks the shortest route visiting every vertex exactly once and is typically solved with heuristics for non-trivial cases.
• Success in this topic requires careful attention to the type of graph, the specific optimization goal, and the assumptions underlying each algorithm.