Content deleted Content added
Undid revision 1194722672 by 95.165.149.179 (talk). The new values for bob caused the "brute force" table below it to become incorrect and I do not see a reason for these changes, so reverting. |
Put an emphasis on tight in the definition of G_y. |
||
Line 75:
The cost of each perfect matching is at least the value of each potential: the total cost of the matching is the sum of costs of all edges; the cost of each edge is at least the sum of potentials of its endpoints; since the matching is perfect, each vertex is an endpoint of exactly one edge; hence the total cost is at least the total potential.
The Hungarian method finds a perfect matching and a potential such that the matching cost equals the potential value. This proves that both of them are optimal. In fact, the Hungarian method finds a perfect matching of '''tight edges''': an edge <math>ij</math> is called tight for a potential {{mvar|y}} if <math>y(i)+y(j) = c(i, j)</math>. Let us denote the [[Glossary of graph theory#Subgraphs|subgraph]] of '''tight''' edges by <math>G_y</math>. The cost of a perfect matching in <math>G_y</math> (if there is one) equals the value of {{mvar|y}}.
During the algorithm we maintain a potential {{mvar|y}} and an [[Glossary of graph theory#orientation|orientation]] of <math>G_y</math> (denoted by <math>\overrightarrow{G_y}</math>) which has the property that the edges oriented from {{mvar|T}} to {{mvar|S}} form a matching {{mvar|M}}. Initially, {{mvar|y}} is 0 everywhere, and all edges are oriented from {{mvar|S}} to {{mvar|T}} (so {{mvar|M}} is empty). In each step, either we modify {{mvar|y}} so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of {{mvar|M}} are tight. We are done if {{mvar|M}} is a perfect matching.
| |||