A2 October 2020 Q6

EdexcelCurrent spec11 marksRoute Inspection Shortest Path

Figure 4: network on A to G with arcs AB 24, AC 42, AD 65, BC 15, CE 19, CF 45, CD 21, CG 31, DF 34, DG y, EF x, FG 24 — Figure 4

[The total weight of the network is \(320 + x + y\)]

(a) State, with justification, whether the graph in Figure 4 is Eulerian, semi-Eulerian or neither. (2)

The weights on the arcs in Figure 4 represent distances. The weight on arc EF is \(x\) where \(12 \lt x \lt 26\) and the weight on arc DG is \(y\) where \(0 \lt y \lt 10\)

An inspection route of minimum length that traverses each arc at least once is found. The inspection route starts and finishes at A and has a length of 409

It is also given that the length of the shortest route from F to G via A is 140

(b) Using appropriate algorithms, find the value of \(x\) and the value of \(y\). (9)

Mark scheme (a)

Scheme	Marks	AO
The graph has exactly two odd nodes and so the graph is semi-Eulerian	B1 dB1	2.4 2.2a
	(2)

Notes

(a) B1: Explanation which consists of the graph having two odd nodes or stating graph is semi-Eulerian

dB1: Exactly two odd nodes (or two odd nodes and five even nodes or the rest even) together with the deduction that therefore the graph is semi-Eulerian

Dijkstra labelling from A: A 1 0 (0); B 2 24 (24); C 3 39 (42 39); E 4 58 (58); D 5 60 (65 60); G 6 60 + y (70 60 + y); F 7 58 + x (84 58 + x) — Mark scheme (b)

Scheme	Marks	AO
	M1 A1 A1 A1	1.1b 1.1b 1.1b 1.1b
Shortest path from A to F is \(58 + x\) and shortest path from A to G is \(60 + y\)	A1ft	2.2a
\(58 + x + 60 + y = 140\)	M1	2.1
The only odd nodes in the network are A and G	B1	2.2a
Route inspection algorithm: Shortest route between A and G is \(60 + y\) \(\Rightarrow\ 320 + x + y + 60 + y = 409\)	M1	3.1b
\(x = 15\) and \(y = 7\)	A1	2.2a
	(9)
	(11 marks)