Round Robin Tournament ScheduleDate: 03/31/2000 at 14:43:25 From: Blake Kinley Subject: Scheduling sports competitions What is the principle or formula I need to do this without using trial and error? I need to be able to create match schedules for up to 32 teams. Here is a sample for 6 Teams that I worked out using the trial-and-error method. Round 1: Field A: Team 6 vs Team 1 Field B: Team 4 vs Team 3 Field C: Team 5 vs Team 2 Round 2: Round 3: Round 4: Round 5: A: 1-3 A: 2-4 A: 3-5 A: 6-5 B: 6-2 B: 1-5 B: 6-4 B: 3-2 C: 5-4 C: 6-3 C: 2-1 C: 4-1 Notice That each team plays on each field a maximum of twice (sometimes only once). I need a method other than trial-and-error to create similar match schedules for 8 Teams on 4 Fields, 10 Teams on 5 Fields, and so on up to at least 32 Teams on 16 Fields. HELP! Date: 04/03/2000 at 13:52:26 From: Doctor TWE Subject: Re: Scheduling sports competitions Hi Blake - thanks for writing to Dr. Math. Scheduling a round-robin tournament is not as easy as it looks. There is a systematic approach to scheduling that ensures that every team plays every other team once with the minimum amount of "idle time" (or byes). This method assumes that there are enough fields so that all the games in a round can be played simultaneously. The technique is sometimes referred to as the "polygon method." It has two variations, depending on whether the total number of teams is an even number or an odd number. I'll cover the odd case first. POLYGON METHOD ROUND-ROBIN SCHDULING: ODD NUMBER OF TEAMS --------------------------------------------------------- Let N = number of teams in the tournament. There will be N rounds (since each team will play every other team once, and will have exactly one idle round, or "bye"). I will use five teams (A, B, C, D, and E) in my example. STEP 1: Draw a regular N-gon. (An N-gon is a polygon with N sides, for example a triangle, pentagon, heptagon, etc.) Each vertex represents one team, and can be labeled as such. A o E o o B o o D C STEP 2: Draw (N-1)/2 line segments connecting the vertices such that: a) No vertex has more than one segment drawn to/from it, and b) No segment is a rotation or reflection of another segment. One easy method to ensure that these conditions are met is to "stripe" the polygon. Draw the polygon such that the two lowest vertices are horizontal. Connect these two with a horizontal segment. Connect the two next lowest ones with another horizontal segment, etc. The top vertex will remain unconnected. (This is because there is an odd number of vertices.) A o E o-------o B o---o D C Each segment represents teams playing each other in the first round. In my example, team E plays team B and team D plays team C. Team A is idle in round one. STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point.) You can either rotate the segments in the polygon (keeping the vertices fixed) or you can rotate the vertices (keeping the segments fixed). I'm going to rotate the vertices because it's easier to draw with ASCII graphics. The new segments represent the match-ups for round two. E o D o-------o A o---o C B In my example, team D plays team A and team C plays team B in round two. Team E is idle. STEP 4: Continue rotating the polygon until you return to your original position. Each rotation represents the match-ups of the next round. When you return to the original position, you don't record the match-ups, as they were already played in round one. For example: Round three: C-E, B-A (D idle) D o C o-------o E o---o B A Round four: B-D, A-E (C idle) C o B o-------o D o---o A E Round five: A-C, E-D (B idle) B o A o-------o C o---o E D One more rotation would bring me back to my original position. Thus, my schedule looks like this: Round Games: Idle ----- -------- ---- 1 E-B, D-C A 2 D-A, C-B E 3 C-E, B-A D 4 B-D, A-E C 5 A-C, E-D B Why does this work? Requiring (N-1)/2 segments in step 2 ensures that there is only one idle team in each round, thus there will be the minimum number of rounds required. The restriction that no vertex has more than one segment drawn to/from it ensures that no team is scheduled for more than one game in each round. And the restriction that no segment is a rotation or reflection of another segment ensures that no match-up will be repeated in a future round. A final note: For N > 6, the "striping" method is not the only way of drawing the segments for step 2, but it is the easiest. Here are two ways of drawing them for a heptagon (N = 7): A A o o G o-------o B G o / o B X \ F o-----------o C F o/ \ o C \ o-----o o o E D E D The "striping" method pairs G-B, F-C and E-D in round one, while the alternate method pairs A-F, G-D and B-C in round one. Each of these creates a valid schedule, they are not the same schedule with just some of the rounds switched. POLYGON METHOD ROUND-ROBIN SCHDULING: EVEN NUMBER OF TEAMS --------------------------------------------------------- Let N = number of teams in the tournament. There will be N-1 rounds (since each team will play every other team once, and there will be no idle teams, or "byes"). I will use six teams (A, B, C, D, E and F) in my example. STEP 1: Draw a regular (N-1)-gon. (for 4 teams draw a triangle, for 6 teams draw a pentagon, for 8 teams draw a heptagon, etc.) Place a point in the center of the polygon. Each vertex and the center point represent one team, and can be labeled as such. A o E o o B o F o o D C STEP 2: Draw N/2 line segments connecting the vertices and the center point such that: a) No vertex (nor the center point) has more than one segment drawn to/from it, and b) No segment is a rotation or reflection of another segment. This is essentially the same as the odd case, but the "idle" team plays the "center" team. "Striping" still works, but the top vertex must be connected to the center point. For example A o | E o-------+-------o B | o F o-------o D C Each segment represents teams playing each other in the first round. In my example, team E plays team B, team D plays team C, and team A plays team F in round one. STEP 3: Rotate the polygon 1/Nth of a circle (i.e. one vertex point). You can either rotate the segments in the polygon (keeping the vertices fixed) or you can rotate the vertices (keeping the segments fixed). I'm going to rotate the vertices because it's easier to draw with ASCII graphics. The new segments represent the match-ups for round two. E o | D o-------+-------o A | o F o-------o C B In my example, team D plays team A, Team C plays team B, and team E plays team F in round two. STEP 4: Continue rotating the polygon until you return to your original position. Each rotation represents the match-ups of the next round. When you return to the original position, you don't record the match-ups, as they were already played in round one. For example: Round three: C-E, B-A, D-F D o | C o-------+-------o B | o F o-------o B A Round four: B-D, A-E, C-F C o | B o-------+-------o D | o F o-------o A E Round five: A-C, E-D, B-F B o | A o-------+-------o C | o F o-------o E D One more rotation would bring me back to my original position. Thus, my schedule looks like this: Round Games: ----- ------------- 1 E-B, D-C, A-F 2 D-A, C-B, E-F 3 C-E, B-A, D-F 4 B-D, A-E, C-F 5 A-C, E-D, B-F You also mentioned restricting the number of fields in play. This can be tricky. Usually, you can start the games for round one in timeslot one, play the remaining round one games in timeslot two, and find games from round two that don't involve teams already playing in timeslot two, etc. If there are less than N/4 fields, the round one games will fill timeslots one and two, and spill into timeslot three, etc. I hope this helps. If you have any more questions, write back. - Doctor TWE, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/