Every sub-topic Pearson Edexcel 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.
3.1Route inspection (Chinese postman)Y12
3.2Travelling salesman problemY13
Try 3 questions
Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 30 questions in this topic, free, no account needed.
Algorithms on graphs II
Easy
Traversable graphs · Year 12 · 1 mark
A connected graph has no vertices of odd degree. What can be said about it?
(1)
Show worked solutionHide worked solution
Working, step by stepMarks
With every degree even, a route can leave each vertex as often as it arrives.A: It is Eulerian: every edge can be travelled once, ending where it started
B1
Total1
MMethodMethod mark: for a correct method, even with a slip.
AAccuracyAccuracy mark: for a correct answer from a correct method.
BIndependentIndependent mark: for a correct fact or result on its own, with no method needed.
A lower bound for the travelling salesman problem · Year 13 · 1 mark
A vertex is deleted from a network. The remaining network has a minimum spanning tree of weight 42, and the two shortest arcs at the deleted vertex have weights 7 and 9. What lower bound does this give for the optimal tour?
(1)
Show worked solutionHide worked solution
Working, step by stepMarks
Lower bound = weight of the residual minimum spanning tree + the two shortest arcs at the deleted vertex.: 58
B1
Total1
MMethodMethod mark: for a correct method, even with a slip.
AAccuracyAccuracy mark: for a correct answer from a correct method.
BIndependentIndependent mark: for a correct fact or result on its own, with no method needed.
With your permission, SUVAT counts which pages are visited: anonymously, with no tracking cookies. (One essential cookie keeps you signed in; that needs no permission.)May SUVAT count page visits, anonymously and without tracking cookies?How your data is used