8. A crucial observation is that for any edge between a leaf and its parent
there is a maximum matching containing this edge. Indeed, consider a
leaf and its parent .Letbe a maximum matching in the tree. If
()is in ,wehaveamaximummatchingdesired. Ifdoes not
include ( ), it must contain an edge ( )from some vertex 6=to
Thieling Chen [Thieling Chen, “Maximum Matching and Minimum Vertex
Covers of Trees,” The Western Journal of Graduate Research, vol. 10, no.
1, 2001, pp. 10-14] suggested to implement the same idea by processing
vertices of the tree in the reverse BFS order (i.e., bottom up and right to
left across each level) as in the following pseudocode:
Algorithm Tree–Max–Matching
//Constructs a maximum matching in a free tree
//Input: A tree
10. No domino tiling of such a board is possible. Think of the board as being
an 8×8chessboard (with two missing squares at the diagonally opposite
Exercises 10.4
1. Consider an instance of the stable marriage problem given by the following
ranking matrix:
2. Design a simple algorithm for checking whether a given marriage matching
is stable and determine its time efficiency class.
3. Find a stable-marriage matching for the instance given in Problem 1 by
applying the stable-marriage algorithm
5. Determine the time-efficiency class of the stable-marriage algorithm
(a) in the worst case.
(b) in the best case.
6. Prove that a man-optimal stable marriage set is always unique. Is it also
true for a woman-optimal stable marriage matching?
33
10. BConsider the problem of the roommates, which is related to but more
difficult than the stable marriage problem: “An even number of boys wish
Hints to Exercises 10.4
1. A marriage matching is obtained by selecting three matrix cells, one cell
2. It suffices to consider each member of one sex (say, the men) as a potential
member of a blocking pair.
3. An application of the men-proposing version to another instance is given
4. You may use either the men-proposing or women-proposing version of the
algorithm.
5.Thetimeefficiency is clearly defined by the number of proposals made.
6. Prove it by contradiction.
7. Prove it by contradiction.
35
Solutions to Exercises 10.4
1. There are the total of 3! = 6 one-one matchings of two disjoint 3-element
sets:
1,3 2231
311,3 22
22311,3
{( )( )()}is unstable: ( )is a blocking pair.
132,2 31
31132,2
2,2 3113
36
{( )()( )}is stable: no other cell can be blocking since each
woman has her best choice. This is obviously the woman-optimal match-
ing.
2. Stability-checking algorithm
Input: A marriage matching of ( )pairs along with rankings of
the
women by each man and rankings of the men by each woman
Output: “yes” if the input is stable and a blocking pair otherwise
3. a.
Free men:
1,3 2231
311322
223113
proposed to
accepted
The (man-optimal) stable marriage matching is ={( )()()}
b.
Free women:
132231
3,1 1322
223113
proposed to
accepted
38
4.
iteration 1
Free men:
iteration 2
Free men:
iteration 3
Free men:
1,3 233243
1441342,2
22143341
41223114
proposed to ;accepted
iteration 4
Free men:
1,3 233243
1441342,2
221,4 3341
41223114
proposed to ;accepted
iteration 7
Free men:
13233243
1441342,2
2,2 143341
412,2 3114
proposed to ;replaced with
iteration 8
Free men:
13233243
1441342,2
2,2 143341
412,2 3114
proposed to ;rejected
iteration 9
5. a. The worst-case time efficiency of the algorithm is Θ(2)On the one
hand, the total number of the proposals, ()cannot exceed 2the total
number of possible partners for men, because a man does not propose
to the same woman more than once. On the other hand, for the instance
6. Assume that there are two distinct man-optimal solutions to an instance
of the stable marriage problem. Then there must exist at least one man
7. Assume that on the contrary there exists a man-optimal stable matching
in which some woman doesn’t have the worst possible partner in a
8. n/a
40
rating):
boy rank 1 rank 2 rank 3
∗∗∗
Any pairing would have to pair one of the boys with But any
such pairing would be unstable since whoever is paired with will want to
Press, 1989.
41