Graph Theory - IB Math AI Question Bank

Subjects

Features

Review

HOT

Tutoring

Graph Theory

Practice exam-style IB Math AI questions for Graph Theory, aligned with the syllabus and grouped by topic.

Verified by Karim

Paper

Difficulty

Status

Level

This content can't be printed from the browser. Use Export PDF with Pro for an offline copy.

Question 1

HL • Paper 1

Easy

Calculator Permitted

HL • Paper 1

Easy

Calculator Permitted

A connected simple graph $G$ has eight vertices. Their degrees are

2,3,3,4,4,4,5,x

The graph has 14 edges.

Determine the value of $x$ .

[2]

State the number of vertices of odd degree.

[1]

Determine the number of additional edges required to make $G$ complete.

[2]

Question 2

HL • Paper 1

Easy

Calculator Permitted

HL • Paper 1

Easy

Calculator Permitted

A connected undirected graph has vertices $A,B,C,D,E,F$ with degrees

d(A)=2,\quad d(B)=3,\quad d(C)=4,\quad d(D)=3,\quad d(E)=2,\quad d(F)=2

Determine whether the graph has an Eulerian trail or an Eulerian circuit.

[2]

A new edge $BD$ is added. Determine whether the new graph has an Eulerian circuit. Justify your answer.

[2]

Question 3

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

The directed graph $G$ has vertices in the order $A,B,C,D$ and adjacency matrix

M=\begin{pmatrix} 0&1&1&0\\ 0&0&1&0\\ 1&0&0&1\\ 0&1&0&0 \end{pmatrix}

Rows represent starting vertices.

Determine the out-degree and in-degree of vertex $A$ .

[2]

Write down the vertices adjacent from $C$ .

[1]

Determine whether $G$ is strongly connected. Justify your answer.

[2]

Question 4

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

An undirected graph has vertices in the order $A,B,C,D$ and adjacency matrix

M=\begin{pmatrix} 0&1&1&0\\ 1&0&1&1\\ 1&1&0&1\\ 0&1&1&0 \end{pmatrix}

Calculate the number of walks of length $3$ from $A$ to $D$ .

[2]

Calculate the number of walks from $A$ to $D$ having length at most $3$ but at least $1$ .

[2]

Explain why the identity matrix is not included in the calculation in part (b).

[1]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 5

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A delivery vehicle moves between depots $A$ , $B$ and $C$ . Its transition matrix is

T=\begin{pmatrix} 0&0.5&0.5\\ 0.25&0&0.75\\ 0.6&0.4&0 \end{pmatrix}

where rows represent the current depot. Initially, the vehicle is at depot $A$ .

Write down the initial state vector $\mathbf p_0$ .

[1]

Determine the probability distribution after two transitions.

[3]

Write down the probability that the vehicle is at depot $C$ after two transitions.

[1]

Question 6

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A connected undirected graph has vertex set $\{A,B,C,D,E\}$ and edge set

\{AB,BC,CD,DA,AC,CE\}

Classify the walk $A-B-C-A-D-C$ as a walk, trail or path, using the most specific applicable term. Justify your answer.

[2]

Determine the endpoints of an Eulerian trail in the graph and give one such trail.

[2]

Explain why the graph cannot have a Hamiltonian cycle.

[1]

Question 7

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A road inspector must start and finish at the same junction while travelling along every road at least once. The road network has edges with lengths, in kilometres,

AB=4,\ BC=3,\ CD=5,\ DA=6,\ AC=2,\ CE=4,\ DE=3

Determine the minimum length of the inspector's route.

[4]

Question 8

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

The distances between five cities are represented by the complete weighted graph below.

\begin{array}{c|ccccc} &A&B&C&D&E\\ \hline A&-&4&7&3&8\\ B&4&-&2&6&5\\ C&7&2&-&4&3\\ D&3&6&4&-&6\\ E&8&5&3&6&- \end{array}

Apply the nearest neighbour algorithm starting at $A$ . Write down the resulting tour.

[3]

Determine the upper bound for the travelling salesman problem obtained from this tour.

[2]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 9

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

