AI HL · AHL 1
0 of 43 skills done
Counting walks with powers of the adjacency matrix
AHL 1.4
Screenshot and video to come
Screenshot and video to come
Choose a graph, a start vertex, an end vertex and a length k. The matrix Ak counts the walks. When there are few, they are listed.
Rows are where a walk starts. Columns are where it ends. The highlighted entry is the answer.
Choose a start and an end vertex.
The graph has vertices W, X, Y and Z. Find the number of walks of length 3 from W to Z.
Have a go first. Then open the working one line at a time.
Adjacency matrix, rows and columns in the order W, X, Y, Z: \(A=\begin{pmatrix}0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)
Entry in row i, column j is the number of edges between i and j.
From the calculator: \(A^3=\begin{pmatrix}4 & 5 & 5 & 5 \\ 5 & 2 & 5 & 2 \\ 5 & 5 & 4 & 5 \\ 5 & 2 & 5 & 2\end{pmatrix}\)
The entry in row i, column j of \(A^3\) counts walks of length 3 from i to j.
Row W, column Z: 5
There are 5 walks of length 3 from W to Z.
The graph has vertices P, Q, R and S. There is a loop at P, two edges between P and Q, and one edge each for QR, RS and PS. Find the number of walks of length 5 from P to R.
Have a go first. Then open the working one line at a time.
Adjacency matrix, rows and columns in the order P, Q, R, S: \(A=\begin{pmatrix}1 & 2 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)
The loop at P goes in as 1, not 2: we count connections, not which way round the loop is travelled. The double edge PQ goes in as 2.
From the calculator: \(A^5=\begin{pmatrix}114 & 124 & 39 & 74 \\ 124 & 56 & 61 & 31 \\ 39 & 61 & 9 & 37 \\ 74 & 31 & 37 & 17\end{pmatrix}\)
The entry in row i, column j of \(A^5\) counts walks of length 5 from i to j.
Row P, column R: 39
There are 39 walks of length 5 from P to R.
The directed graph shows one-way links between K, L, M and N. Find the number of walks of length 4 from L to M.
Have a go first. Then open the working one line at a time.
Adjacency matrix, rows and columns in the order K, L, M, N: \(A=\begin{pmatrix}0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\)
Entry in row i, column j is the number of edges from i to j.
From the calculator: \(A^4=\begin{pmatrix}2 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1\end{pmatrix}\)
The entry in row i, column j of \(A^4\) counts walks of length 4 from i to j.
Row L, column M: 2
There are 2 walks of length 4 from L to M.
The directed graph shows the one-way links between four vertices. Find the number of walks of length less than 4 from T to S.
Have a go first. Then open the working one line at a time.
Adjacency matrix, rows and columns in the order S, T, U, V: \(A=\begin{pmatrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\)
Rows are where an arc starts, columns where it ends.
From the calculator: \(A+A^2+A^3=\begin{pmatrix}2 & 2 & 1 & 1 \\ 4 & 2 & 2 & 1 \\ 3 & 2 & 1 & 1 \\ 2 & 1 & 1 & 0\end{pmatrix}\)
Walks of length 1, 2 and 3 are all shorter than 4.
Row T, column S: 1 + 1 + 2 = 4
Check the split by reading the same entry in A, \(A^2\) and \(A^3\).
In the graph, list all the paths of length 3 from H to L. A path does not visit any vertex twice.
Have a go first. Then open the working one line at a time.
H is joined to J and M.
Every path of length 3 starts H-J or H-M.
H-J-K-L; H-J-M-L; H-M-J-L
Check each one: 3 edges, no vertex repeated, finishing at L.
3 paths
Write the list. It is the working.
In the same graph, list all the cycles of length 4 that start and end at J. A cycle and its reverse count as the same cycle: write each one once.
Have a go first. Then open the working one line at a time.
J-H-M-L-J; J-K-L-M-J
A cycle returns to its start and visits no other vertex twice.
2 cycles
J-K-L-M-J and J-M-L-K-J are the same cycle in two directions. Count it once.