Revision as of 09:23, 10 February 2021 edit 203.97.16.73 (talk) →The algorithm in terms of bipartite graphs: Prove that the algorithm always makes progress when the matching is not yet of maximum possible size. ← Previous edit		Revision as of 18:55, 14 March 2021 edit undo Fjf2002 (talk \| contribs) 8 edits m Grammar corrected Next edit →
Line 71: ===Proof that the algorithm makes progress=== We must show that as long as the matching is not of maximum possible size, the algorithm is always be able to make progress — that is, to either increase the number of matched edges, or tighten at least one edge. It suffices to show that at least one of the following holds at every step: * <math>M</math> is of maximum possible size.

Hungarian algorithm: Difference between revisions