For a travelling salesman problem, a feasible Hamiltonian cycle of weight $42$ has been found. Applying the deleted vertex algorithm at vertices $A,B,C,D,E$ gives lower bounds $39,42,40,41,38$ , respectively.

State the strongest lower bound and the vertex that produces it.

[1]

Deduce the weight of an optimal Hamiltonian cycle. Justify your answer.

[3]

Question 10

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A communication network has vertices $P,Q,R,S,T,U,V$ and edges

PQ,\ PR,\ QS,\ QT,\ RU,\ UV

The network is connected.

Show that the network is a tree.

[2]

Write down the unique path from $S$ to $V$ and state its length.

[2]

A new edge $TV$ is added. Write down the cycle that is created.

[1]

Question 11

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A company wishes to connect six sites $A,B,C,D,E,F$ . The possible links and their costs, in thousands of dollars, are

\begin{aligned} &AB=2,\ AC=5,\ BC=3,\ BD=6,\ CD=4,\\ &CE=7,\ DE=2,\ DF=5,\ EF=3,\ BE=8. \end{aligned}

Using Kruskal's algorithm, write down the first three edges selected.

[2]

Determine a minimum spanning tree and its total cost.

[3]

Question 12

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

The weighted adjacency table for a network is shown below. A dash indicates that there is no direct edge.

\begin{array}{c|ccccc} &A&B&C&D&E\\ \hline A&-&4&2&-&7\\ B&4&-&1&5&6\\ C&2&1&-&8&3\\ D&-&5&8&-&2\\ E&7&6&3&2&- \end{array}

Use Prim's algorithm, starting at $D$ , to write down the edges in the order in which they are selected.

[3]

Calculate the total weight of the minimum spanning tree.

[2]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 13

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A complete weighted graph has the following edge weights:

\begin{aligned} &AB=6,\ AC=4,\ AD=7,\ AE=5,\ BC=3,\\ &BD=8,\ BE=6,\ CD=5,\ CE=7,\ DE=2. \end{aligned}

Delete vertex $A$ and determine the weight of a minimum spanning tree on the remaining vertices.

[2]

Use the deleted vertex algorithm to determine a lower bound for the travelling salesman problem.

[2]

Explain why the value found in part (b) is a lower bound.

[1]

Question 14

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

Four clinics $A,B,C,D$ are connected through an intermediate junction $X$ . The undirected road lengths, in kilometres, are

AX=3,\ BX=4,\ CX=2,\ DX=5,\ AB=8,\ BC=9,\ CD=10,\ AD=12

A route in the completed graph may represent a multi-edge shortest route in the original network.

Determine the least distances from $A$ to $D$ and from $B$ to $D$ .

[2]

Complete the least-distance model as required and apply the nearest neighbour algorithm starting at $A$ . Determine the resulting tour and its total length.

[3]

Question 15

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A simplified page-ranking model contains webpages $P,Q,R,S$ . The hyperlinks are

P\to Q,\quad P\to R,\quad Q\to R,\quad R\to P,\quad R\to S,\quad S\to P

A user chooses with equal probability between all links leaving the current page. The webpages are ordered $P,Q,R,S$ .

Construct the transition matrix $T$ , using rows as source webpages.

[2]

Initially, the user is equally likely to be on any webpage. Determine the probability distribution after two transitions.

[3]

Using the distribution after two transitions, identify the webpages with the joint highest rank.

[1]

Question 16

HL • Paper 1

Medium

Calculator Permitted

HL • Paper 1

Medium

Calculator Permitted

A maintenance vehicle must traverse every edge of a network and return to its starting point. The network has vertices $A,B,C,D,O$ and weighted edges

OA=2,\ OB=3,\ OC=4,\ OD=5,\ AB=4,\ BC=6,\ CD=4,\ DA=7

Identify the odd-degree vertices.

[1]

Determine the least total weight of the edges that must be duplicated.

[3]

Hence determine the minimum total weight of a closed route traversing every edge.

[2]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 17

HL • Paper 2

Medium

Calculator Permitted

HL • Paper 2

Medium

Calculator Permitted

A connected simple graph $G$ represents communication links between eight research stations. The degrees of seven of the vertices are

2,2,3,3,4,4,4

