Matchings (Decision Maths)

Everything you need to know about matchings!

HideShow resource information
  • Created by: Jackarias
  • Created on: 01-06-10 09:59
Preview of Matchings (Decision Maths)

First 162 words of the document:

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 "The Marriage Problem")
Example
A college dramatic society has six helpers:
Andrew, Donna, Henry, Karl, Nicola and Yana.
They are to be matched to six tasks:
Props, Lighting, Make-up, Sound, Tickets and Wardrobe.
The table indicates which tasks each person is able to do.
Name Tasks
Andrew Wardrobe, Props, Tickets
Donna Tickets, Make-up
Henry Lighting, Make-up
Karl Sound, Wardrobe, Lighting
Nicola Sound
Yana Lighting, Tickets
(Read pp 195-198)
Ex 7A pp 198-200
1
JMcC

Other pages in this set

Page 2

Preview of page 2

Here's a taster:

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 either using coloured
pencils or a `squiggly' line.
A maximal matching is a matching in which the number of
edges is as large as possible. e.g.…read more

Page 3

Preview of page 3

Here's a taster:

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 you go along from right to left
are the ones currently in the initial matching. e.g.…read more

Page 4

Preview of page 4

Here's a taster:

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 not in the matching now are to be used.…read more

Page 5

Preview of page 5

Here's a taster:

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.…read more

Page 6

Preview of page 6

Here's a taster:

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 M
Step 3 Change status (c.s. is an accepted abbreviation)
c.s.…read more

Page 7

Preview of page 7

Here's a taster:

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)
Hence matching becomes:
This is now a complete maximal matching.…read more

Page 8

Preview of page 8

Here's a taster:

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 one unmatched person), then the next
alternating path must take into account the new matching
formed by previous alternating paths.
Alternating paths must be listed clearly.…read more

Page 9

Preview of page 9

Here's a taster:

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 following requests.…read more

Page 10

Preview of page 10

Here's a taster:

SLBS
Hence E 5 = B 4 = C 3
c.s.…read more

Comments

daviesg

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 »