Revise Graph theory: adjacency matrices and walks for IB Mathematics: Applications and Interpretation (3.7)

A graph is a set of vertices (also called nodes) together with a set of edges, each edge joining a pair of vertices. That is all a graph is; everything else is vocabulary for describing shapes and behaviour. The degree of a vertex is the number of edge-ends meeting there, which for a simple graph is just the number of edges attached to it. Edges may carry extra information: in a directed graph each edge has a direction, like a one-way street, so travel is only permitted along the arrow; in a weighted graph each edge carries a number such as a distance, time or cost.

A simple graph is undirected and unweighted, with no loops (an edge from a vertex to itself) and no repeated edges between the same pair of vertices; this is the commonest case in AI HL. A graph is connected when there is a walk between every pair of vertices, so the whole network hangs together in one piece. A subgraph is any graph you obtain by keeping some of the vertices and some of the edges of a larger graph. A tree is a connected graph with no cycles; a tree on $n$ vertices has exactly $n-1$ edges, which is why trees are the leanest way to keep a network connected.

The adjacency matrix $A$ of a graph with $n$ vertices is the $n \times n$ matrix whose entry $A_{ij}$ records the number of edges from vertex $i$ to vertex $j$. Label the rows and the columns with the vertices in the same order, then fill each cell. For a simple graph every entry is 0 or 1: a 1 where an edge exists and a 0 where it does not. The matrix is a complete, machine-readable copy of the graph, and its shape reveals the graph's nature at a glance.

For a graph with adjacency matrix $A$, the entry $A_{ij}$ is the number of edges directly joining vertex $i$ to vertex $j$, i.e. the number of walks of length 1 from $i$ to $j$.

A walk is a journey along the edges of a graph in which vertices and edges may be repeated; its length is the number of edges it uses. The adjacency matrix $A$ already counts walks of length 1, since $A_{ij}$ is the number of direct edges from $i$ to $j$. The central result of the topic extends this to any length: raising $A$ to the power $n$ counts walks of length $n$. The reason is exactly how matrix multiplication works. The $(i,j)$ entry of $A^2$ is $\sum_k A_{ik}A_{kj}$, a sum over every possible middle vertex $k$; each term counts the ways to step from $i$ to $k$ and then from $k$ to $j$, so the total is the number of two-step routes from $i$ to $j$. Repeating the argument gives every higher power.

The number of walks of length $n$ from vertex $i$ to vertex $j$ is the $(i,j)$ entry of $A^n$: $\text{(number of walks of length } n \text{ from } i \text{ to } j) = (A^n)_{ij}.$

Two consequences are worth stating outright. A diagonal entry $(A^n)_{ii}$ counts the closed walks of length $n$ that start and finish at vertex $i$. And to count walks of length at most $n$ you sum the powers: the relevant entry of $A + A^2 + \cdots + A^n$. Reading the wording of the question, an exact length or an at-most length, decides which matrix you need.

When edges carry numbers, a distance, a time, a price, the graph is stored in a weighted matrix, also called a cost matrix. Its $(i,j)$ entry is the weight of the edge from $i$ to $j$; where there is no direct edge the cell is left blank or marked with a dash (sometimes $\infty$), and the diagonal is usually 0. The crucial distinction from the adjacency matrix is this: to find the cost of a route you add the weights of the edges along it; you do not take powers of the cost matrix. Powers count walks only when the entries are 0s and 1s.

Every power in this topic should come from your calculator. Enter the matrix once into the matrix editor, giving it a name such as $A$, then compute $A^2$, $A^3$ and so on directly from the home screen, or form sums like $A + A^2 + A^3$ in one expression for an at-most-length question. Type the entries carefully, keep the vertex order identical to the one you are reading answers against, and copy the powered matrix onto your script before extracting the single entry you need. Because the arithmetic is exact (the entries are whole numbers), there is no rounding to worry about, only accurate entry and the right choice of entry to read.

On Paper 2 the marks are analytic: each is tied to a specific line of working, a method mark (M) for the right approach or an accuracy mark (A) for a correct result, and an accuracy mark depends on the method mark it follows. Follow-through (FT) means an earlier slip need not cost you the marks that build on it, provided the later step is carried out correctly on your own figures, so a candidate who computes $A^2$ with one wrong entry but then reads the correct position still earns the reading mark. The engine also accepts any equivalent correct form. That protection exists only if the method is written down. Study how each of the four marks below is earned by a specific line.

Adjacency matrices are the gateway to the rest of the graph-theory topic. The same 0/1 matrix, weighted with distances, feeds the shortest-path and minimum-spanning-tree algorithms of 3.8, where trees reappear as the cheapest way to connect a network. The idea that a matrix can be multiplied to advance a system by one step returns in transition matrices and Markov chains, where powers of a matrix push a probability distribution forward in time. Master the two moves here, translating a graph into a matrix and reading walks off its powers, and you have the core technique that the more advanced network mathematics is built upon.