Content deleted Content added
→Algorithm: separate out alternating path description into a new section |
→Alternating paths: relation to flow |
||
Line 16:
Conversely, suppose that a matching ''M'' is not optimal, and let ''P'' be the symmetric difference ''M'' ⊕ ''M''* where ''M''* is an optimal matching. Then ''P'' must form a collection of disjoint cycles and alternating paths; the difference in size between ''M'' and ''M''* is the number of paths in ''P''. Thus, if no alternating path can be found, an algorithm may safely terminate, since in this case ''M'' must be optimal.
An alternating path is closely related to an [[augmenting path]], a path in a [[maximum flow]] problem that increases the amount of flow between the terminals of the flow. It is possible to transform the bipartite matching problem into a maximum flow instance, such that the alternating paths of the matching problem become augmenting paths of the flow problem. The Hopcroft–Karp algorithm may be generalized to problems of maximum flow on unweighted graphs, but is not as efficient in that generalization as it is for bipartite matching.
==Algorithm==
| |||