IB Maths AI HL AI 3.4 Graph theory questions

Exam-style questions in the shape of Paper 1 and Paper 2, with full markschemes. Read the markscheme, or type, photograph or draw your answer and get it marked.

Paper

Paper 1 Paper 2

Difficulty

Easy Medium Hard

Question 1

Paper 2Medium6 marks

A road-maintenance vehicle starts at depot A, must travel along every road segment at least once, and must return to A. The roads are undirected.

Road	Length (km)	Road	Length (km)
AB	4	AC	6
AD	8	BC	2
BD	5	CD	3
CE	7	DE	4
DF	6	EF	2

The following table gives the least distance, in kilometres, between each pair of locations.

	A	B	C	D	E	F
A	–	4	6	8	12	14
B	4	–	2	5	9	11
C	6	2	–	3	7	9
D	8	5	3	–	4	6
E	12	9	7	4	–	2
F	14	11	9	6	2	–

(a)

State all the locations of odd degree.

[1]

(b)

Using the least-distance table, determine which pairs of odd-degree locations should have their shortest paths repeated to minimize the additional distance.

[1]

(c)

Hence determine the minimum distance travelled. Explain why the Chinese postman algorithm is appropriate rather than the travelling salesman algorithm, and why the repetitions in part (b) allow the vehicle to return to A after traversing every road.

[4]

Question 2

Paper 1Medium8 marks

A courier moves between three depots, $A$ $B$ and $C$ The directed routes leaving each depot are shown below.

Depot	Depots reachable in one leg
$A$	$B, C$
$B$	$A, C$
$C$	$A$

At each depot, the courier chooses uniformly from the routes leaving that depot. Use the convention that the entry in row $i$ column $j$ of a transition matrix is the probability of moving from depot $i$ to depot $j$

(a)

Write down the adjacency matrix $A$ for this network, using the order $A,B,C$ for both rows and columns.

[2]

(b)

Find the number of two-leg walks from $A$ back to $A$ using the appropriate entry of $A^2$

[2]

(c)

Construct the transition matrix $T$ for the courier’s movements, using the order $A,B,C$ for both rows and columns.

[2]

(d)

Using your transition matrix, find the probability that the courier is at $A$ after exactly two legs, starting from $A$

[2]

The best questions are still waiting

Unlock every question in this topic, then type, photograph or draw your answer and have it marked against the markscheme. Find out where you are dropping marks.

Unlock all questions Compare Student and Student Plus

	A	B	C	D	E	F
A	–	4	6	8	12	14
B	4	–	2	5	9	11
C	6	2	–	3	7	9
D	8	5	3	–	4	6
E	12	9	7	4	–	2
F	14	11	9	6	2	–

	A	B	C	D	E	F
A	–	4	6	8	12	14
B	4	–	2	5	9	11
C	6	2	–	3	7	9
D	8	5	3	–	4	6
E	12	9	7	4	–	2
F	14	11	9	6	2	–

	A	B	C	D	E	F
A	–	4	6	8	12	14
B	4	–	2	5	9	11
C	6	2	–	3	7	9
D	8	5	3	–	4	6
E	12	9	7	4	–	2
F	14	11	9	6	2	–