The graph has $13$ edges. The two vertices of degree $3$ are labelled $U$ and $V$ .

I.

Determine the degree of the eighth vertex.

[2]

II.

Determine how many more edges would be required to make $G$ complete.

[2]

A new edge $UV$ is added. Determine whether the resulting graph has an Eulerian circuit. Justify your answer.

[4]

Question 18

HL • Paper 2

Medium

Calculator Permitted

HL • Paper 2

Medium

Calculator Permitted

A company plans fibre links between seven facilities. The possible links and installation costs, in thousands of dollars, are

\begin{aligned} &AB=4,\ AC=7,\ BC=2,\ BD=6,\ CD=3,\ CE=8,\ DE=5,\\ &DF=9,\ EF=1,\ EG=6,\ FG=4,\ CG=10,\ BG=9. \end{aligned}

I.

Using Kruskal's algorithm, write down the links in the order in which they are selected.

[2]

II.

Calculate the total cost of the minimum spanning tree.

[2]

Apply Prim's algorithm starting at $G$ . State the order in which the links are selected and explain why the total agrees with part (a).

[4]

Question 19

HL • Paper 3

Medium

Calculator Permitted

HL • Paper 3

Medium

Calculator Permitted

A connected simple graph models communication links between ten mountain observatories $A,B,C,D,E,F,G,H,I,J$ . The degrees of the first eight vertices are

1,2,2,3,3,3,4,4

The graph has $14$ edges, and $d(J)=d(I)+2$ .

I.

Determine $d(I)$ and $d(J)$ .

[3]

II.

State the number of odd-degree vertices.

[1]

I.

Explain why the original graph has neither an Eulerian circuit nor an Eulerian trail.

[2]

II.

It is known that the four odd-degree vertices can be paired using two edges that are not already in the graph. Determine the minimum number of edges that must be added to obtain an Eulerian circuit. Justify your answer.

[2]

Question 20

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A directed data network has vertices in the order $A,B,C,D,E$ and adjacency matrix

M=\begin{pmatrix} 0&1&1&0&0\\ 0&0&1&1&0\\ 1&0&0&0&1\\ 0&0&0&0&1\\ 0&1&0&0&0 \end{pmatrix}

Rows represent starting vertices.

I.

Determine the in-degree and out-degree of vertex $C$ .

[2]

II.

Explain why the directed graph is strongly connected.

[2]

I.

Calculate the number of walks of length $4$ from $A$ to $E$ .

[2]

II.

Calculate the number of walks from $A$ to $E$ having length at least $1$ and at most $4$ .

[2]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 21

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A simplified page-ranking model has webpages $J,K,L,M$ . The directed hyperlinks are

J\to K,\quad J\to L,\quad K\to L,\quad L\to J,\quad L\to M,\quad M\to J,\quad M\to K

A user chooses with equal probability from the hyperlinks leaving the current webpage. Rows represent the current webpage.

I.

Construct the transition matrix $T$ , using the vertex order $J,K,L,M$ .

[2]

II.

The user starts at webpage $J$ . Determine the probability distribution after two transitions.

[2]

I.

Determine the probability distribution after four transitions.

[2]

II.

Find the stationary distribution and hence identify the webpage with the highest long-term rank.

[2]

Question 22

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

An undirected walking network has vertices $A,B,C,D,E,F$ and edges

AB,BC,CD,DE,EF,FA,AC,CE

The vertices are ordered $A,B,C,D,E,F$ .

I.

Write down the degree of each vertex.

[2]

II.

Construct the adjacency matrix $A$ of the network.

[2]

I.

Calculate the number of walks of length $5$ from $A$ to $D$ .

[2]

II.

Calculate the number of walks from $A$ to $D$ having positive length at most $3$ .

[2]

Question 23

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A weighted graph has vertices $A,B,C,D,E,F$ and edges

\begin{aligned} &AB=1,\ AC=1,\ BC=1,\ BD=3,\ CE=3,\\ &DE=2,\ DF=4,\ EF=2,\ AE=5,\ BF=5. \end{aligned}

I.

Use Kruskal's algorithm to find one minimum spanning tree.

[2]

II.

Calculate the weight of the minimum spanning tree.

