Slides in this set

Slide 1

Preview of page 1

MATCHINGS
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 more

Slide 2

Preview of page 2

As YN is
is unmatched,
unmatched, we
we use
use Y
Nas
asthe
thestarting
startingpoint
pointof
ofan
analternating
alternatingpath
path.
Initially, Andrew, Donna,
This Henry & Karl
is represented by are
thematched
followingto the first
Bipartite task in their list.
Graph:
Y
N -- S L = K K --L W = =H A M -- P BREAKTHROUGH
Change status Y
N = = L S ---- K K = = W -- H
L -- A =
= MP
NWecan do Sthe
apply
Salgorithm onceby K
is being done
Add YL,
NS,KW,
KL, HM
AP more to improve
K can
the do L
matching
Remove LK,
SK, WA
LH L is being done by H
H can do M
BREAKTHROUGH
This is a maximal
matching
All 6 people arehave
We now now 5
matched to 6 different jobs
people matched…read more

Slide 3

Preview of page 3

Remember to state the final matching when you have finished
Andrew ­ Props
Donna ­ Tickets
Henry ­ Make-up
Karl ­ Wardrobe
Nicola ­ Sound
Yana - Lighting…read more

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »