Mathematics Magazine for Grades 112 



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

c1) First suppose that A=B=n.
In this case we will have to determine the term
of minimum value, in a way
similar to the definiton previously presented, keeping in mind at the same time
the permutation that generated it. We introduce the notation
so that we can write the
expression:
this means that
is obtained from
by framing the corresponding
elements of column
respectively line
to the right and down . We attach the decision
vector
to the matrix
, with meaning
where
represents the term from
line i
chosen in a k step
in the
sum ,
. Also, we build the
vector that remembers the
reverse permutation attached to the permutations, which
means
or
, where
. Iterative we build
. Now suppose the four rows to
step k, k
1 are built. For step k+1 the
whole construction aims at: ·
Obtaining
with minimum value, in the sense of the definition, with terms from the
matrix
, using the results up to step k. ·
Bringing the vectors
respectively
up to date. In this step we distinguish
three situations:
In the end we have represents the minimum value of the maximum coupling: . To exemplify, we present the following implemental algorithm in C++ programming language: 

Read more on the written version of the publication. 
