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

A power grid connects stations $G, H, I, J, K$ , with directed edges representing power flow. The adjacency matrix is:

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

Draw the directed graph.

[2]

Find the number of walks of length 6 from $G$ to $I$ .

[3]

Determine the number of stations reachable from $G$ in exactly 4 steps.

[4]

A new station $L$ is added, receiving power from $H$ and $J$ , and sending to $I$ . Update the adjacency matrix and redraw the graph.

[3]

In the updated network, find the number of walks of length 3 from $L$ to $G$ , and interpret this in the context of power flow.

[4]

Question 3

HLPaper 2

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.

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 4

HLPaper 2

A graph represents a pipeline network with vertices $A, B, C, D, E$ , and edges with weights as maintenance costs (in thousands of USD). The adjacency matrix is:

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

Draw the weighted graph corresponding to $M$ .

Use Prim's algorithm, starting at $A$ , to find the minimum spanning tree, indicating the order of edge selection.

[5]

A maintenance team must inspect all pipelines, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total cost.

[4]

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

[3]

If the edge $A-B$ cost increases to $x$ thousand USD , find the range of $x$ for which $A-B$ remains in the MST.

[4]

Question 5

HLPaper 2

A logistics company operates a network of warehouses labeled $A, B, C, D$ , and $E$ , connected by direct delivery routes with weights representing distances (in km). The weighted graph is shown below.

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 6

HLPaper 2

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 7

HLPaper 2

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.

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 8

HLPaper 2

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 9

HLPaper 2

A communication system has nodes $U, V, W, X, Y$ , and $Z$ , with directed edges representing signal paths, some with self-loops. The adjacency matrix is:

M=\left(\begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 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 4 from $U$ to $Z$ .

[3]

Determine the number of nodes reachable from $U$ in exactly 5 steps.

[4]

A new node $K$ is added, sending signals to $V$ and $X$ , and receiving from $Z$ . Update the adjacency matrix and graph.

[3]

In the updated system, find the number of cycles of length 3 including $K$ .

[4]

Question 10

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]

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 2

A power grid connects stations $G, H, I, J, K$ , with directed edges representing power flow. The adjacency matrix is:

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

Draw the directed graph.

[2]

Find the number of walks of length 6 from $G$ to $I$ .

[3]

Determine the number of stations reachable from $G$ in exactly 4 steps.

[4]

A new station $L$ is added, receiving power from $H$ and $J$ , and sending to $I$ . Update the adjacency matrix and redraw the graph.

[3]

In the updated network, find the number of walks of length 3 from $L$ to $G$ , and interpret this in the context of power flow.

[4]

Question 3

HLPaper 2

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.

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 4

HLPaper 2

A graph represents a pipeline network with vertices $A, B, C, D, E$ , and edges with weights as maintenance costs (in thousands of USD). The adjacency matrix is:

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

Draw the weighted graph corresponding to $M$ .

Use Prim's algorithm, starting at $A$ , to find the minimum spanning tree, indicating the order of edge selection.

[5]

A maintenance team must inspect all pipelines, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total cost.

[4]

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

[3]

If the edge $A-B$ cost increases to $x$ thousand USD , find the range of $x$ for which $A-B$ remains in the MST.

[4]

Question 5

HLPaper 2

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 6

HLPaper 2

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 7

HLPaper 2

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.

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 8

HLPaper 2

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 9

HLPaper 2

A communication system has nodes $U, V, W, X, Y$ , and $Z$ , with directed edges representing signal paths, some with self-loops. The adjacency matrix is:

M=\left(\begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 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 4 from $U$ to $Z$ .

[3]

Determine the number of nodes reachable from $U$ in exactly 5 steps.

[4]

A new node $K$ is added, sending signals to $V$ and $X$ , and receiving from $Z$ . Update the adjacency matrix and graph.

[3]

In the updated system, find the number of cycles of length 3 including $K$ .

[4]

Question 10

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]

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 2

A power grid connects stations $G, H, I, J, K$ , with directed edges representing power flow. The adjacency matrix is:

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

Draw the directed graph.

[2]

Find the number of walks of length 6 from $G$ to $I$ .

[3]

Determine the number of stations reachable from $G$ in exactly 4 steps.

[4]

A new station $L$ is added, receiving power from $H$ and $J$ , and sending to $I$ . Update the adjacency matrix and redraw the graph.

[3]

In the updated network, find the number of walks of length 3 from $L$ to $G$ , and interpret this in the context of power flow.

[4]

Question 3

HLPaper 2

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.

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 4

HLPaper 2

A graph represents a pipeline network with vertices $A, B, C, D, E$ , and edges with weights as maintenance costs (in thousands of USD). The adjacency matrix is:

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

Draw the weighted graph corresponding to $M$ .

Use Prim's algorithm, starting at $A$ , to find the minimum spanning tree, indicating the order of edge selection.

[5]

A maintenance team must inspect all pipelines, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total cost.

[4]

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

[3]

If the edge $A-B$ cost increases to $x$ thousand USD , find the range of $x$ for which $A-B$ remains in the MST.

[4]

Question 5

HLPaper 2

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 6

HLPaper 2

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $A, B, C, D, E$ .

[2]

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

[5]

Calculate the total distance of the MST.

[2]

A delivery van must visit all warehouses, starting and ending at $A$ . Use the nearest neighbor algorithm to find an upper bound for the total distance.

[4]

Determine a lower bound for the van's total distance using the MST from part (b).

[3]

Question 7

HLPaper 2

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.

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 8

HLPaper 2

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 9

HLPaper 2

A communication system has nodes $U, V, W, X, Y$ , and $Z$ , with directed edges representing signal paths, some with self-loops. The adjacency matrix is:

M=\left(\begin{array}{llllll} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 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 4 from $U$ to $Z$ .

[3]

Determine the number of nodes reachable from $U$ in exactly 5 steps.

[4]

A new node $K$ is added, sending signals to $V$ and $X$ , and receiving from $Z$ . Update the adjacency matrix and graph.

[3]

In the updated system, find the number of cycles of length 3 including $K$ .

[4]

Question 10

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]

AHL 3.15—Adjacency matrices and tables Questionbank