Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This tutorial (page 22) on Hopcroft-Karp algorithm for maximum bipartite matching states the following:

Let $M^*$ be a maximum matching, and let $M$ be any matching in $G = (V, E)$. ...

Let us consider the graph $G'=(V, M \oplus M^*)$. It contains at most $|M^*|-|M|$ augmenting paths with respect to $M$.

Here $M\oplus M^*$ is the symmetric difference between $M$ and $M^*$. But how does the last line (It contains at most $|M^*|-|M|$ augmenting paths with respect to $M$) follow?

share|improve this question
1  
Each augmenting path increases the size of the matching by $1$. –  Andrew Salmon May 26 '13 at 7:15
    
@AndrewSalmon But how does it prove the statement? Can you explain a bit more? –  f.nasim May 26 '13 at 10:32
1  
The size of the matching $M$ is $|M|$. So you're starting with size $|M|$--then, each augmenting path can increase the size of the matching by $1$, so after $|M^*| - |M|$ augmenting paths there are $|M| + |M^*| - |M| = |M^*|$ augmenting paths. There can't be more, because $M^*$ is a maximum matching. –  Andrew Salmon May 26 '13 at 18:41
    
@AndrewSalmon Got it. –  f.nasim May 27 '13 at 4:50

1 Answer 1

up vote 2 down vote accepted

Post intended to take this question off the "unanswered" list


Each augmenting path increases the size of the matching by $1$.

The size of the matching $M$ is $|M|$. So you're starting with size $|M|$: then, each augmenting path can increase the size of the matching by $1$, so after $|M^∗|−|M|$ augmenting paths there are $|M|+|M^∗|−|M|=|M^∗|$ augmenting paths. There can't be more, because $M^∗$ is a maximum matching.

share|improve this answer
    
Thanks for your answer. –  f.nasim Jun 10 '13 at 11:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.