AHL 3.15—Adjacency matrices and tables Questionbank

Practice AHL 3.15—Adjacency matrices and tables with authentic IB Mathematics Applications & Interpretation (AI) exam questions for both SL and HL students. This question bank mirrors Paper 1, 2, 3 structure, covering key topics like core principles, advanced applications, and practical problem-solving. Get instant solutions, detailed explanations, and build exam confidence with questions in the style of IB examiners.

Paper

Level

Question 1

HLPaper 2

A neural network has nodes $A, B, C, D, E$ , and $F$ , with directed edges representing signal propagation. The adjacency matrix is:

M=\left(\begin{array}{llllll} 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right)

Draw the directed graph.

[2]

Find the number of walks of length 6 from $A$ to $E$ .

[3]

List all trails of length 4 from $A$ to $C$ .

[3]

A new node $G$ is added, sending signals to $B$ and $E$ , and receiving from $D$ . Update the adjacency matrix and graph.

[3]

In the updated network, find the number of nodes reachable from $G$ in exactly 3 steps.

[4]

Question 2

HLPaper 1

A museum has exhibits $A, B, C, D$ , and $E$ , connected by pathways with weights as viewing times (in minutes). The adjacency matrix is:

M=\left(\begin{array}{lllll} 0 & 5 & 0 & 7 & 0 \\ 5 & 0 & 4 & 0 & 6 \\ 0 & 4 & 0 & 3 & 0 \\ 7 & 0 & 3 & 0 & 5 \\ 0 & 6 & 0 & 5 & 0 \end{array}\right)

Construct the adjacency table for the pathways.

[2]

Use Kruskal's algorithm to find the MST, listing edges in order of selection.

[5]

A visitor wants to view all exhibits, starting and ending at $A$ . Find an upper bound for the total time using the nearest neighbor algorithm.

[4]

Find a lower bound using the MST from part (b).

[3]

If a new exhibit $F$ is added with pathways $F-A(4), F-B(3)$ , and $F-D(6)$ , update the MST and calculate its total weight.

[4]

Question 3

HLPaper 2

A transport network has hubs $A, B, C, D, E$ , and $F$ , with directed edges representing one-way routes. The adjacency matrix includes self-loops (hubs retaining cargo):

M=\left(\begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 \end{array}\right)

Draw the directed graph, including self-loops.

[2]

Find the number of walks of length 5 from $A$ to $F$ .

[3]

A cargo starts at $A$ . Determine which hubs are reached after exactly 4 steps.

[4]

A new hub $G$ is added, sending to $B$ and $F$ , and receiving from $E$ . Update the adjacency matrix and graph.

[3]

In the updated network, find the number of walks of length 3 from $G$ to $A$ , and interpret in the context of cargo transport.

[4]

Question 4

HLPaper 1

A city's metro system has stations $A, B, C, D, E$ , with weighted edges representing distances (in km). The adjacency matrix is:

M=\left(\begin{array}{lllll} 0 & 4 & 0 & 6 & 0 \\ 4 & 0 & 3 & 0 & 5 \\ 0 & 3 & 0 & 2 & 0 \\ 6 & 0 & 2 & 0 & 4 \\ 0 & 5 & 0 & 4 & 0 \end{array}\right)

Construct the adjacency table for the network.

[2]

Use Kruskal's algorithm to find the MST, listing edges in order of selection.

[5]

A tourist starts at $A$ and visits all stations, returning to $A$ . Use the nearest neighbor algorithm to find an upper bound for the distance.

[4]

Find a lower bound using the MST from part (b).

[3]

If a new station $F$ is added with edges $F-A(3), F-B(2)$ , and $F-D(5)$ , update the MST and calculate its new total weight.

[4]

Question 5

HLPaper 2

A robot navigates a grid of rooms $A, B, C, D, E$ , and $F$ , with directed edges indicating possible movements, some marked with sensors (dashed edges) that double the probability of being chosen. The graph is:

Determine the transition matrix for the robot's movement, considering sensor paths have twice the probability of normal paths.

[3]

Using a graphic display calculator, estimate the percentage of time the robot spends at $F$ if it moves indefinitely.

[3]

Comment on one limitation of this probabilistic model.

[2]

If a new room $G$ is added with a sensor path to $C$ and a normal path from $F$ , update the transition matrix.

[3]

Question 6

HLPaper 2

Based on the graph:

Create the complete weighted adjacency matrix (including the shortest weighted connection between every two vertices).

[3]

Find the upper bound for the travelling salesman problem using vertex A.

[3]

Question 7

HLPaper 2

Based on this graph:

Create the adjacency matrix.

[2]

Find a hamiltonian path in this graph

[1]

What change would be needed for a hamiltonian cycle to be present?

[1]

Question 8

HLPaper 2

Based on the graph:

Create an unweighted adjacency matrix for the graph.

[2]

Hence, identify the odd vertices.

[1]

Hence, find the solution to the chinese postman problem.

[4]

Question 9

HLPaper 2

Based on the graph:

Create the weighted adjacency matrix showing all shortest connections.

[2]

Use the deleted vertex theorem with each vertex to find the best lower bound.

[4]

Use the nearest neighbour algorithm to find the upper bound

[2]

Hecnce or otherwise, solve the travelling salesman problem.

[2]

Question 10

HLPaper 2

Based on this graph:

Create a weighted adjacency matrix.

[2]

Use Kruskal's algorithm to create the minimum spanning tree, and state its value.

[3]