Home / IB Mathematics AHL 3.15: Adjacency matrices AI HL Paper 2- Exam Style Questions

IB Mathematics AHL 3.15: Adjacency matrices AI HL Paper 2- Exam Style Questions- New Syllabus

IBDP Maths AI HL Paper 2 - All Topics

Question

The maritime connections between five island ports, \(A\) through \(E\), are modeled by a directed graph, \(G\). The adjacency matrix \(M\), representing the direct paths available between these ports, is given by:
\(M = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \end{pmatrix}\)
(a) Identify the specific direct route between two ports that is restricted to one-way travel only.
(b) Utilizing matrix algebra:
(i) prove that no single port can reach every other port in the network in a sequence of exactly three voyages.
(ii) determine if it is possible to travel between any two ports in the system using three or fewer voyages. Justify your conclusion.
During the peak travel season, a new pricing structure is introduced. The minimum cost, in euros (EUR), for travel between the ports is summarized in the following adjacency table:
PortABCDE
A03785
B30496
C740\(a\)10
D89\(a\)03
E561030
(c) Assuming no direct passage exists between ports \(D\) and \(C\), demonstrate that the minimum cost \(a\) must be 13 EUR by evaluating all potential multi-stage routes.
(d) Departing from port \(A\), apply the nearest neighbour algorithm to establish an upper bound for the total expense of a circuit that visits every port once and returns to \(A\).
(e) By removing vertex \(A\) and its associated edges, employ the deleted vertex algorithm to calculate a lower bound for the cost of a Hamiltonian path through the remaining ports.

Most-appropriate topic codes:

• TOPIC AHL 3.15: Adjacency matrices and walks — parts (a), (b)
• TOPIC AHL 3.16: Hamiltonian cycles and TSP algorithms — parts (d), (e)
▶️ Answer/Explanation
Detailed solution

(a)
Comparing the entries of matrix \(M\):
\(M_{AE} = 1\) but \(M_{EA} = 0\).
\(M_{DE} = 1\) but \(M_{ED} = 0\).
The route between \(A\) and \(E\) (or between \(D\) and \(E\)) can only be travelled in one direction.

(b)
(i) Calculate \(M^3\) to find walks of exactly length 3:
\(M^3 = \begin{pmatrix} 1 & 3 & 1 & 1 & 3 \\ 3 & 1 & 3 & 1 & 4 \\ 0 & 3 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 2 \\ 0 & 4 & 0 & 2 & 1 \end{pmatrix}\)
The matrix contains 0 entries (e.g., \(M^3_{CA}=0\)), confirming some routes are impossible in exactly three trips.

(ii) Check connectivity in 3 trips or fewer using \(M + M^2 + M^3\):
\(M + M^2 + M^3 = \begin{pmatrix} 2 & 5 & 2 & 2 & 5 \\ 4 & 4 & 4 & 2 & 6 \\ 1 & 4 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 3 \\ 1 & 5 & 1 & 3 & 3 \end{pmatrix}\)
All ports can be reached because there are no 0 entries in the non-diagonal positions of the sum matrix.

(c)
To show \(a = 13\), evaluate indirect paths between \(C\) and \(D\):
• Route \(CAD\): \(7 + 8 = 15\)
• Route \(CBD\): \(4 + 9 = 13\)
• Route \(CED\): \(10 + 3 = 13\)
(Route \(CBED\): \(4 + 6 + 3 = 13\) is also accepted).
The least cost is 13 EUR.

(d)
Nearest Neighbour Algorithm from A:
1. Start at \(A\). Nearest unvisited is \(B\) (3). Path: \(A \to B\)
2. From \(B\), nearest unvisited is \(C\) (4). Path: \(A \to B \to C\)
3. From \(C\), nearest unvisited is \(E\) (10). Path: \(A \to B \to C \to E\)
4. From \(E\), only remaining is \(D\) (3). Path: \(A \to B \to C \to E \to D\)
5. Return to start: \(D \to A\) (8).
Total cost = \(3 + 4 + 10 + 3 + 8 = \mathbf{28}\) EUR.

(e)
Deleted Vertex Algorithm (A):
1. Form MST of \(\{B, C, D, E\}\):
– Edge \(ED\) (3)
– Edge \(BC\) (4)
– Edge \(BE\) (6)
Length of spanning tree = \(4 + 6 + 3 = 13\).
2. Reconnect \(A\) using the two cheapest incident edges:
– \(AB\) (3)
– \(AE\) (5)
Lower bound = \(13 + 3 + 5 = \mathbf{21}\) EUR.

More DP Math AI HL Paper 2 Questions..

Leave a Reply

Scroll to Top