Graph Theory and Matrix Methods (HL)

Networks are everywhere: roads between cities, connections between web pages, links in a supply chain. Graph theory studies these networks abstractly, and matrices give us a computational engine to analyze them — a distinctly applied, HL topic in IB AI.

Graphs, vertices, and edges

A graph consists of vertices (nodes) joined by edges. Edges may carry weights (distances, costs, times) and may be directed (one-way) or undirected. The degree of a vertex is the number of edges meeting it. Graphs model transport systems, social networks, and utility grids, where the questions of interest are connectivity, shortest routes, and efficient tours.

Adjacency matrices

For a graph with $n$ vertices, the adjacency matrix $M$ is an $n \times n$ array where entry $M_{ij}$ records the number of edges from v