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

A prominent international sports event assesses its network of seven towns, depicted as vertices, with edges representing the roads linking them. The weight on each edge signifies the distance, in kilometers, between the connected towns.

(a) Evaluate the possibility of designing a journey that starts and ends at different towns, ensuring all roads are used exactly once. Provide a justification for your assessment.

The shortest distances, in kilometers, between any pair of towns are presented in the following table:

 ABCDEFG
A×68511919
B6×1257313
C812×77ab
D557×65c
E11776×411
F93a54×d
G1913bc11d×

(b)(i) Calculate the value of \( a \), which represents the shortest distance between towns \( C \) and \( F \).

(b)(ii) Calculate the value of \( b \), which represents the shortest distance between towns \( C \) and \( G \).

(b)(iii) Calculate the value of \( c \), which represents the shortest distance between towns \( D \) and \( G \).

(b)(iv) Calculate the value of \( d \), which represents the shortest distance between towns \( F \) and \( G \).

(c) Implement the nearest neighbor algorithm, starting at vertex \( G \), to determine an upper limit for the traveling salesman problem.

(d)(i) Draw a minimum spanning tree for the subgraph including vertices \( A, B, C, D, E, F \).

(d)(ii) Record the total weight of the minimum spanning tree created.

(e) Based on the prior findings, establish a lower limit for the traveling salesman problem using a 1-tree approach.

(f) Propose a method to improve the lower limit previously determined.

The optimal route starting at \( A \) is confirmed as \( A – C – E – G – B – F – D – A \), with a total length of 52 kilometers.

(g) Taking into account that each road length shown in the graph is rounded to the nearest kilometer, compute the lower limit for the total distance of the optimal route.

▶️ Answer/Explanation
Markscheme

(a) Euler trail feasibility
More than two vertices have odd degree, so an Euler trail that starts and ends at different towns and uses every road exactly once is not possible.

(b) Table entries
(i) \(a=d(C,F)\)
Best via \(E\): \(C\to E=7\), \(E\to F=4\Rightarrow a=7+4=\mathbf{11}\).
(ii) \(b=d(C,G)\)
Best via \(E\): \(C\to E=7\), \(E\to G=11\Rightarrow b=7+11=\mathbf{18}\).
(iii) \(c=d(D,G)\)
Best via \(E\): \(D\to E=6\), \(E\to G=11\Rightarrow c=6+11=\mathbf{17}\).
(iv) \(d=d(F,G)\)
There is no direct edge \(F\!-\!G\). Compare paths: \(F\to E\to G:\ 4+11=15\), \(F\to B\to G:\ 3+13=16\), other routes are longer. Hence \(d=\mathbf{15}\).

(c) Nearest neighbour from \(G\) (upper bound)
\(G\to E(11)\to F(4)\to B(3)\to D(5)\to A(5)\to C(8)\to G(18)\).
Total \(=11+4+3+5+5+8+18=\mathbf{54\text{ km}}\) ⇒ upper bound 54 km.

(d)(i) Minimum spanning tree for \(A,B,C,D,E,F\)
One valid MST (Kruskal): \(BF(3),\ EF(4),\ AD(5),\ DB(5),\ DF(5)\). (Any cycle-free tree with the same total is acceptable.)

(d)(ii) Total weight
\(3+4+5+5+5=\mathbf{24\text{ km}}\).

(e) Lower bound for TSP (1-tree bound)
MST on \(A\!:\!F\) is 24 km. Add the two shortest edges incident to \(G\): \(GE=11\) and \(GB=13\).
Lower bound \(=24+11+13=\mathbf{48\text{ km}}\).

(f) Improving the lower bound
Recompute the 1-tree bound after removing a different vertex and take the largest bound; or augment the MST with a minimum perfect matching on odd-degree vertices (Held–Karp idea).

Given optimal tour: \(A\!-\!C\!-\!E\!-\!G\!-\!B\!-\!F\!-\!D\!-\!A\) with length \(8+7+11+13+3+5+5=52\text{ km}\).

(g) Rounding-aware lower bound for that optimal tour
Each of the 7 edges could be up to \(0.5\) km smaller (nearest-km rounding). \(52-7\times0.5=\mathbf{48.5\text{ km}}\).

More DP Math AI HL Paper 2 Questions..
Scroll to Top