D1 June 2015 Q1

EdexcelOld spec6 marksAllocation

Figure 1: bipartite graph joining vans A to F to deliveries 1 to 6 — Figure 1

Figure 2: initial matching A to 2, C to 4, E to 6, F to 3 — Figure 2

A delivery firm has six vans, A, B, C, D, E and F, available for six deliveries, 1, 2, 3, 4, 5 and 6. Each van must be assigned to just one delivery.

The bipartite graph shown in Figure 1 shows the possible matchings and Figure 2 shows an initial matching.

A complete matching is required, starting from the given initial matching.

(a) Explain why it is necessary to use the maximum matching algorithm twice. (1)

There are three possible alternating paths that start at either D or B. One of these is

D – 2 = A – 3 = F – 6 = E – 5

(b) Find the other two alternating paths. (2)

D – 2 = A – 3 = F – 6 = E – 5

(1)

(d) Starting from the improved matching found in (c), use the maximum matching algorithm to find a complete matching. You should list the alternating path that you use and your complete matching. (2)

Mark scheme (a)

Scheme	Marks
There are two unmatched vertices in each set (the algorithm matches only one vertex from one set to one vertex in the other set once per iteration)	B1
	(1)

Notes

a1B1: CAO – an understanding that there are two unmatched vertices in each set. However, be generous, and see below examples that we would accept for B1

Both B and D (or 1 and 5) are unmatched
Two vertices in set X (or two in set Y) are unmatched
There are four unmatched nodes (or there are more than two unmatched nodes)
There are two pairs of nodes that are not matched (on one side of the graph)
There are two vans (or deliveries) that are not matched to deliveries (or vans)
There are two vertices on the left (or two on the right) that have not been matched
Two vertices in set X and Y are unmatched (bod)

Examples for B0:

There are two unmatched nodes
There are two sets of unmatched nodes
Ther are two unmatched arcs in each set

So accept poor terminology (for example, point for vertex, side for set, etc.) but not incorrect terminology (arc for vertex, etc.) and accept contextualised answers (‘vans’ rather than ‘vertices’)

Mark scheme (b)

Scheme	Marks
B – 4 = C – 5	M1
D – 2 = A – 3 = F – 6 = E – 1	A1
	(2)

Notes

b1M1: One correct alternating path (accept any symbol connecting the vertices, for example, B – 4 – C – 5, or B4C5). Note that 5 – C = 4 – B and 1 – E = 6 – F = 3 – A = 2 – D (so paths from 5 to B and 1 to D) are fine

b1A1: Both paths correct (isw if more than two paths are stated)

Mark scheme (c)

Scheme	Marks
A = 3, (B unmatched), C = 4, D = 2, E = 5, F = 6	B1
	(1)

Notes

c1B1: CAO – condone lack of B or 1 being stated as unmatched. The improved matching may be stated or drawn – do check carefully the top of the second page for the improved matching drawn there. Only accept a clear diagram with exactly five arcs

Mark scheme (d)

Scheme	Marks
Alternating path: B – 4 = C – 5 = E – 1 Change status: B = 4 – C = 5 – E =1	M1
Complete matching: A = 3, B = 4, C = 5, D = 2, E = 1, F = 6	A1
	(2)
	(6 marks)

Notes

d1M1: The correct alternating path from B to 1 (or vice-versa) and then either (i) or (ii)

(i) the ‘change status’ either stated in words (but only accept ‘change (of) status’ or ‘c.s.’ not ‘change state’ etc.) OR shown (all symbols e.g. (…-…=…-…) interchanged (…=…-…=…).

(ii) the correct complete matching either stated or drawn – only accept a clear diagram with exactly six arcs – do check carefully the top of the second page for the complete matching drawn there.

d1A1: CAO – all three parts – the correct alternating path and the change status either stated or shown and the complete matching either stated or drawn