[2]

Determine whether the minimum spanning tree is unique. Justify your answer by giving two different minimum spanning trees.

[4]

Question 24

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

An ecological network is represented by a connected simple graph $G$ with nine vertices and eight edges. The vertex degrees are

1,1,1,1,2,2,2,3,x

I.

Determine the value of $x$ .

[2]

II.

Show that $G$ is a tree.

[2]

One new edge is added between two previously non-adjacent vertices. Explain why exactly one cycle is created, and determine how many further edges would be required to make the resulting graph complete.

[4]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 25

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A directed graph models the permitted movement of data packets between five servers $P,Q,R,S,T$ . Its directed edges are

P\to Q,\quad P\to R,\quad Q\to R,\quad Q\to S,\quad R\to P,\quad R\to T,\quad S\to T,\quad T\to P,\quad T\to S

Rows of an adjacency matrix represent starting vertices.

I.

Construct the adjacency matrix $A$ using the vertex order $P,Q,R,S,T$ .

[2]

II.

Determine the in-degree and out-degree of server $T$ .

[2]

I.

Calculate the number of directed walks of length $3$ from $P$ to $T$ .

[2]

II.

Hence calculate the number of walks from $P$ to $T$ having positive length at most $3$ .

[2]

Question 26

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

Visitors move randomly between three exhibition rooms $A,B,C$ . From $A$ , a visitor chooses equally between $B$ and $C$ . From $B$ , the visitor chooses equally between $A$ and $C$ . From $C$ , the visitor always moves to $A$ . Rows represent the current room.

I.

Construct the transition matrix $T$ using the order $A,B,C$ .

[2]

II.

A visitor starts in room $A$ . Determine the probability distribution after two transitions.

[2]

I.

Find the stationary distribution of the visitor.

[3]

II.

Interpret the first component of this stationary distribution in context.

[1]

Question 27

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A research institute is installing fibre between laboratories $A,B,C,D,E,F$ . The possible links and their costs, in thousands of euros, are given by the edge list below; this edge list defines the network:

AB=3,\quad AC=6,\quad BC=2,\quad BD=5,\quad CD=4,\quad CE=7,\quad DE=3,\quad DF=8,\quad EF=2,\quad BF=9,\quad AE=10,\quad AF=11

I.

Use Kruskal's algorithm to determine a minimum spanning tree.

[3]

II.

Calculate the total cost of the minimum spanning tree.

[1]

The institute wants to add exactly one available link so that failure of any one link leaves all laboratories connected.

[4]

Question 28

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A courier must visit six distribution centres. Travel times, in minutes, form a complete weighted graph with edges

\begin{aligned} &AB=2,\quad AC=7,\quad AD=8,\quad AE=6,\quad AF=3,\quad BC=3,\quad BD=7,\\ &BE=8,\quad BF=6,\quad CD=2,\quad CE=6,\quad CF=8,\quad DE=3,\quad DF=7,\quad EF=2. \end{aligned}

	A	B	C	D	E	F
A	—	2	7	8	6	3
B	2	—	3	7	8	6
C	7	3	—	2	6	8
D	8	7	2	—	3	7
E	6	8	6	3	—	2
F	3	6	8	7	2	—

I.

Apply the nearest-neighbour algorithm starting at $A$ .

[2]

II.

Calculate the resulting upper bound.

[1]

Use the deleted vertex algorithm with $A$ deleted to prove that the tour in part (a) is optimal.

[5]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 29

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A festival walkway graph is a simple undirected graph with vertices $X,A,B,C,D$ and edges

XA, AB, BX, XC, CD, DX

Thus, two triangular walkway loops share only the vertex $X$ .

I.

Determine whether the graph has an Eulerian circuit. Justify your answer.

[2]

II.

Explain why the graph has no Hamiltonian cycle.

[2]

For the new graph, determine whether an Eulerian trail exists and whether a Hamiltonian cycle exists. Justify each answer.

[4]

Question 30

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A street-cleaning vehicle must traverse every street in a connected network and return to its starting point. The street lengths, in kilometres, are

AB=4,\ BC=2,\ CD=5,\ DA=3,\ AC=6,\ CE=4,\ DE=2,\ EB=3

