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

 

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

 

Exemple: In a factory, 6 workers operate on 6 machines. Let  be the losses determined by employing worker i on machine j. According to the matrix:

determine the optimum order of positioning the 6 workers on the 6 machines so that the total losses are minimum.

          By applying the algorithm we obtain:

Step 1:        ;

Step 2:       

Step 3:       

                     

Step 4:   

                    

Step 5:      

                      

Step 6:                                                               

Therefore,   

   and the  order on the machines is: (1,4), (2,6), (3,5), (4,2), (5,1),  (6,3).

Application: The coach’s problem (a real problem for a real coach)

In a team sport ( football, rugby, hockey) where n players go on the field, the coaches of every team, together with their teams of experts, manage to determine the risk a coach is taking by deciding that player i ( ) be put to play on the position j ( ).

Having this information within reach (a rectangular matrix with m lines and n columns, ), the coach has to naturally solve this problem:

  1.  to choose from the m players, the “first” n players on positions so that the total risk is minimum;

  2.  if during the game one of the players is not fit (or is injured), his replacement being necessary, to establish who of the m-n players on the bench will go on the field and what changes have to be done in the organization of the game (  modifications of positions among players) so that the total risk is also minimum.

This problem, although very old, can now be solved very easily; even more, we now can rigorously explain why a coach makes some changes that the spectators “do not understand” (for example, when he replaces a forward with a mid-fielder or a defender).

Biblography:

  1.  E. Tiganescu, D. Mitrut - The basis of operational research ASE Bucharest Publishing, 1994

  2. T. Carmen - s.a. introduction in algorithms, Libris Agora Publishing Cluj Napoca, 2000

  3. I.Vieru - The role of decision in dynamic programming, GInfo 10/3 2000.

  4. I. Tomescu - combinatorics and graph theory, Bucharest University, 1978.

 
 
 

Read more on the written version of the publication.