Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-4/problems/b/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.4

Counting walks with powers of the adjacency matrix Problem set B Worked solutions

Skills

  1. The graph has five vertices. Find the number of walks of length 4:

    VWXYZ

    1. (a) from V to X;

      • Adjacency matrix, rows and columns in the order V, W, X, Y, Z: \(A=\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0\end{pmatrix}\)
      • From the calculator: \(A^4=\begin{pmatrix}11 & 13 & 9 & 14 & 11 \\ 13 & 26 & 13 & 19 & 19 \\ 9 & 13 & 11 & 11 & 14 \\ 14 & 19 & 11 & 19 & 14 \\ 11 & 19 & 14 & 14 & 19\end{pmatrix}\)
      • Row V, column X: 9

    2. (b) from W to Z.

      • Adjacency matrix, rows and columns in the order V, W, X, Y, Z: \(A=\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0\end{pmatrix}\)
      • From the calculator: \(A^4=\begin{pmatrix}11 & 13 & 9 & 14 & 11 \\ 13 & 26 & 13 & 19 & 19 \\ 9 & 13 & 11 & 11 & 14 \\ 14 & 19 & 11 & 19 & 14 \\ 11 & 19 & 14 & 14 & 19\end{pmatrix}\)
      • Row W, column Z: 19

  2. The graph has vertices K, L, M and N. There is a loop at K, a double edge KL, and single edges LM, MN and NK. Enter the loop as 1. Find the number of walks of length 5:

    KLMN

    1. (a) from L to N.

      • Adjacency matrix, rows and columns in the order K, L, M, N: \(A=\begin{pmatrix}1 & 2 & 0 & 1 \\ 2 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0\end{pmatrix}\)
      • 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}\)
      • Row L, column N: 31

  3. The directed graph shows one-way links. Find the number of walks of length 4:

    STUV

    1. (a) from S to T;

      • Adjacency matrix, rows and columns in the order S, T, U, V: \(A=\begin{pmatrix}0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A^4=\begin{pmatrix}1 & 2 & 2 & 1 \\ 0 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1\end{pmatrix}\)
      • Row S, column T: 2

    2. (b) from U to S.

      • Adjacency matrix, rows and columns in the order S, T, U, V: \(A=\begin{pmatrix}0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A^4=\begin{pmatrix}1 & 2 & 2 & 1 \\ 0 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1\end{pmatrix}\)
      • Row U, column S: 1

  4. The directed graph shows one-way links. Find the number of walks of length less than 4:

    QRSU

    1. (a) from R to Q;

      • Adjacency matrix, rows and columns in the order Q, R, S, U: \(A=\begin{pmatrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A+A^2+A^3=\begin{pmatrix}1 & 2 & 1 & 1 \\ 3 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 3 & 3 & 2 & 1\end{pmatrix}\)
      • Row R, column Q: 3

    2. (b) from S to R.

      • Adjacency matrix, rows and columns in the order Q, R, S, U: \(A=\begin{pmatrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A+A^2+A^3=\begin{pmatrix}1 & 2 & 1 & 1 \\ 3 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 3 & 3 & 2 & 1\end{pmatrix}\)
      • Row S, column R: 2

  5. In the graph, a path visits no vertex twice. A cycle and its reverse count as one cycle.

    MNPQR

    1. (a) List all the paths of length 3 from M to Q.

      • Start at M, take 3 edges, finish at Q, repeat no vertex.
      • M-N-P-Q; M-N-R-Q; M-R-N-Q
      • 3 paths

    2. (b) List all the cycles of length 4 that start and end at N.

      • Start at N, take 4 edges, return to N, repeat no other vertex.
      • N-M-R-Q-N; N-P-Q-R-N
      • 2 cycles

  6. Is the graph Eulerian, semi-Eulerian or neither? If it has one, write down an Eulerian circuit or trail.

    UVWXY
    • Degrees: U 2, V 3, W 2, X 3, Y 2
    • Exactly two odd vertices, V and X, so the graph is semi-Eulerian (not Eulerian)
    • Start at V, end at X: V-U-Y-X-V-W-X
    • Check: each edge appears once

In context

  1. Five servers A to E in a data centre are joined by cables. There are two cables between B and C. Each other pair joined on the map has one cable. A message is passed along cables from server to server. Find the number of walks of length 3:

    ABCDE

    1. (a) from A to C;

      • Adjacency matrix, rows and columns in the order A, B, C, D, E: \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 & 0 \\ 1 & 2 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0\end{pmatrix}\)
      • From the calculator: \(A^3=\begin{pmatrix}4 & 7 & 9 & 2 & 5 \\ 7 & 4 & 14 & 2 & 4 \\ 9 & 14 & 4 & 8 & 2 \\ 2 & 2 & 8 & 0 & 4 \\ 5 & 4 & 2 & 4 & 0\end{pmatrix}\)
      • Row A, column C: 9

    2. (b) from D to E.

      • Adjacency matrix, rows and columns in the order A, B, C, D, E: \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 2 & 0 & 0 \\ 1 & 2 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0\end{pmatrix}\)
      • From the calculator: \(A^3=\begin{pmatrix}4 & 7 & 9 & 2 & 5 \\ 7 & 4 & 14 & 2 & 4 \\ 9 & 14 & 4 & 8 & 2 \\ 2 & 2 & 8 & 0 & 4 \\ 5 & 4 & 2 & 4 & 0\end{pmatrix}\)
      • Row D, column E: 4

  2. A visitor follows hyperlinks between five web pages A to E, as shown. Each link goes one way. Find the number of walks of length less than 4:

    ABCDE

    1. (a) from A to E;

      • Adjacency matrix, rows and columns in the order A, B, C, D, E: \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A+A^2+A^3=\begin{pmatrix}1 & 1 & 2 & 2 & 3 \\ 1 & 0 & 1 & 1 & 2 \\ 2 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 2 & 1 & 1\end{pmatrix}\)
      • Row A, column E: 3

    2. (b) from E to C.

      • Adjacency matrix, rows and columns in the order A, B, C, D, E: \(A=\begin{pmatrix}0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0\end{pmatrix}\)
      • From the calculator: \(A+A^2+A^3=\begin{pmatrix}1 & 1 & 2 & 2 & 3 \\ 1 & 0 & 1 & 1 & 2 \\ 2 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 2 & 1 & 1\end{pmatrix}\)
      • Row E, column C: 2

