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

 

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

 

void calvoid calcul()

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

  s=a[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];

                                                             R=a[i][k]+a[k][j]-a[i][j];

                                                             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];

                                                                           R=a[i][k]+a[k][c]-a[i][j]-a[u][c]+a[u][j];

                                                                           if(R<li0){li0=R;c0=c;i0=i;u0=u;j0=j;}

                                                                         }

                                                       }

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

                               else { s+=li0;

                                          if(c0==j0){d[i0]=k;d[k]=c0;v[c0]=k;v[k]=i0;}

                                          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]]);

   printf("\n");

 }

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.