IB Maths AI HL 3.16 Graph algorithms

[Maximum number: 17]

This question compares possible designs for a new computer network between multiple school buildings, and whether they meet specific requirements.
A school's administration team decides to install new fibre-optic internet cables underground. The school has eight buildings that need to be connected by these cables. A map of the school is shown below, with the internet access point of each building labelled A-H.

Figure for Question AHL 3.16 (HL)—Graph algorithms question 1 — IB Maths AI HL

Jonas is planning where to install the underground cables. He begins by determining the distances, in metres, between the underground access points in each of the buildings.

He finds $\mathrm{AD}=89.2 \mathrm{~m}, \mathrm{DF}=104.9 \mathrm{~m}$ and $\mathrm{A} \hat{\mathrm{DF}}=83^{\circ}$ .

(a)

By using Kruskal's algorithm, find the minimum spanning tree for S, showing clearly the order in which edges are added.

[ 3 ]

(b)

Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.

[ 2 ]

(c)

The computer network fails if any part of it becomes unreachable from any other part. To help protect the network from failing, every building could be connected to at least two other buildings. In this way if one connection breaks, the building is still part of the computer network. Jonas can achieve this by finding a Hamiltonian cycle within the graph.

State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.

[ 1 ]

(d)

Starting at D, use the nearest neighbour algorithm to find the upper bound for the installation cost of a computer network in the form of a Hamiltonian cycle.

Note: Although the graph is not complete, in this instance it is not necessary to form a table of least distances.

[ 5 ]

edges (or weights) are chosen in the order

DG (8668)
GH (9603)
HE (9251)
EC (8239)
CB (13 156)
BA (8811)
AF (21 310)
FD (11 539)
A1A1A1

Figure for Answer to Question (d) — IB Maths AI HL

Note: Award A1 for the first two edges chosen in the correct order. Award A1A1 for the first five edges chosen in the correct order. Award A1A1A1 for all eight edges chosen in the correct order. Accept a diagram as an answer, provided the order of edges is communicated.
finding the sum of the weights of their edges
8668+9603+9251+8239+13156+8811+21310+11539
upper bound = $\$ 90577$

(e)

By deleting D, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.

[ 6 ]

attempt to find MST after deleting vertex D
these edges (or weights) (in any order)
CE (8239)
AB (8811)
EH (9251)
GH (9603)
BE (10 153)
FG (12606)

Note: Prim's or Kruskal's algorithm could be used at this stage.
reconnect D to MST with two different edges

DG (8668)
BD (8778)

Note: This A1 is independent of the first A mark and can be awarded if both DG and BD are chosen to reconnect D to the MST, even if the MST is incorrect.

Figure for Answer to Question (e) — IB Maths AI HL

finding the sum of the weights of their edges
8239+8811+9251+9603+10153+12606+8668+8778
Note: For candidates with an incorrect MST or no MST, the weights of at least seven of the edges being summed (two of which must connect to D ) must be shown to award this (M1).
lower bound = $\$ 76109$

IB Maths AI HL 3.16 Graph algorithms Question Bank

Exam points

AHL 3.16 (HL)—Graph algorithms question 1

Question (a)

Question (b)

Question (c)

Question (d)

Question (e)