Hungarian algorithm - Wikipedia, the free encyclopedia
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods.
https://en.wikipedia.org/wiki/Matching_(graph_theory)
A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching. Figure (b) above is an example of a perfect matching. Every perfect matching is maximum and hence maximal. In some literature, the term complete matching is used.
The Hungarian method is a combinatorial optimization algorithm that solves the assignment problem in polynomial time and which anticipated later primal-dual methods.
We are given a nonnegative n×n matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost. If the goal is to find the assignment that yields the maximum cost, the problem can be altered to fit the setting by replacing each cost with the maximum cost subtracted by the cost.
The algorithm is easier to describe if we formulate the problem using a bipartite graph. We have a complete bipartite graph 
with 
worker vertices (
) and job vertices (
), and each edge has a nonnegative cost 
. We want to find a perfect matching with minimum cost.
with worker vertices () and job vertices (), and each edge has a nonnegative cost . We want to find a perfect matching with minimum cost.
Given workers and tasks, and an n×n matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.
workers and tasks, and an n×n matrix containing the cost of assigning each worker to a task, find the cost minimizing assignment.
First the problem is written in the form of a matrix as given below
where a, b, c and d are the workers who have to perform tasks 1, 2, 3 and 4. a1, a2, a3, a4 denote the penalties incurred when worker "a" does task 1, 2, 3, 4 respectively.
https://en.wikipedia.org/wiki/Matching_(graph_theory)
Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.
A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched.
A maximal matching is a matching M of a graph G with the property that if any edge not in M is added to M, it is no longer a matching, that is, M is maximal if it is not a proper subset of any other matching in graph G.
A maximum matching (also known as maximum-cardinality matching[1]) is a matching that contains the largest possible number of edges. 
A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. That is, every vertex of the graph is incident to exactly one edge of the matching. Figure (b) above is an example of a perfect matching. Every perfect matching is maximum and hence maximal. In some literature, the term complete matching is used.
A near-perfect matching is one in which exactly one vertex is unmatched. This can only occur when the graph has an odd number of vertices, and such a matching must be maximum. In the above figure, part (c) shows a near-perfect matching. If, for every vertex in a graph, there is a near-perfect matching that omits only that vertex, the graph is also called factor-critical.
Read full article from Hungarian algorithm - Wikipedia, the free encyclopedia