Mathematics Magazine for Grades 112 



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

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
FordFulkerson 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 FordFulkerson 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. 
