174 10. Matchings in Graphs
If we find an augmenting pathP, we can delete those edges ofPthat are
inMand replace them by those edges ofPthat are not inM. It is clear
that this results in a matchingM′that is larger thanMby one edge. (The
fact thatM′is a matching follows from the observation that the remaining
edges ofMcannot contain any node ofP: The two endpoints ofP were
supposed to be unmatched, while the interior nodes ofPwere matched by
edges ofMthat we deleted.) So we can repeat this until we get either a
perfect matching or a matchingMfor which no augmenting path exists.
So we have two questions to answer: how do we find an augmenting path
if it exists? And if it does not exist, does this mean that there is no perfect
matching at all? It will turn out that an answer to the first question will
also imply the (affirmative) answer to the second.
LetU be the set of unmatched nodes inAand letW be the set of
unmatched nodes inB. As we noted, any augmenting path must have an
odd number of edges, and hence it must connect a node inUtoanodein
W. Let us try to find such an augmenting path starting from some node in
U. Let’s say that a pathQisalmost augmentingif it starts at a node inU,
ends at a node inA, and every second edge of it belongs toM. An almost
augmenting path must have an even number of edges, and must end with
an edge ofM.
What we want to do is to find the set of nodes inAthat can be reached
on an almost augmenting path. Let’s agree that we consider a node inU
to be an almost augmenting path in itself (of length 0); then we know that
every node inUhas this property. Starting withS=U, we build up a set
Sgradually. At any stage, the setSwill consist of nodes we already know
are reachable by some almost augmenting path. We denote byTthe set
of nodes inBthat are matched with nodes inS(Figure 10.7). Since the
nodes ofUhave nothing matched with them and they are all inS,wehave
|S|=|T|+|U|.We look for an edge that connects a nodes∈Sto some noder∈Bthat
isnotinT. LetQbe an almost augmenting path starting at some node
u∈Uand ending ats. Now there are two cases to consider:
—Ifris unmatched (which means that it belongs toW), then by ap-
pending the edgesrtoQwe get an augmenting pathP.Sowecan
increase the size ofM(and forget aboutSandT).—Ifris matched with a nodeq∈A, then we can append the edgessr
andrqtoQto get an almost augmenting path fromUtoq.Sowe
can addqtoS.So if we find an edge connecting a node inSto a node not inT,wecan
increase either the size ofMor the setS(and leaveMas it was). Sooner or
later we must encounter a situation where eitherMis a perfect matching