Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
error in proof about order of matching A in bipartite matching? | Reply
in the second part when talking about the graduation problem it says

It is important to understand that any order to iterate through set A can be considered when solving the standard bipartite-matching problem. For example, it doesn't matter what element from set A we choose to be the first one to be matched. Consider the solution found by the algorithm containing this element x from A, matched with an element y from B. Also, we should consider any optimal solution. Clearly, in the optimal, y must be matched with an element z from A, otherwise we can add the pair x-y to the matching, contradicting the fact that the solution is optimal. Then, we can just exchange z with x to come with a solution of the same cardinality, which completes the proof.

Let A have one element a. Let B have 2 elements b, c. Let there be the paths a->b and a->c. there are 2 maximal matchings a->b and a->c. pick one of them say a->b. x=a y=b. now in the other optimal solution a->c b is not matched but according to the proof it must be. am i missing something?
Re: error in proof about order of matching A in bipartite matching? (response to post by oog) | Reply
In your example both optimal solutions involve x. The point of the proof is that, if some vertex is left out in a solution found by the algorithm, but there exists an optimal solution that contains it, we can modify our solution in order to contain the left-out vertex.

Obviously the solution to a maximum bipartite matching problem is not unique, so there may be vertices matched in an optimal solution, but not matched in another one (both in sets A and B).