Adjacency matrices and walks
In a minute
An stores a graph as a grid of numbers, and its powers count : entry of is the number of walks of length from to . You also use and build the behind Google's PageRank.
You'll be able to
- Write the adjacency matrix of a graph, and read a graph from its .
- Describe a walk and its length.
- Count walks of exactly , or at most , edges with powers of the adjacency matrix, and decide which vertices can be reached.
- Use a weighted adjacency table of costs, distances or times.
- Construct the transition matrix for a random walk on a , as in PageRank.
Before you start2 quick questions on what this builds on
Revise first: 1.14 Matrices, determinants and inverses and 3.14 Graph theory basics
Adjacency matrices
A drawing of a graph is easy to read but hard to calculate with. An adjacency matrix holds the same information as numbers.
Label the rows and columns in the same order, usually alphabetical. A means no direct edge, and two separate edges give a .
Undirected graph: each edge works both ways, so and the matrix is symmetric about the leading diagonal. With no loops, each row adds up to the of its vertex.
: an edge from to adds to row , column only. Rows add up to out-degrees and columns to in-degrees.
A loop at puts on the leading diagonal: going round it is one step from back to . A has only s and s, with s on the diagonal.
Try it first, then reveal one step at a time.
- F is joined to G, K and L, so row F is . G is joined to F and K: .
- K is joined to F, G, L and V: . L to F, K and V: . V to K and L: .
- Check: is symmetric with s on the diagonal. The row sums add to , matching the paths.
Try it first, then reveal one step at a time.
- Rows are “from”, columns are “to”. Row P: . Row Q: . Row R: . Row S: .
- is not symmetric: row R, column S is but row S, column R is , because the run from R to S is one way.
- Column P adds to , the in-degree of P. In context: a skier can reach P directly from Q, R or S, but there is only one way out of P.
Walks and powers of the adjacency matrix
Write a walk as a list of vertices. F–K–L–K has length and visits K twice. In a directed graph a walk follows the arrows. 3.16 adds trails, which never repeat an edge, and paths, which never repeat a vertex.
Count the walks of length from to . Each is for some middle vertex , and there are of them through .
Adding over every gives : row of times column of . That is entry of .
The leading diagonal of counts closed walks: entry counts the walks of length from back to .
Try it first, then reveal one step at a time.
- You need entry (F, V) of : row F of times column V of .
- Row F is and column V is , so .
- The non-zero products come from K and L, so the walks are F–K–V and F–L–V, as in the figure.
Try it first, then reveal one step at a time.
- Write down what you need: entry (Q, P) of . This earns the method mark.
- Enter in the order P, Q, R, S and find . Row Q, column P is .
- One walk is Q–R–P–Q–R–S–P. It uses the lift from Q to R twice, which a walk allows.
Walks of at most k edges, and reaching every vertex
When any number of edges up to a limit is allowed, add the counts for each length.
“At most ” means lengths to . “Fewer than ” stops at .
A in entry of means no walk of exactly edges goes from to . If every entry off the leading diagonal of is non-zero, every vertex can reach every other in at most steps.
Try it first, then reveal one step at a time.
- Add entry (G, V) of , and : .
- These are G–K–V, then G–F–K–V, G–F–L–V and G–K–L–V.
- In context: there are ways from the gate to the viewpoint along at most three paths.
Try it first, then reveal one step at a time.
- (a) . Off the diagonal, row S, column R is (and so is row P, column S).
- So no: there is no walk of or edges from S to R.
- (b) . Every entry off the leading diagonal is non-zero, so yes. For example, S to R is S–P–Q–R.
- The in row S, column S only means a skier can't return to S within steps.
- (a) No: no walk from S to R. (b) Yes: every entry off the leading diagonal of is non-zero.
Weighted adjacency tables
Never write for a missing edge: would mean a link that is free or instant. Undirected weights give a symmetric table; for directed weights, rows are “from”.
The table shows only direct edges, so the cheapest way between two vertices may go through others. Raising a table of weights to a power doesn't count walks.
Try it first, then reveal one step at a time.
- (a) One vertex per island, and one edge for each entry above the leading diagonal, labelled with its time (figure below).
- (b) Quickest to X: V–W–X , less than V–X . Quickest to Y: V–W–X–Y , less than V–W–Y or V–X–Y .
- Z is reached from Y () or X (): beats . So V–W–X–Y–Z takes minutes.
- Interpret: the quickest journey uses four ferries. Waiting at each change could make a route with fewer ferries better in practice.
Try it first, then reveal one step at a time.
- (a) Uphill is slower than downhill, so times depend on direction: F to H takes minutes, H to F only .
- (b) F–G–H–F: . F–H–G–F: .
- So F–H–G–F, minutes: it does the slow climb to H early and freewheels down to G.
Transition matrices for a random walk
Picture a visitor who keeps moving along an edge chosen at random. A transition matrix holds the probability of each move.
For an undirected graph, the out-degree is the degree. Each column adds up to . Columns are “from”, as in 4.19: the other way round from , so is transposed with each column divided by its total.
The graph must be strongly connected: a vertex with no edge out would give a column of zeros, and a walker could get stuck in one part of the graph.
Try it first, then reveal one step at a time.
- Degrees: A , B , C , D .
- Column A: B and C each get . Column B: A and C each get . Column C: A, B and D each get . Column D: C gets .
- Check: each column adds up to . Interpret: row C, column D is because D's only doorway leads to C.
Google's PageRank works this way. Pages are vertices and links are directed edges. A surfer clicks a random link on each page, and the pages visited most in the long run rank highest. The full algorithm also adds random jumps; 4.19 finds the long-run proportions.
Try it first, then reveal one step at a time.
- Out-degrees: H (to N, S, W), N (to H, S), S (to H), W (to S). Every page can reach every other, so the graph is strongly connected.
- Column H: N, S, W each . Column N: H, S each . Column S: H gets . Column W: S gets .
- Interpret: S has the most links in, but it passes every visitor to H. In the long run the surfer is on H about of the time and on S about : links from a busy page count for more.
Common mistakes
- A matrix of the wrong size or with no labels. vertices give an matrix; label the rows and columns.
- Reading the wrong entry. Row is the start, so walks from E to B are in row E, column B.
- Using alone when shorter walks count. “At most ” needs ; “fewer than ” stops at .
- Treating walks as real routes. A walk can pass its end vertex early or repeat edges, so if the journey must stop at the target, the true count may be smaller.
Exam tips
- “Find the number of walks”: write the entry you need, such as “row Q, column P of ”, before the number. That earns the method mark.
- “State, with justification” whether every vertex can be reached: quote the zero or non-zero entries and say what they mean, such as “no walk from S to R in steps”.
- “Hence”: use your own matrix from the earlier part. A wrong matrix used correctly can still earn follow-through marks.
Key takeaways
Practise this
13 past-paper questions on Adjacency matrices and walks in the AI HL bank, each with a mark scheme and a worked explanation.