Further Mathematics · AQA 7367 · Option D · Topic DB

Networks

Networks: minimum spanning trees, route inspection and the travelling salesperson problem.

5 sub-topics
Taught in Year 12
57 practice questions
5 animated lessons

Practice questions (57) Lessons Worksheets All AQA Further Mathematics topics

What the specification says

Every sub-topic AQA can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

DB1Language of networks: node, arc, weightY12
DB2Minimum spanning treesY12
DB3Route inspectionY12
DB4Travelling salesperson: upper and lower boundsY12
DB5Evaluate and refine network modelsY12

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 57 questions in this topic, free, no account needed.

Algorithms on graphs

Easy

Minimum spanning trees · Year 12 · 1 mark

A connected network has 10 vertices. How many edges does a minimum spanning tree of it have?
(1)

Show worked solutionHide worked solution

A tree on $n$ vertices always has $n - 1$ edges. $B$ : 9

Total1

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms on graphs

Medium

Minimum spanning trees · Year 12 · 5 marks

Figure 1 shows a network of paths between seven buildings. The numbers are lengths in metres.

Figure 1

(a)
Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order you select them.
(3)
(b)
State the weight of the minimum spanning tree.
(1)
(c)
Explain why Prim's algorithm would give a tree of the same weight.
(1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)3 marks

Take arcs in order of weight, rejecting any that would form a cycle.
AD (4), DF (4), CF (5), BD (7), BE (10), FG (12)

Part (b)1 mark

$42\text{ m}$

Part (c)1 mark

Both algorithms find a minimum spanning tree, and every minimum spanning tree has the same total weight.

Total5

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

Algorithms on graphs II

Hard

Route inspection · Year 12 · 5 marks

Figure 1 shows a network of streets. The numbers are lengths in metres. A road-sweeper must travel along every street, starting and finishing at A.

Figure 1

(a)
Find the total length of the streets.
(1)
(b)
Use the route inspection algorithm to find the length of the shortest route.
(4)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)1 mark

$102$

Part (b)4 marks

Odd vertices: $A$ , $B$ , $D$ , $E$ .
Consider all three pairings. $AB + DE$ ${}= 12 + 19$ ${}= 31,$ $\quad AD + BE$ ${}= 11 + 4$ ${}= 15,$ $\quad AE + BD$ ${}= 16 + 15$ ${}= 31$
Repeat the shortest pairing. $102 + 15 = 117\text{ m}$

Total5

MMethod mark: for a correct method, even with a slip.
AAccuracy mark: for a correct answer from a correct method.
BIndependent mark: for a correct fact or result on its own, with no method needed.

How did it go?

Report a problem with this question

What the specification says

Try 3 questions

Part (a)3 marks

Part (b)1 mark

Part (c)1 mark

Part (a)1 mark

Part (b)4 marks

Analytics choice: help improve SUVAT?