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


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


void calvoid calcul()

{ d[1]=1; v[1]=1;


  for(k=2;k<=n;k++) {  li0=a[1][k]+a[k][d[1]]-a[1][d[1]]; i0=1;  c0=j=d[i0];

                               for(i=1;i<k;i++){ j=d[i];


                                                             if(R<li0){ li0=R;i0=i;j=d[i];c0=j0=j;}

                                                             for(int c=1;c<k;c++)

                                                              if(c-j){int u=v[c];





                               if(li0>=a[k][k]){s+=a[k][k]; d[k]=k;v[k]=k;}

                               else { s+=li0;


                                          else{ d[i0]=k; v[k]=i0;d[u0]=j0;

                                                    v[j0]=u0; d[k]=c0; v[c0]=k;




   printf(" S= %d\n",s);

   for(i=1;i<=n;i++)printf("%d ", a[i][d[i]]);



c2)  For  n=|A|<|B|=m,   the algorithm covers the following steps:

- c1) is applied and  , ,  are found;

- for  ,  is found;  if  <0 then we effectuate the following up to date bringings:  

Note: The solution is declared like in case c1).

c3) For  n=|B|<|A|=m the algorithm covers the following steps:

-  c1) is applied and , , ;  are found.

-  for ,   is found, if    then we perform the following       .

Note : In this case,  on displaying the decision vector  (see [3]),  the row can be scanned on columns  or we can select those lines, in an increasing, using i, for which .

Pursuing the steps shown, we can demonstrate, using a typical dinamyc programming procedure, the following theorem: the presented algorithm determines a maximum coupling of minimum value.


Read more on the written version of the publication.