Content deleted Content added
names with initial caps |
→Augmenting paths: explain how a bipartite matching problem can be transformed into a network flow problem |
||
Line 12:
Conversely, suppose that a matching <math>M</math> is not optimal, and let <math>P</math> be the symmetric difference <math>M \oplus M^*</math> where <math>M^*</math> is an optimal matching. Because <math>M</math> and <math>M^*</math> are both matchings, every vertex has degree at most 2 in <math>P</math>. So <math>P</math> must form a collection of disjoint cycles, of paths with an equal number of matched and unmatched edges in <math>M</math>, of augmenting paths for <math>M</math>, and of augmenting paths for <math>M^*</math>; but the latter is impossible because <math>M^*</math> is optimal. Now, the cycles and the paths with equal numbers of matched and unmatched vertices do not contribute to the difference in size between <math>M</math> and <math>M^*</math>, so this difference is equal to the number of augmenting paths for <math>M</math> in <math>P</math>. Thus, whenever there exists a matching <math>M^*</math> larger than the current matching <math>M</math>, there must also exist an augmenting path. If no augmenting path can be found, an algorithm may safely terminate, since in this case <math>M</math> must be optimal.
An augmenting path in a matching problem is closely related to the [[augmenting path]]s arising in [[maximum flow problem]]s, paths along which one may increase 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. It suffices to insert two vertices, source and sink, and insert edges of infinite capacity from the source to each vertex in <math>U</math>, and from each vertex in <math>V</math> to the sink; and let edges from <math>U</math> to <math>V</math> have unit capacity.<ref>{{harvtxt|Ahuja|Magnanti|Orlin|1993}}, section 12.3, bipartite cardinality matching problem, pp. 469–470.</ref>
==Algorithm==
| |||