Content deleted Content added
Line 3:
==Theory==
The algorithm developped by Kuhn was largerly based on the earlier works of two other [[Hungarian]] mathematicians: [[Konig]] and [[Egervary]]. The great advantage of Kuhn’s method is that it is strongly polynomial. The main idea of the algorithm is that it combines two separate parts in Egervery’s proof (computing a deficient set and revising the current <math>\pi</math> ) into one. The procedure of covering the prime zeros can be implemented in a [[flow network]], and automated by means of the [[Ford-Fulkerson algorithm]]. The nxm matrix is transformed in a <math>G=(U,V)</math> bipartite graph, with I/O capacity equal to 1. Each arc joining the nodes of the flow network represents a zero in the cost matrix. After the maximum flow is obtained, the affected arcs represent the prime zeros. The [[minimum cut]] obtained by Ford-Fulkerson, will automate the process of covering the independent zeros. Each node that gets "cut" on the max-flow graph, represents a covered row or line on the cost matrix. However, in the Hungarian method the assignment can be easily found on the cost matrix, yet the expansion into a max-flow sub-problem is a useful method in more complex scenaria.
==Modelisation==
| |||