# Matchings: 2 of 2 (Decision Maths)

Visual Powerpoint to explain matchings. There's also a Word Document that might suit your learning style more.

- Created by: Jackarias
- Created on: 01-06-10 10:14

## Slides in this set

### Slide 1

Matchings

Example

Freya buys some chocolates to share with her friends. There

are six chocolates raspberry rage (R) , truffle tickle (T), nut

nibble (N), strawberry supreme (S), walnut whirl (W) and

marshmallow melt (M). Of her friends, Ann likes raspberry

rage and marshmallow melt; Baz likes strawberry supreme;

Carl likes nut nibble and marshmallow melt; Dee likes truffle

tickle, nut nibble and walnut whirl; and Ellie likes strawberry

supreme and marshmallow melt. Freya herself likes

raspberry rage, truffle tickle and strawberry supreme.

Can they each have a chocolate they like?…read more

### Slide 2

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

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

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

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

## Related discussions on The Student Room

- Decision 1 matchings help! »
- Edexcel AS Mathematics: Decision Maths D1 6689 01 - 15 ... »
- Aqa decision 2 wednesday 24th june 2015 »
- Edexcel Mathematics: Decision Mathematics D1 (Not IAL) 16 ... »
- D1 (Decision 1) 17 May 2013 Official Thread »
- AQA AS Mathematics (Old Spec) - Decision 1 MD01 - 22 June ... »
- AQA AS Mathematics MD01 Decision 1 ? Tuesday 16th June ... »
- AQA D1 Decision 1 (MD01) on 24th May 2013 - Official ... »
- AQA Mathematics MD01 Decision 1 ? Friday 24th June [Exam ... »
- Edexcel A2 C4 Mathematics June 2015 - Official Thread »

## Similar Mathematics resources:

# Matchings: 2 of 2 (Decision Maths)

Visual Powerpoint to explain matchings. There's also a Word Document that might suit your learning style more.

- Created by: Jackarias
- Created on: 01-06-10 10:14

## Slides in this set

### Slide 1

Matchings

Example

Freya buys some chocolates to share with her friends. There

are six chocolates raspberry rage (R) , truffle tickle (T), nut

nibble (N), strawberry supreme (S), walnut whirl (W) and

marshmallow melt (M). Of her friends, Ann likes raspberry

rage and marshmallow melt; Baz likes strawberry supreme;

Carl likes nut nibble and marshmallow melt; Dee likes truffle

tickle, nut nibble and walnut whirl; and Ellie likes strawberry

supreme and marshmallow melt. Freya herself likes

raspberry rage, truffle tickle and strawberry supreme.

Can they each have a chocolate they like?…read more

### Slide 2

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

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

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

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:

## Related discussions on The Student Room

- Decision 1 matchings help! »
- Edexcel AS Mathematics: Decision Maths D1 6689 01 - 15 ... »
- Aqa decision 2 wednesday 24th june 2015 »
- Edexcel Mathematics: Decision Mathematics D1 (Not IAL) 16 ... »
- D1 (Decision 1) 17 May 2013 Official Thread »
- AQA AS Mathematics (Old Spec) - Decision 1 MD01 - 22 June ... »
- AQA AS Mathematics MD01 Decision 1 ? Tuesday 16th June ... »
- AQA D1 Decision 1 (MD01) on 24th May 2013 - Official ... »
- AQA Mathematics MD01 Decision 1 ? Friday 24th June [Exam ... »
- Edexcel A2 C4 Mathematics June 2015 - Official Thread »

## Comments

No comments have yet been made