Chapter 11 Simple Graphs448
Family Children
Grinches: Zippy, Dingdong, Bottlecap, Lucy
Hatfields: Zippy, Bottlecap, Dingdong, Lucy
Scrooges: Bottlecap, Lucy, Dingdong, Zippy
McCoys: Lucy, Zippy, Bottlecap, Dingdong(a)Exhibit two different stable matching of Children and Families.
Family Child in 1st match Child in 2nd match
Grinches:
Hatfields:
Scrooges:
McCoys:(b)Examine the matchings from part a, and explain why these matchings are the
only two possible stable matchings between Children and Families.
Hint:In general, there may be many more than two stable matchings for the same
set of preferences.
Problem 11.29.
The Mating Ritual 11.6 for finding stable marriages works without change when
there are at least as many, and possibly more, men than women. You may assume
this. So the Ritual ends with all the women married and no rogue couples for these
marriages, where an unmarried man and a married woman who prefers him to her
spouse is also considered to be a “rogue couple.”
Let Alice be one of the women, and Bob be one of the men. Indicate which of
the properties below that are preserved invariants of the Mating Ritual 11.6 when
there are at least as many men as women. Briefly explain your answers.
(a)Alice has a suitor (man who is serenading her) whom she prefers to Bob.(b)Alice is the only woman on Bob’s list.(c)Alice has no suitor.(d)Bob prefers Alice to the women he is serenading.(e)Bob is serenading Alice.(f)Bob is not serenading Alice.(g)Bob’s list of women to serenade is empty.