Pages in this set

Page 1

Preview of page 1
SLBS




MATCHINGS

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
SLBS




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
SLBS




ALTERNATING PATHS

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
SLBS




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
SLBS




THE MAXIMUM MATCHING ALGORITHM

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
found)…

Page 6

Preview of page 6
SLBS




Example

Returning to the college dramatic society and the initial
matching:

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
SLBS




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
SLBS




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

Problem solved!


Note:

Remember to state which people are doing which jobs at the
end!

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

Page 9

Preview of page 9
SLBS




Example


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
SLBS




Hence E 5 = B 4 = C 3

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

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





10
JMcC

Comments

daviesg

Report

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 »