Preview
IB DP Mathematics: Applications and Interpretation | HL | Geometry and Trigonometry — Graph Theory | Topic 3.15
📋 Learning Intentions
- Construct an adjacency matrix from a directed or undirected graph, correctly encoding edge connections as matrix entries.
- Calculate the number of walks of length \(k\) between any two vertices by computing the \(k\)-th power of an adjacency matrix using the GDC.
- Interpret entries in \(A^k\) as counts of distinct walks of exactly length \(k\) between pairs of vertices.
- Construct a transition matrix from a directed weighted graph or probability diagram, verifying that each column (or row) sums to 1.
- Apply repeated matrix multiplication to determine long-run state probabilities in a Markov chain context.
- Interpret the steady-state vector of a transition matrix in a real-world context such as market share or population movement.
Real-World Introduction
Every time a search engine ranks a webpage, it is performing a calculation on a matrix that encodes which pages link to which other pages. The number of ways to navigate from one page to another in exactly \(k\) clicks is precisely the entry in the \(k\)-th power of that graph's adjacency matrix. This is not a coincidence — it is the mathematical foundation of Google's original PageRank algorithm.
Transition matrices extend this idea by attaching probabilities to each connection. A customer switching between mobile phone providers, a molecule moving between energy states, or a population migrating between cities can all be modelled by a transition matrix. Multiplying the matrix by itself repeatedly reveals where the system will settle in the long run — the steady state.
🌐 Why This Matters Epidemiologists use transition matrices to model how individuals move between Susceptible, Infected, and Recovered states in disease spread models. The long-run behaviour of the matrix predicts whether a disease will die out or persist — a direct application of the mathematics in this topic.
Core Concepts & Definitions
A graph is a collection of vertices (nodes) connected by edges. To perform algebraic operations on a graph — such as counting paths or modelling probabilities — the graph must first be translated into a matrix. This translation is called the adjacency matrix.
📖 Key Definition — Adjacency Matrix For a graph \(G\) with \(n\) vertices labelled \(1, 2, \ldots, n\), the adjacency matrix \(A\) is the \(n \times n\) matrix where: \[ A_{ij} = \begin{cases} 1 & \text{if there is an edge from vertex } i \text{ to vertex } j \\ 0 & \text{otherwise} \end{cases} \] For an undirected graph, \(A\) is symmetric: \(A_{ij} = A_{ji}\). For a directed graph (digraph), \(A_{ij}\) records an edge from \(i\) to \(j\), and \(A_{ji}\) records the reverse direction separately.
The adjacency matrix is read row-by-row: row \(i\) tells you which vertices vertex \(i\) connects to. A 1 in position \((i,j)\) means "there is a direct edge from \(i\) to \(j\)." A 0 means no direct edge. Self-loops (edges from a vertex to itself) appear on the main diagonal; in most IB problems, self-loops are absent so the diagonal is zero.