Content deleted Content added
→Analysis: reword difference to be more explicit what kind of difference we mean |
→Analysis: +teh |
||
Line 28:
Therefore, the first √''n'' phases, in a graph with ''n'' vertices and ''m'' edges, take time O(''m'' √''n'').
It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial √''n'' phases of the algorithm are complete, the shortest remaining augmenting path has at least √''n'' edges in it. However, the [[symmetric difference]] of the eventual optimal matching and of the partial matching ''M'' found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least √''n'', there can be at most √''n'' paths in the collection, and the size of the optimal matching can differ from the size of ''M'' by at most √''n'' edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most √''n'' additional phases before the algorithm terminates.
Since the algorithm performs a total of at most 2√''n'' phases, it takes a total time of O(''m'' √''n'').
| |||