CourseCourseConceptConceptDocsDocuments

IB Maths AI HL Ahl 3 16 Hl Graph Algorithms Questions

Practise classifying graph routes, finding minimum spanning trees, applying postman or travelling-salesman algorithms, and checking weights, parity and route conditions.

Syllabus
First assessment 2021
Course
Mathematics: applications and interpretation HL
Level
HL

Exam points

  • Classify walks, trails, paths, circuits and cycles, and determine Eulerian or Hamiltonian routes under graph constraints.
  • Apply Kruskal or Prim to find minimum spanning trees and interpret total weight.
  • Use Chinese postman methods or travelling-salesman nearest-neighbour/deleted-vertex algorithms to produce and justify route bounds.
  • Check graph conditions, edge weights, parity and the meaning of the chosen algorithm before reporting the result.

Learn this topic

Study AHL 3.16 (HL)—Graph algorithms conceptsOpen the corresponding Concept lesson for explanations, examples and exam connections.

IB Maths AI HL Ahl 3 16 Hl Graph Algorithms Questions question 1

[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 IB Maths AI HL Ahl 3 16 Hl Graph Algorithms Questions 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 AD=89.2 m,DF=104.9 m\mathrm{AD}=89.2 \mathrm{~m}, \mathrm{DF}=104.9 \mathrm{~m} and ADF^=83∘\mathrm{A} \hat{\mathrm{DF}}=83^{\circ}.

Question (a)

(a)

Jonas creates the following graph, S, using the cost of installing the cables between two buildings as the weight of each edge.

Figure for Question (a) — IB Maths AI HL

The computer network could be designed such that each building is directly connected to at least one other building and hence all buildings are indirectly connected.

[ 5 ]

Question (i)

(i)

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

[ 3 ]

Question (ii)

(ii)

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

[ 2 ]

Question (b)

(b)

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 ]

Question (c)

(c)

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 ]

Question (d)

(d)

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

[ 6 ]
All question bank results loaded