RevisionDojo

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)

1.

Draw the directed graph.

[2]

2.

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

[3]

3.

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

[3]

4.

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

[3]

5.

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)

1.

Construct the adjacency table for the pathways.

[2]

2.

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

[5]

3.

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]

4.

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

[3]

5.

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)

1.

Draw the directed graph, including self-loops.

[2]

2.

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

[3]

3.

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

[4]

4.

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

[3]

5.

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)

1.

Construct the adjacency table for the network.

[2]

2.

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

[5]

3.

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]

4.

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

[3]

5.

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:

1.

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

[3]

2.

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

[3]

3.

Comment on one limitation of this probabilistic model.

[2]

4.

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 1

A directed graph models a data network with nodes $P, Q, R, S$ , and $T$ , representing servers, and directed edges indicating one-way data transmission.

1.

Write down the adjacency matrix $M$ for this graph, with rows and columns ordered $P, Q, R, S, T$ .

[2]

2.

Find the number of distinct walks of length 5 from $P$ to $R$ .

[3]

3.

Determine the number of servers reachable from $P$ in exactly 3 steps.

[3]

4.

A new server $U$ is added, receiving data from $Q$ and sending to $R$ . Update the adjacency matrix and redraw the graph.

[3]

5.

In the updated network, calculate the number of walks of length 4 from $U$ to $P$ .

[4]

Question 7

HLPaper 2

A communication network between five research stations, labeled $A, B, C, D$ , and $E$ , is represented by a directed graph. The directed edges indicate one-way communication links. The graph is shown below.

1.

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

[3]

2.

Calculate the number of distinct walks of length 4 from vertex $A$ to vertex $C$ .

[4]

3.

A message is sent from station $A$ and must pass through exactly two other stations before reaching station $C$ . Determine the number of possible routes for this message.

[3]

4.

The network is upgraded by adding a new station $F$ , connected such that $F$ sends messages to $B$ and $E$ , and receives messages from $C$ . Update the adjacency matrix to include station $F$ .

[3]

5.

Using the updated matrix from part (d), find the number of walks of length 3 from $F$ to $A$ .

[3]

Question 8

HLPaper 2

A social network is modeled as a graph with vertices $V, W, X, Y, Z$ , representing users, and edges indicating direct friendships. The adjacency matrix $M$ is:

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

1.

Determine the degree of each vertex.

[2]

2.

Find the number of walks of length 5 from $V$ to $Y$ .

[3]

3.

A message starts at $V$ and spreads to friends, then friends of friends, and so on. Find the number of users who receive the message after exactly 3 steps.

[4]

4.

The network adds a new user $U$ , connected to $W$ and $Y$ . Update the adjacency matrix and redraw the graph.

[3]

5.

Using the updated matrix, find the number of triangles (cycles of length 3) including vertex $U$ .

[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)

1.

Draw the directed graph, including self-loops.

[2]

2.

Find the number of walks of length 4 from $U$ to $Z$ .

[3]

3.

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

[4]

4.

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

[3]

5.

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

[4]

Question 10

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.

1.

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

[2]

2.

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

[5]

3.

Calculate the total distance of the MST.

[2]

4.

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]

5.

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

[3]

AHL 3.15—Adjacency matrices and tables Questionbank