D1 June 2017 Q1

EdexcelOld spec10 marksAllocation

(a) Define the terms

(i) bipartite graph,

(ii) alternating path. (4)

Figure 1: bipartite graph joining guests A to F to rooms 1 to 6 — Figure 1

Figure 2: initial matching A to 1, B to 3, D to 4, E to 6 — Figure 2

At a hotel, six guests, A, B, C, D, E and F, are to be allocated to six rooms, 1, 2, 3, 4, 5 and 6. Each room needs to be allocated to exactly one guest.

A bipartite graph showing their possible allocations is given in Figure 1. An initial matching is given in Figure 2.

(b) Starting from the initial matching given in Figure 2, apply the maximum matching algorithm to find an alternating path from F to 5. Hence find an improved matching. You must list the alternating path that you use and state your improved matching. (3)

Guest C now has room 5 added to his possible allocations.

(c) Starting with the improved matching found in (b), apply the maximum matching algorithm to obtain a complete matching. You must list the alternating path that you use and state your complete matching. (3)

Mark scheme (a)

Scheme	Marks
(i) A bipartite graph consists of two sets of vertices X and Y	B1
The edges only join vertices in X to vertices in Y, not vertices within a set	B1
(ii) A path from an unmatched vertex in one set to an unmatched vertex in the other set which alternately uses arcs not in/in the matching	B1 B1
	(4)

Notes

ai1B1: Two sets of vertices – must contain the three words in bold – accept nodes for vertices but not points or any other non-technical language

ai2B1: (Edges) must go from one (set) into the other – candidates must give an indication of going from one set to the other – however, they do not need to use the word ‘set’ for this mark. Candidates do not need to mention that edges should not join vertices within a set but if a candidate does imply that a bipartite graph can join vertices within a set then withold this mark (no isw). If a candidate only says that you cannot connect nodes from the same set then this is B0. As an absolute minimum accept a statement along the lines of: ‘must go from one to the other’ – note that for this mark technical language may be absent or incorrect.

aii3B1: unmatched to unmatched (vertices do not need to be explicitly mentioned for this mark but B0 if arcs implied)

aii4B1: (alternate) arcs not in/in (not vertices/nodes) – must mention arcs/edges (not lines) and an understanding of what ‘alternating’ means in this context

Mark scheme (b)

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

Notes

SC: APs FROM F TO 2 AND FROM C TO EITHER 2 OR 5 - SEE NOTES

b1M1: An alternating path (e.g. letter 1st set – number 2nd set – letter 1st set – …) from F to 5 or vice-versa

b1A1: CAO – a correct path including change status either stated (only accept ‘change (of) status’ or ‘c.s’ but not, e.g.‘change state’) or shown (all symbols e.g. (… – … = … – …) interchanged (… = …. – … = …)) Chosen path clear

e.g.

F * 1 = A * 3 = B * 4 = D * 6 = E * 5
F = 1 * A = 3 * B = 4 * D = 6 * E = 5 scores M1A1 (change status shown)
change status F – 1 = A – 3 = B – 4 = D – 6 = E – 5 scores M1A1 (change status stated)
c.s. F – 1 = A – 3 = B – 4 = D – 6 = E – 5 scores M1A1 (change status stated)
F – 1 = A – 3 = B – 4 = D – 6 = E – 5
c.s. F = 1 – A = 3 – B = 4 – D = 6 – E = 5 scores M1A1 (change status stated and shown)
F – 1 = A – 3 = B – 4 = D – 6 = E – 5
F = 1, A = 3, B = 4, … scores M1A0 (no change status stated or shown)

b2A1: CAO – improved matching - must follow from the correct stated path. Accept either stated or on a clear diagram (with five arcs only). Please check the top of the second page as many candidates will draw either the improved or complete matching on the nodes provided there

Mark scheme (c)

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

Notes

c1M1: A second alternating path from C to 2 or vice-versa

c1A1: CAO – a correct path including change status stated or shown. Chosen path clear

c2A1: CAO (complete matching) must follow from two correct stated paths (so both previous M marks must have been awarded). Accept on a clear diagram (with six arcs only)

Special Cases for (b) and (c):Alternating path from F to 2

Candidates who find an alternating path from F to 2 can score in (b)

M1 for an alternating path from F to 2 (or vice-versa),

A1 for the correct alternating path (F – 1 = A – 3 = B – 2) and change of status (stated or shown)

A1 for the correct improved matching of A = 3, B = 2, D = 4, E = 6, F = 1 from the correct stated path

In (c) the alternating path is simply C – 5 and therefore no marks in (c) – so an alternating path from F to 2 can score a maximum of three marks (of the six available) in (b) and (c)

Alternating path from either C to 2 or C to 5

Candidates who find in (b) an alternating path from either C to 2 or C to 5 can score in (b)

M1 for an alternating path from either C to 2 or C to 5

A1 for either C – 3 = B – 2 or C – 3 = B – 4 = D – 6 = E – 5 together with the change of status (either stated or shown)

In (c)

M1 for either F – 1 = A – 3 = C – 5 (following their path fom C to 2) or F – 1 = A – 3 = C – 5 = E – 6 = D – 4 = B – 2 (following their path from C to 5)

So both special cases can score a maximum of three marks (of the six available in (b) and (c))