IB Maths AI 3.12 Notes

Adjacency matrices

In this section, we represent graphs using matrices. This gives a neat algebraic way to describe connections in a network and allows us to answer questions about walks, weights, and transitions.

An adjacency matrix records which vertices are connected in a graph. Suppose a graph has vertices listed in the order $A$, $B$, $C$, $D$. The adjacency matrix $A$ is formed by letting the entry in row $i$ and column $j$ show whether vertex $i$ is joined to vertex $j$.

For a simple unweighted graph:

• put $1$ if there is an edge
• put $0$ if there is no edge

For an undirected graph, the adjacency matrix is symmetric because connections work both ways. For example, suppose the graph has edges $AB$, $AC$, $BC$, and $CD$.

Using the order $A$, $B$, $C$, $D$, the adjacency matrix is $A=\begin{pmatrix}0&&1&&1&&0\\1&&0&&1&&0\\1&&1&&0&&1\\0&&0&&1&&0\end{pmatrix}$.

The diagonal entries are $0$ because there are no loops.