I.

Identify the odd-degree vertices.

[2]

II.

Calculate the total length of all the streets.

[1]

Compare all possible pairings of the odd-degree vertices and determine the least additional distance required.

[3]

Hence determine the minimum length of a closed route and give one possible route.

[2]

Question 31

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A maintenance worker must inspect every corridor of a campus network and return to the starting point. Corridor lengths, in hundreds of metres, are

PQ=3,\ QR=4,\ RS=2,\ SP=5,\ PR=6,\ RT=3,\ TU=4,\ US=2

I.

Identify the odd-degree vertices and find the shortest route between them.

[2]

II.

Determine the minimum total length of the inspection route.

[2]

A new corridor $PU$ of weight $1$ is constructed. Determine the new minimum total length of an inspection route and explain why it is shorter than the route in part (a).

[4]

Question 32

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

The table gives travel times, in minutes, between six locations in a complete network.

\begin{array}{c|cccccc} &A&B&C&D&E&F\\ \hline A&-&4&8&7&6&3\\ B&4&-&5&9&7&6\\ C&8&5&-&4&3&7\\ D&7&9&4&-&5&8\\ E&6&7&3&5&-&4\\ F&3&6&7&8&4&- \end{array}

Location	A	B	C	D	E	F
A		4	8	7	6	3
B	4		5	9	7	6
C	8	5		4	3	7
D	7	9	4		5	8
E	6	7	3	5		4
F	3	6	7	8	4

I.

Apply the nearest-neighbour algorithm starting at $A$ . State the resulting tour.

[2]

II.

Determine the resulting upper bound.

[2]

Delete vertex $A$ and use the deleted vertex algorithm to find a lower bound. Hence state the largest possible difference between the upper bound in part (a) and the optimal tour.

[4]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 33

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A travelling salesperson must visit five warehouses. The complete weighted graph has edge weights

\begin{aligned} &AB=2,\ AC=6,\ AD=7,\ AE=3,\ BC=4,\\ &BD=5,\ BE=6,\ CD=2,\ CE=5,\ DE=4. \end{aligned}

I.

Apply the nearest-neighbour algorithm starting at $A$ .

[2]

II.

State what the value found represents for the optimal travelling-salesperson tour.

[2]

Delete vertex $A$ and use the deleted vertex algorithm. Hence prove that the tour found in part (a) is optimal.

[4]

Question 34

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A water-taxi network has terminals $A,B,C,D,E$ . The available direct routes have lengths, in kilometres,

AB=4,\ AC=9,\ BC=3,\ BD=8,\ CD=2,\ CE=7,\ DE=4,\ AE=12

For the travelling-salesperson model, a completed edge represents a shortest route in the original network.

I.

Determine the least distances from $A$ to $C$ , from $B$ to $D$ , and from $C$ to $E$ .

[2]

II.

Determine the least distances from $A$ to $D$ and from $B$ to $E$ .

[2]

Apply the nearest-neighbour algorithm to the completed graph, starting at $A$ . Determine the tour and its total length.

[4]

Question 35

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A bicycle moves randomly between docking stations $A,B,C,D,E$ . The directed routes are

A\to B,\ A\to D,\ B\to C,\ C\to A,\ C\to D,\ D\to C,\ D\to E,\ E\to A

At each station, the bicycle is equally likely to take any outgoing route.

I.

Construct the transition matrix $T$ in the order $A,B,C,D,E$ , using rows as source stations.

[2]

II.

Initially, the bicycle is equally likely to be at any station. Determine the probability distribution after three transitions.

[2]

Find the stationary distribution and identify all stations with the highest long-term probability.

[4]

Question 36

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A directed graph has vertices in the order $P,Q,R,S$ and adjacency matrix

A=\begin{pmatrix} 0&1&1&0\\ 0&0&1&0\\ 0&0&0&1\\ 1&1&0&0 \end{pmatrix}

I.

Calculate the number of walks from $P$ to $S$ having positive length at most $4$ .

[2]

II.

Calculate the number of walks of length $6$ from $P$ to $S$ .

[2]

Determine the smallest integer $k$ such that every vertex can reach every other distinct vertex using at most $k$ directed edges. Justify your answer using matrix powers.

