D1 Alternating Path Algorithms

I really can't do this question!! Any help much appreciated :smile:

Four friends, Alan, Bill, Clare, Diane, share a Chinese take-away. Alan likes duck and pork, Bill likes pork and chicken, Clare likes duck, pork and beef, whilst Diane only likes pork

(A) model this question with a bipartite graph

(B) The group purchase one portion each of duck, pork, chicken and beef. Starting from Alan and Bill's first-named preferences, use the alternating path algorithm twice to find a complete matching. Explain clearly how the alternating path is used.

I have done part (A) :

but I can't do part (B) at all. I just don't understand how to do it and the need to use the alternating path algorithm twice :confused:

(edited 11 years ago)

OP

anyone?

Original post by calla_lily

The group purchase one portion each of duck, pork, chicken and beef. Starting from Alan and Bill's first-named preferences...

so that means Alan gets Duck and Bill gets Pork. Assume Clare gets Beef for an initial matching:

A ---- D
B ---- P
C _ ...C
D ...\_ B

Then you start on a node not included, and go along a path that is not included, then one that is included (i.e. alternating path). You keep going until you reach a node that wasn't included again. Record this path

.... not included in initial matching
---- included

Diane .... Pork ---- Bill .... Chicken

Then change all the lines so that the ones that were included, now are not, and vice versa

Diane ---- Pork .... Bill ---- Chicken

This changes the matching to something like this

A ---- D
B _ .. _P
C _\/_ C
D _/\_ B

You do the second one :wink:

Reply 3

calla_lily

OP

11

Original post by njl94

so that means Alan gets Duck and Bill gets Pork. Assume Clare gets Beef for an initial matching:

A ---- D
B ---- P
C _ ...C
D ...\_ B

Then you start on a node not included, and go along a path that is not included, then one that is included (i.e. alternating path). You keep going until you reach a node that wasn't included again. Record this path

.... not included in initial matching
---- included

Diane .... Pork ---- Bill .... Chicken

Then change all the lines so that the ones that were included, now are not, and vice versa

Diane ---- Pork .... Bill ---- Chicken

This changes the matching to something like this

A ---- D
B _ .. _P
C _\/_ C
D _/\_ B

You do the second one :wink:

thanks!!

but I still don't see the need to do this twice to find a complete matching???

(edited 11 years ago)

Reply 4

username602917

9

oh yeah, didn't actually think about that..
well you can get a complete matching in one, so even better!
I can only guess the question is wrong, or the initial matching I used wasn't the one they used

Reply 5

calla_lily

OP

11

Original post by njl94

oh yeah, didn't actually think about that..
well you can get a complete matching in one, so even better!
I can only guess the question is wrong, or the initial matching I used wasn't the one they used

It was the question that confused me in the first place as I didn't see the point of doing two. I think the question is at fault, blame my teacher!! :tongue:

thanks anyway

D1 Alternating Path Algorithms

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you