ChApTeR 10
■
MATChINgs, CuTs, ANd Flows
211
graph in Figure
10-1
. Let’s say that in our first two iterations,
a gives a ring to
e, and
c gives one to
g. This gives us a
tentative matching consisting of two pairs (indicated by the heavy black edges). Now we turn to
b. What is he to do?
Let’s follow a strategy somewhat similar to the Gale-Shapley algorithm mentioned in Chapter 7, where the
women can change their minds when approached by a new suitor. In fact, let’s mandate that they
always do. So when
b asks
g, she returns her current ring to
c, accepting the one from
b. In other words, she
cancels her
engagement to
c. (This idea of canceling is crucial to all the algorithms in this chapter.) But now
c is single, and if we are to ensure that
the iteration does indeed lead to improvement, we can’t accept this new situation. We immediately look around for
a new mate for
c, in this case
e. But if
c passes his returned ring to
e, she has to cancel her engagement to
a, returning
his ring. He in turn passes this on to
f, and we’re done. After this
single zigzag swapping session, rings have been
passed back and forth along the highlighted edges. Also, we now have increased the number of couples from two to
three (
a +
f,
b +
g, and
c +
e).
We can, in fact, extract a general method from this ad hoc procedure. First, we need to find one unmatched man.
(If we can’t, we’re done.) We then need to find some alternating sequence of engagements and cancellations so that
we
end with an engagement. If we can find that, we know that there must have been one more engagement than there
were cancellations, increasing the number of pairs by one. We just keep finding such zigzags for as long as we can.
The zigzags we’re looking for are
paths that go from an unmatched node on the left side to an unmatched node
on the right side. Following the logic of the engagement rings, we see that the path can only move to the
right across an
edge that is
not already in the matching (a proposal),
and it can only move left across one that
is in the matching
(a cancellation). Such a path (like the one highlighted in Figure
10-1
) is called an
augmenting path, because it augments
our solution (that is, it increments the engagement count), and we can find augmenting paths by traversal. We just need
to be sure we follow the rules—we can’t follow matched edges to the right or unmatched edges to the left.
What’s left is ensuring that we can indeed find such augmenting paths as long as there is room for improvement.
Although this seems plausible enough, it’s not immediately obvious why it
must be so. What we want to show is that
if there is room for improvement, we can find an augmenting path. That means that we have a current match
M and
that there is some greater matching
M’ that we haven’t found yet. Now consider the edges in the
symmetric difference
between these two—that is, the edges that are in either one but not in both. Let’s
call the edges in M red and the ones
in
M’ green.
This jumble of red and green edges would actually have some useful structure. For example, we know that each
node would be incident to at most two edges, one of each color (because it couldn’t have two edges from the same
matching). This means that we’d have one or more connected components, each of which was a zigzagging path or
cycle of alternating color. Because
M’ is bigger than
M, we must have at least one component with more green than
red edges, and the only way that could happen would be in a path—an odd-length one that
started and ended with
a green edge.
Do you see it yet? Exactly! This green-red-…-green path would be an augmenting path. It has odd length, so one
end would be on the male side and one on the female. And the first and last edges were green, meaning they were
not
part of our original matching, so we’re free to start augmenting. (This is essentially my take on what’s known as Berge’s
lemma.)
When it comes to implementing this strategy, there is a lot of room for creativity. One possible implementation
is shown in Listing 10-1. The code for the tr function can be found in Listing 5-10. The parameters X and Y are
collections (iterable objects) of nodes, representing the bipartition of the graph G. The running time might not be
obvious, because edges are switched on and off during execution, but we
do know that
one pair is added to the
matching in each iteration, so the number of iterations is
O(
n), for
n nodes. Assuming
m edges, the search for an
augmenting path is basically a traversal of a connected component, which is
O(
m). In total, then, the running time
is
O(
nm).
