D1 June 2006 Q2

EdexcelOld spec7 marksAllocation

(a) Define the term ‘alternating path’. (2)

Figure 1: bipartite graph joining customers Adam (A), Daniela (D), Henry (H), Min-Seong (M), Robert (R), Sam (S) to films B, C, F, K, P, Y; bold lines A-B, D-C, H-Y, M-F show the initial matching — Figure 1

The bipartite graph in Figure 1 shows the films that six customers wish to hire this Saturday evening. The shop has only one copy of each film. The bold lines indicate an initial matching.

(b) Starting from this initial matching use the maximum matching algorithm twice to obtain a complete matching. You should clearly state the alternating paths you use. (5)

Mark scheme (a)

Scheme	Marks
A path from an unmatched vertex in \(X\) to an unmatched vertex in \(Y\), which alternately uses arcs in/not in the matching. (where \(X\) and \(Y\) are distinct sets of vertices.)	B2,1,0
	(2)

Notes

B2 A good, complete answer

B1 Partially correct – unmatched to unmatched or arcs in/not in the matching are enough. ‘bod’ gets B1

Mark scheme (b)

Scheme	Marks
e.g. \(R - B = A - P\) c.s. \(R = B - A = P\)	M1 A1 (2)
\(S - F = M - C = D - K\) c.s. \(S = F - M = C - D = K\)	M1 A1
\(\therefore\ A = P\quad D = K\quad H = Y\quad M = C\quad R = B\quad S = F\)	A1 (3)
	(5)
	(7 marks)

Notes

M1 Path from/to \(R\)/\(S\) to/from \(K\)/\(P\)

A1 c.a.o. incl c.s.

M1 Second path from remaining LH vertex to remaining RH vertex (depends on the first M1)

A1 c.a.o. incl. c.s. (Penalise c.s. only once)

A1 Must ft from 2 correct paths c.a.o.