Edge coloring: A natural model for sports scheduling

摘要

Graph theory can be used to solve discrete problems in many real life problems. This study shows how fundamental concepts of graph theory such as edge coloring can be used to solve sports scheduling involving many teams and multiple venues such as Olympic Games and World Cup football tournaments. A round robin tournament is assumed for this purpose involving an even number of teams n. Every game involves two teams i and j representing two vertices of the graph and an edge (i, j) of this graph representing a match involving them. The objective of tournament scheduling is to allot each game to some time slot so that each team play at most one game in a round and the total number of rounds are kept at the minimum. Games are divided to subsets F_s where s is a specific round. Edges of the subset F_1 are represented by dashed lines, F_2 by solid straight lines, F_3 by double solid lines etc. In every subset s each team is matched with one team making a perfect matching. A tournament is said to be compact if each team plays exactly once in each round. If each team plays exactly once with all other teams in a given number of teams then the format is called single round robin (SRR). In similar way a double round robin (DRR) can also be considered for a tournament. For SRR scheduling, even number of teams are required. The approach used of SRR can be extended to DRR also. If the number of teams is odd, then a dummy team can be used to make the scheduling possible. The main problem is to decide the venue and the round for each tournament. Though the problem appears to be simple, with some constraints it may become a N-hard type combinatorial optimization problem. Many algorithmic approaches are proposed in the literature for solving these type of problems. (36 refs.)