[4]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 37

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A festival site is represented by a connected graph with vertices $A,B,C,D,E,F$ and edges

AB,BC,CA,CD,DE,EF,FD

Thus, two triangular regions are joined by the edge $CD$ .

I.

Determine whether the graph has an Eulerian trail or an Eulerian circuit.

[2]

II.

Give one Eulerian trail.

[2]

Explain why the original graph has no Hamiltonian cycle. A new edge $BF$ is then added. Give a Hamiltonian cycle in the new graph.

[4]

Question 38

HL • Paper 2

Hard

Calculator Permitted

HL • Paper 2

Hard

Calculator Permitted

A renewable-energy company can install cables along the following links. The weights are cable lengths in kilometres.

\begin{aligned} &AB=2,\ AC=5,\ BC=3,\ BD=4,\ CD=2,\ CE=6,\\ &DE=3,\ DF=5,\ EF=2,\ AF=8,\ BE=7. \end{aligned}

I.

Use Prim's algorithm starting at $A$ to determine the order in which the links are selected.

[2]

II.

Calculate the total length of the minimum spanning tree.

[2]

The link $CD$ becomes unavailable. Use Prim's algorithm starting at $A$ to determine a new minimum spanning tree and its total length.

[4]

Question 39

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A wheel network $W_n$ , where $n\geq 4$ , consists of a cycle of $n$ outer vertices and one central vertex. The central vertex is adjacent to every outer vertex. The accompanying diagram is a separate schematic example and does not define the edge set of $W_n$ ; use the written definition.

I.

Write down the degree of the central vertex and the degree of each outer vertex.

[2]

II.

Hence determine the number of edges in $W_n$ .

[2]

Show that $(A^2)_{vv}=d(v)$ for every vertex $v$ , and hence determine $\operatorname{tr}(A^2)$ in terms of $n$ and $|E|$ .

[4]

Question 40

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A power network has vertices $P,Q,R,S,T,U$ . The upper vertex in the diagram is denoted by $U$ . The available links have weights

PQ=2,\quad QR=3,\quad RS=4,\quad ST=5,\quad PU=6,\quad QU=6,\quad SU=7,\quad TU=8,\quad PT=x

where $x>0$ .

I.

For $x=10$ , use Kruskal's algorithm to determine a minimum spanning tree.

[2]

II.

Calculate its total weight.

[1]

I.

Find the values of $x$ for which the link $PT$ occurs in a minimum spanning tree.

[3]

II.

Hence write down the minimum spanning tree weight as a piecewise function of $x$ .

[2]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 41

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A road inspector must traverse every road in a connected network and return to the starting junction. The road lengths, in kilometres, are

AB=4,\quad BC=3,\quad CD=4,\quad DE=3,\quad EF=4,\quad FA=3,\quad AC=2,\quad CE=2,\quad BD=2,\quad AE=3

I.

Identify the odd-degree vertices.

[2]

II.

Calculate the total length of all roads.

[1]

Apply the Chinese postman algorithm to determine the minimum length of the inspector's closed route.

[5]

Question 42

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A snowplough must traverse every road and return to its starting junction. The network has weighted edges, with lengths in kilometres:

PQ=3,\quad QR=4,\quad RS=3,\quad SP=4,\quad RT=2,\quad TP=5

A new road $PR$ of length $x$ kilometres is proposed. If constructed, the new road must also be cleared.

I.

Identify the odd-degree vertices in the original network and find the length of a shortest path between them.

[2]

II.

Determine the minimum length of a closed route in the original network.

[2]

I.

Show that after the new road is constructed, the network has an Eulerian circuit.

[2]

II.

Find the values of $x$ for which constructing the new road decreases the minimum closed-route length.

[2]

Question 43

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A ferry company serves ports $H,J,K,L,M$ . The available two-way routes, with lengths in kilometres, are

HJ=4,\quad HK=10,\quad JK=3,\quad JL=8,\quad KL=2,\quad KM=7,\quad LM=3,\quad HM=12

For a travelling-salesperson model, an edge in the completed graph represents a shortest route through the original network.

I.

