Subscribe

Mathematics Magazine for Grades 1-12  

 

Algorithm for Determining a Maximum Coupling of Minimum Value in a Bipartite Graph
by Ilie Vieru Teacher- National  College Gh. Vranceanu Bacău, Romania

 

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

 

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:

  •  is added to  in which case we effectuate the following: : ; ; .
  •  is formed by adding the terms  and   for which we have  in which case ; ; ; ; .
  •  is formed by adding the term   and   for which we have   in which case ; ;   ; ; ; .

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.