Pages in this set

Page 1

Preview of page 1


You are given a list of n "jobs" and n "people" together with
their preferences and, usually, an initial matching. You have to
assign the "jobs" to the "people" so that all the "jobs" are being
done by "people" who are prepared to do them. (Sometimes
known as…

Page 2

Preview of page 2

A matching in a bipartite graph is a subset of edges such that
no two edges have a common vertex.

Initially Andrew, Donna, Henry and Karl are matched to the
first task in their individual lists. This can be shown on the
bipartite graph in a distinctive way by…

Page 3

Preview of page 3


It joins an unmatched vertex on the left to an unmatched
vertex on the right. The edges in the path are alternately in
and not in the matching.
The edges you go along from left to right are not currently in
the initial matching but the ones…

Page 4

Preview of page 4

On an alternating path, the number of edges not in M is one
more than the number of edges in M.
We change the status of all the edges in the alternating path.
Those that were in the matching are now not to be used whilst
those that were…

Page 5

Preview of page 5


This improves an existing matching, if possible, by first
establishing an alternating path between vertices not in the
current matching. The status of the edges are then changed to
produce an improved matching.
(If the current matching is maximal, no alternating path will be

Page 6

Preview of page 6


Returning to the college dramatic society and the initial

Step 1

Step 2 As N is unmatched, we use N as the starting point
of an alternating path.

We choose one of the possibilities (in this case ending at M)

N S = K L = H…

Page 7

Preview of page 7

This now gives us the following matching:

Returning to step 2, we choose Y as it is unmatched.

Y L = K W = A P

c.s. Y = L K = W A = P

Add YL, KW & AP
Remove LK & WA (Leave DT & HM)…

Page 8

Preview of page 8

So, Andrew does Props
Donna does Tickets
Henry does Make-up
Karl does Wardrobe
Nicola does Sound
Yana does Lighting

Problem solved!


Remember to state which people are doing which jobs at the

If more than one alternating path has to be found (because
there is more than…

Page 9

Preview of page 9


The diagram represents eight seats in a railway carriage, which
are numbered 1, 2, 3, 4, 5, 6, 7, 8. These are the last eight
seats available on a special sightseeing trip. The booking clerk
has to arrange the seating for the final customers.

Six customers make the…

Page 10

Preview of page 10

Hence E 5 = B 4 = C 3

c.s. E = 5 B = 4 C = 3

Add E5, B4 & C3
Remove 5B & 4C




A useful presentation of the Matchings method, explanations given as well as a worked example showing the alternating paths.

Similar Mathematics resources:

See all Mathematics resources »See all resources »