Mathematics Magazine for Grades 112 



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

Exemple:
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:
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 midfielder or a defender). Biblography:


Read more on the written version of the publication. 
