Mathematics Magazine for Grades 1-12  

Correspondents
Algorithm for Determining a Maximum Coupling of Minimum Value in a Bipartite Graph

by Ilie Vieru Teacher- National  College Gh. Vranceanu Bacău, Romania

(1)                                                                (1), (2) , (3), (4)

There are well known the problems in which an optimum  association of the elements of set  with the ones of set  is required, under the conditions of some restrictions of the possibilities of association. In general, each possible association  generates a certain effect  (cost,profit,etc), which we assume to be known.

The restrictions of the association possibilities stand for:

·        An element  from set A can be associated only with certain elements from set B and reciprocally.

·        In the end, at most one element from set B has been associated to each element from set A and reciprocally.

The optimum association stands for the finding of a maximum coupling in a bipartite graph and usually involves two objectives:

·        To determine the maximum number of associations;

·        The optimum sum (maximum or minimum) of the effects of associations.

From the practical problems which reduce to determinig a maximum coupling of optimum value , we mention:

·        Allocating the workers in a unit on machines, acording to their skills and their prefferences and also according to the complexity of the machines;

·        Allocating the employees on the jobs

·        Assembling work groups base on the affinities among the members of the collective;

·        Transfer of information in a group.

Note: We assume the definitions concerning the bipartite graph, coupling, maximum coupling, value of coupling ( e.q. [1],[2],[4])  to be known.

          In 1931 Konig formulated the following theorem: The maximum number of vertices of a coupling in a bipartite graph  is equal to

a)     In 1955, relying on Konig’s theorem, H.K. Kuhn  elaborated an algorithm known as the hungarian algorithm, with which we can determine a maximum coupling of minimum value in a bipartite graph for . It is based on the observation that if we add(or substract) the same number to all the values of the vertices, the hierarchy of the maximum couplings will not be changed. The algorithm starts from the square matrix  where:

          This algorithm, even tough it has polynomial complexity , is laborios, difficult to implement, not recomended for competitions.

b)    for determining the bipartite graph maximum coupling, we can use the Ford-Fulkerson method for the bipartite graph , in a polynomial time in  and . The solution is building a transport network in which the fluxes represent the couplings.The initial graph is completed with two more vertexes s(source) and t(destination), connected to the vertexes from A respectively B as in the example [2] from page 517. It is assumed that each vertice has a positive capacity.In this context, the Ford-Fulkerson algorithm is applied obtaining the optimum solution. In this case also, the algorithm, although with polynomial complexity, is difficult to implement, being specific to the transport networks.

c)     In the following I propose an original algorithm , fast and very easy to implement. For this  we start from a few elements of superior algebra. It is known that for calculating the determinant asociated to matrix a we have the formula where  represents the signature of the permutation  and each of the terms of the sum represent a product with n terms of the matrix A, so that they use out all the lines and columns of the matrix. In other words, in each term of the sum there are no two factors on the same line or the same column of the matrix.

Read more on the written version of the publication.