Determine the least distances from $H$ to $K$ , from $H$ to $L$ , and from $J$ to $M$ .

[3]

II.

Write down the least distance from $K$ to $M$ .

[1]

I.

Apply the nearest-neighbour algorithm to the completed graph, starting at $H$ .

[2]

II.

Calculate the tour length and explain how the final completed edge is travelled in the original network.

[2]

Question 44

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A simplified page-ranking model has webpages $U,V,W,X$ . The hyperlinks are

U\to V,\quad U\to W,\quad V\to W,\quad W\to U,\quad W\to X,\quad X\to U,\quad X\to V

A user chooses equally between all outgoing hyperlinks. Rows represent the current webpage.

I.

Construct the transition matrix $T$ in the order $U,V,W,X$ .

[2]

II.

A user starts on webpage $U$ . Determine the probability distribution after three transitions.

[2]

Find the stationary distribution and identify the webpage with the greatest long-term rank.

[4]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Question 45

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A monitoring network is arranged as a rooted $k$ -ary tree of depth $h$ . The root is at level $0$ . Every non-leaf vertex has exactly $k$ children, and all leaves are at level $h$ .

I.

For $k=2$ and $h=4$ , determine the number of vertices and the number of leaves.

[2]

II.

Determine the number of edges in this network.

[2]

For general $k>1$ and $h\geq1$ , show that the number of edges is

\frac{k^{h+1}-k}{k-1}

[4]

Question 46

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

The vertices $A_1,A_2,\ldots,A_n$ , where $n\geq4$ , represent checkpoints positioned at coordinates $1,2,\ldots,n$ on a straight line. The complete graph has edge weight

w(A_iA_j)=|i-j|

I.

For $n=6$ , apply the nearest-neighbour algorithm starting at $A_1$ .

[2]

II.

Calculate the weight of this tour.

[1]

For the graph defined above, prove that the nearest-neighbour algorithm starting at $A_1$ produces an optimal Hamiltonian cycle for general $n\ge4$ .

[5]

Question 47

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

A communication graph is the complete bipartite graph $K_{m,n}$ . Its vertices are divided into sets $L$ and $R$ , where $|L|=m$ and $|R|=n$ . Every vertex in $L$ is adjacent to every vertex in $R$ , and there are no edges joining two vertices in the same set.

I.

Write down the degree of a vertex in $L$ and the degree of a vertex in $R$ .

[2]

II.

Determine the number of edges in $K_{m,n}$ .

[1]

Fix a vertex $v$ in $L$ , and let $A$ be the adjacency matrix of the graph. Determine $(A^2)_{vv}$ and $(A^4)_{vv}$ , and hence deduce formulae for $(A^{2r})_{vv}$ and $(A^{2r+1})_{vv}$ for positive integers $r$ .

[5]

Question 48

HL • Paper 3

Hard

Calculator Permitted

HL • Paper 3

Hard

Calculator Permitted

Five observatories $A,B,C,D,E$ are arranged around a circular reserve. The complete weighted graph has weight $p$ on each perimeter edge

AB,\quad BC,\quad CD,\quad DE,\quad EA

and weight $q$ on each of the five remaining edges, where $0<p\leq q$ .

Edge	Type	Weight
A-B	Perimeter	p
B-C	Perimeter	p
C-D	Perimeter	p
D-E	Perimeter	p
E-A	Perimeter	p
A-C	Diagonal	q
A-D	Diagonal	q
B-D	Diagonal	q
B-E	Diagonal	q
C-E	Diagonal	q

I.

For $q>p$ , apply the nearest-neighbour algorithm starting at $A$ and give one possible tour.

[2]

II.

Write down the resulting upper bound.

[1]

Use the deleted vertex algorithm, deleting $A$ , to prove that a perimeter tour is optimal for every $q\geq p$ .

[5]

Build a Practice Exam — Math AI HL

Test your knowledge with a custom paper containing questions from selected topics.

Geometry of 3D Shapes

Trigonometric Functions

The Ultimate All-in-One
IB Platform

All content on this website has been developed independently from and is not endorsed by the International Baccalaureate Organization. International Baccalaureate and IB are registered trademarks owned by the International Baccalaureate Organization.