D1 June 2016 Q1

EdexcelOld spec5 marksAllocation

Figure 1: bipartite graph joining L, M, N, P, T to activities A to E — Figure 1

Figure 2: initial matching L to D, M to C, N to A, T to E — Figure 2

(a) Define the term ‘bipartite graph’. (2)

Figure 1 shows the possible allocations of five people, Larry (L), Monisha (M), Nina (N), Phil (P) and Theo (T), to five activities, A, B, C, D and E.

Figure 2 shows an initial matching.

(b) Starting from this initial matching, use the maximum matching algorithm to find a complete matching. You should list the alternating path you use and state your complete matching. (3)

Mark scheme (a)

Scheme	Marks
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
	(2)

Notes

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

a2B1: (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). 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

Mark scheme (b)

Scheme	Marks
Alternating path: P – A = N – E = T – D = L – C = M – B	M1
Change status: P = A – N = E – T = D – L = C – M = B	A1
Complete matching: L = C, M = B, N = E, P = A, T = D	A1
	(3)
	(5 marks)

Notes

b1M1: An alternating path (e.g. letter 1st set – letter 2nd set – letter 1st set – …) from P to B 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.

P * A = N * E = T * D = L * C = M * B
P = A * N = E * T = D * L = C * M = B scores M1A1 (change status shown)
change status P = A – N = E – T = D – L = C – M = B scores M1A1 (change status stated)
c.s. P = A – N = E – T = D – L = C – M = B scores M1A1 (change status stated)
P – A = N – E = T – D = L – C = M – B
c.s. P = A – N = E – T = D – L = C – M = B scores M1A1 (change status stated and shown)
P – A = N – E = T – D = L – C = M – B
P = A, N = E, T = D, … scores M1A0 (no change status stated or shown)

b2A1: CAO – must follow from the correct stated path. Accept either stated or on a clear diagram (with five arcs only)