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

Name Date

Counting walks with powers of the adjacency matrix Problem set B

Write the adjacency matrix, use the calculator for the power, and read the right row and column. Say which entry you read.

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

Skills

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

    VWXYZ
    1. (a) from V to X;
    2. (b) from W to Z.

  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.

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

    STUV
    1. (a) from S to T;
    2. (b) from U to S.

  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;
    2. (b) from S to R.

  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.
    2. (b) List all the cycles of length 4 that start and end at N.

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

    UVWXY

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;
    2. (b) from D to E.

  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;
    2. (b) from E to C.

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.
    2. (b) Use your answer to find the number of edges in the graph.

  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

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