A scheduling problem with a simple graphical solution
Beecham, A. F.; Hurley, A. C.; Beecham A. F.; CSIRO Division of Chemical Physics, P.O. Box 160, Clayton, Victoria 3168; Hurley A. C.; CSIRO Division of Chemical Physics, P.O. Box 160, Clayton, Victoria 3168
Журнал:
The Journal of the Australian Mathematical Society. Series B. Applied Mathematics
Дата:
1980
Аннотация:
AbstractIt is shown that a problem which arose in the scheduling of two simultaneous competitions between a number of golf clubs may be reduced to that of 4- colouring the edges of a certain bipartite graph which has 4 edges meeting at each vertex. This colouring problem is solved by an analysis in terms of directed cycles, which is simple to carry through in a practical case and is easily extended to the problem with 4 replaced by 2<sup>m</sup>. The more general colouring problem with 4 replaced by any positive integer is solved by relating it to the marriage problem enunciated by Philip Hall and to the latin multiplication technique of Kaufmann but, in practical applications, this approach involves severe computational difficulties.
422.0Кб