RevisionDojo

AHL 3.15—Adjacency matrices and tables - IB Questionbank | RevisionDojo

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 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 2

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 3

HLPaper 2

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

M=\begin{pmatrix} 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{pmatrix}

Draw the directed graph representing this neural network.

[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. It sends signals to $B$ and $E$ , and receives signals from $D$ . Update the adjacency matrix $M_{\text{new}}$ and draw the updated graph.

[3]

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

[4]

Question 4

HLPaper 1

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

M=\begin{pmatrix} 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{pmatrix}

Construct the adjacency table for the pathways and their respective viewing times.

[2]

Use Kruskal's algorithm to find the minimum spanning tree (MST) for the network, listing the edges in the order they are selected.

[5]

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

[4]

Find a lower bound for the travel time by deleting vertex $A$ and using the MST found in part 2.

[4]

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 5

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 6

HLPaper 2

Based on this graph: Graph of vertices A, B, C, D, E

Write down the adjacency matrix for this graph.

[2]

Find a Hamiltonian path in this graph.

[1]

State the change that would be needed for a Hamiltonian cycle to be present.

[1]

Question 7

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 8

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]

Hence or otherwise, solve the travelling salesman problem.

[2]

Question 9

HLPaper 2

A robot navigates a grid of six rooms, $A, B, C, D, E$ , and $F$ . The possible movements between rooms are represented by a directed graph. Some paths are marked with sensors (indicated by dashed edges); these paths have twice the probability of being chosen compared to normal paths from the same room.

The movements are shown in the following graph:

Note: For vertex $B$ , the path to $C$ is a sensor path, while the path to $D$ is a normal path. For vertex $C$ , both paths to $D$ and $F$ are normal paths. All other vertices have a single outgoing normal path as shown.

Determine the transition matrix, $\mathbf{M}$ , for the robot's movement.

[3]

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

[3]

Comment on one limitation of this probabilistic model in representing a real robot's movement.

[2]

A new room $G$ is added to the system. The path from $F$ is changed to a normal path to $G$ , and a new sensor path is added from $G$ to $C$ . Update the transition matrix to represent this new 7-room system.

[3]

Question 10

HLPaper 2

Based on this graph:

Create a weighted adjacency matrix for the graph, with vertices listed in alphabetical order (A, B, C, D).

[2]

Use Kruskal's algorithm to find the minimum spanning tree, stating the order in which edges are added and the total weight of the tree.

[3]

Paper

Level

Question 1

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 2

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 3

HLPaper 2

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

M=\begin{pmatrix} 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{pmatrix}

Draw the directed graph representing this neural network.

[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. It sends signals to $B$ and $E$ , and receives signals from $D$ . Update the adjacency matrix $M_{\text{new}}$ and draw the updated graph.

[3]

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

[4]

Question 4

HLPaper 1

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

M=\begin{pmatrix} 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{pmatrix}

Construct the adjacency table for the pathways and their respective viewing times.

[2]

Use Kruskal's algorithm to find the minimum spanning tree (MST) for the network, listing the edges in the order they are selected.

[5]

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

[4]

Find a lower bound for the travel time by deleting vertex $A$ and using the MST found in part 2.

[4]

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 5

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 6

HLPaper 2

Based on this graph: Graph of vertices A, B, C, D, E

Write down the adjacency matrix for this graph.

[2]

Find a Hamiltonian path in this graph.

[1]

State the change that would be needed for a Hamiltonian cycle to be present.

[1]

Question 7

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 8

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]

Hence or otherwise, solve the travelling salesman problem.

[2]

Question 9

HLPaper 2

The movements are shown in the following graph:

Determine the transition matrix, $\mathbf{M}$ , for the robot's movement.

[3]

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

[3]

Comment on one limitation of this probabilistic model in representing a real robot's movement.

[2]

[3]

Question 10

HLPaper 2

Based on this graph:

Create a weighted adjacency matrix for the graph, with vertices listed in alphabetical order (A, B, C, D).

[2]

Use Kruskal's algorithm to find the minimum spanning tree, stating the order in which edges are added and the total weight of the tree.

[3]

Paper

Level

Question 1

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 2

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 3

HLPaper 2

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

M=\begin{pmatrix} 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{pmatrix}

Draw the directed graph representing this neural network.

[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. It sends signals to $B$ and $E$ , and receives signals from $D$ . Update the adjacency matrix $M_{\text{new}}$ and draw the updated graph.

[3]

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

[4]

Question 4

HLPaper 1

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

M=\begin{pmatrix} 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{pmatrix}

Construct the adjacency table for the pathways and their respective viewing times.

[2]

Use Kruskal's algorithm to find the minimum spanning tree (MST) for the network, listing the edges in the order they are selected.

[5]

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

[4]

Find a lower bound for the travel time by deleting vertex $A$ and using the MST found in part 2.

[4]

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 5

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 6

HLPaper 2

Based on this graph: Graph of vertices A, B, C, D, E

Write down the adjacency matrix for this graph.

[2]

Find a Hamiltonian path in this graph.

[1]

State the change that would be needed for a Hamiltonian cycle to be present.

[1]

Question 7

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 8

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]

Hence or otherwise, solve the travelling salesman problem.

[2]

Question 9

HLPaper 2

The movements are shown in the following graph:

Determine the transition matrix, $\mathbf{M}$ , for the robot's movement.

[3]

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

[3]

Comment on one limitation of this probabilistic model in representing a real robot's movement.

[2]

[3]

Question 10

HLPaper 2

Based on this graph:

Create a weighted adjacency matrix for the graph, with vertices listed in alphabetical order (A, B, C, D).

[2]

Use Kruskal's algorithm to find the minimum spanning tree, stating the order in which edges are added and the total weight of the tree.

[3]

AHL 3.15—Adjacency matrices and tables Questionbank