Other slides in this set

Slide 2

Preview of page 2

Here's a taster:

Matchings
Bipartite graphs
We can represent this situation using a bipartite graph. This is a graph with
two distinct sets; the friends and the chocolates. The edges only go from a
vertex in one set to a vertex in the other; in this case where the person likes
that particular chocolate.
Ana R. raspberry rage
Baz T. truffle tickle
Carl N. nut nibble
Dee S. strawberry supreme
Ellie W. walnut whirl
Freya M. marshmallow melt
Anna
Freya
Baz likes
Carl
Dee
Ellie likes
likes
likes
strawberry
truffle
nut
strawberry
raspberry
nibble rage
tickle,
and
rage, and
supreme
supreme
nut marshmallow
marshmallow
truffle
nibble
andtickle
and melt
marshmallow
walnut
melt
and strawberry
whirl
melt supreme…read more

Slide 3

Preview of page 3

Here's a taster:

Initial Matching
If we now pair people with particular chocolates they like in a one-to-one way
(no two people to the same chocolate, no two chocolates to one person) then
we have a matching.
A R. If a matching includes the same
number of edges as vertices in each
B T. set (6 in this case) then it is called a
complete matching.
C N. The diagram shows the matching
D S. A-R, B-S, C-N, D-T, E-M
E W. THIS MATCHING IS NOT COMPLETE
F M.…read more

Slide 4

Preview of page 4

Here's a taster:

Matchings
Alternating paths
If we have a matching and want to improve it we can do so by finding an
alternating path. This is a path which
(a) Starts on an unmatched vertex on the right hand side [W]
(b) Consists of edges alternately not in and in the matching
(c) Finishes on an unmatched vertex in the second set
A R. Start with W
join to W to D
B T.
Now remove D-T
C N. T now has no match so include T-F
D S. F was previously unmatched, so we have
now have breakthrough.
E W. The alternating path is W-D-T-F
F M. Every vertex is now matched so we have
a complete matching…read more

Slide 5

Preview of page 5

Here's a taster:

Matchings
Alternating paths
The solution consists of
1. Edges in the alternating path but not in the initial matching;
D-W and F-T
2. Edge in the initial matching but not in the alternating path;
A-R, B-S, C-N and E-M
A R. Interpretation:
Ann has raspberry rage
B T.
Baz has strawberry supreme
C N. Carl had nut nibble
D S. Dee has walnut whirl
Ellie has marshmallow melt
E W.
Freya has truffle tickle.
F M.…read more

Comments

No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all resources »