Content deleted Content added
m →Matrix interpretation: rm vestigial line break |
max changed to min. In case of an NxM matrix, the maximum number of matchings (n) is min(number of people, number of assignments) |
||
Line 215:
This is equivalent to subtracting a number from all rows which are not crossed and adding the same number to all columns which are crossed. These operations do not change optimal assignments.
Repeat steps 3–4 until an assignment is possible; this is when the minimum number of lines used to cover all the 0s is equal to
From Kőnig's theorem,<ref>[[K%C5%91nig%27s theorem (graph theory)]] Konig's theorem</ref> the minimum number of lines (minimum Vertex cover<ref>[[Vertex cover]] minimum vertex cover</ref>) will be <math>n</math> (the size of maximum matching<ref>[[Matching (graph theory)]] matching</ref>). Thus, when <math>n</math> lines are required, minimum cost assignment can be found by looking at only zeroes in the matrix.
| |||