A graph stored as a grid of numbers: Picture four towns A, B, C, D joined by roads. Instead of drawing them, store the connections in a square grid — the adjacency matrix A.
The rows and columns are labelled with the same vertices in the same order. Entry in row i, column j is the number of edges going from vertex i to vertex j (usually 0 or 1).
Why bother? Once the network is a matrix, a GDC can do all the route-counting for you — no more tracing paths by hand.
Undirected vs directed — symmetry is the tell: Undirected graph (roads you can drive both ways): an edge between A and B puts a 1 in both position (A,B) and (B,A), so the matrix is symmetric (a mirror image across the diagonal).
Directed graph (one-way streets, web links): an arrow A→B puts a 1 in (A,B) only. The matrix is usually not symmetric.
Loops (an edge from a vertex to itself) sit on the diagonal; in an undirected graph a loop is often counted as 2.
IB-style question — write down an adjacency matrix
A small delivery network of four depots A, B, C, D has two-way roads: A–B, A–C, B–C and C–D.
Write down the adjacency matrix, taking the vertices in the order A, B, C, D.
Step by step
- Two-way roads → undirected → symmetric matrix. Put a 1 in each direction of every road, 0 everywhere else (no loops here, so the diagonal is 0).
- Fill row by row. Row A connects to B and C; row B to A and C; row C to A, B and D; row D to C.
- Sanity check: it is symmetric (mirror across the diagonal), as every undirected adjacency matrix must be. The row sums (2, 2, 3, 1) are the degrees of A, B, C, D.
Final answer
M = ((0,1,1,0),(1,0,1,0),(1,1,0,1),(0,0,1,0)). It is symmetric because the roads are two-way.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Aⁿ counts the walks of length n: Here is the result the exam tests again and again:
the entry in row i, column j of Aⁿ is the number of walks of length n (n edges, repeats allowed) from vertex i to vertex j.
A walk is any sequence of edges followed end to end — you may reuse vertices and edges. "Length" means the number of edges used, not the distance.
So A² counts 2-step routes, A³ counts 3-step routes, and so on. A GDC raises a matrix to a power instantly, so these questions are pure calculator work once you have A.
Why does this work? (the row × column picture): To get from i to j in 2 steps you go i → (some middle vertex k) → j. The (i,j) entry of A² is the row-i × column-j dot product: it adds, over every k, (edges i→k) × (edges k→j). That product is 1 exactly when both legs exist, so the sum literally counts the 2-step routes.
A³ = A²·A then glues a third edge on, and the pattern continues — each extra power adds one more edge to the walk.
IB-style question — count walks of a given length
For the depot network M = ((0,1,1,0),(1,0,1,0),(1,1,0,1),(0,0,1,0)) (vertices A, B, C, D), use a GDC to find the number of walks of length 3 that start at A and end at D.
Step by step
- Walks of length 3 → use M³. Enter M into the GDC and compute the cube.
- Read the entry for 'start A, end D' — that is row A (row 1), column D (column 4).
- Interpret it: there is exactly one 3-edge walk from A to D. (It is A → C → C? no loops, so it is A → B → C → D, the only such route.)
Final answer
1 walk of length 3 from A to D (read directly from the (A,D) entry of M³).