Stretch

  1. This graph has no loops and no double edges. Its adjacency matrix is A.

    MNPQR

    1. (a) Find \(A^2\) and write down its diagonal. Compare it with the degrees of the vertices.

      • Adjacency matrix, rows and columns in the order M, N, P, Q, R: \(A=\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0\end{pmatrix}\)
      • From the calculator: \(A^2=\begin{pmatrix}2 & 1 & 2 & 1 & 1 \\ 1 & 3 & 1 & 2 & 2 \\ 2 & 1 & 3 & 1 & 2 \\ 1 & 2 & 1 & 2 & 1 \\ 1 & 2 & 2 & 1 & 4\end{pmatrix}\)
      • Diagonal: M 2, N 3, P 3, Q 2, R 4
      • Degrees: M 2, N 3, P 3, Q 2, R 4. A walk of length 2 from a vertex to itself goes out along an edge and back, so there is one for each edge at the vertex.

    2. (b) Use your answer to find the number of edges in the graph.

      • Each edge adds 1 to the degree of two vertices, so the degrees add to twice the number of edges
      • 2 + 3 + 3 + 2 + 4 = 14, and 14 ÷ 2 = 7

  2. The directed graph shows one-way links between four vertices. Find the smallest k for which there are more than 8 walks of length k from D to F.

    DEFH
    • Adjacency matrix, rows and columns in the order D, E, F, H: \(A=\begin{pmatrix}0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0\end{pmatrix}\)
    • Use the calculator for \(A^k\) in turn and read row D, column F
    • k = 1: 1, k = 2: 1, k = 3: 1, k = 4: 2, k = 5: 3, k = 6: 4, k = 7: 6, k = 8: 9
    • The first count above 8 is at k = 8

jmaths.xyz · AI HL · AHL 1.4 Counting walks with powers of the adjacency matrix