Difference between revisions of "Walther MA279 Spring2016 topic8" - Rhea

Revision as of 20:28, 22 April 2016

Scheduling MA 279 Team Project: Dana Smith, Bronz McDaniels, Ryan Andrew, Eliot Mathieu

Introduction

The mathematics of tournaments refers to the use of digraphs, where vertices represent teams or players, and arcs between vertices indicate the winner and loser of each game played in the tournament. Games cannot end in a tie. Types of tournaments include single elimination and round robin.

Definitions

The following vocabulary is necessary and useful for understanding the mathematics of tournaments.

• Tournament: A tournament T is an orientation of a complete graph. Thus for every pair of vertices v, w in T, either (v, w) or (w,v) is an arc of the graph.

• Digraph: A graph in which the edges have a direction associated to them, typically indicated by an arrow

• Arcs: A directed edge that is defined by a starting vertex and its ending vertex. If we have vertices X and Y we will define XY as an arc in which X goes to Y

• Arc-set: A list of all the arcs in a digraph.

• Indegree: The indegree of a vertex X is the number of arcs that have X as their ending point.

• Outdegree: The outdegree of a vertex X is the number of arcs that have X as their starting point.

• Complete graph:A graph with N vertices in which every pair of distinct vertices is joined by an edge. Denoted by the symbol Kn.

• Paths: A sequence of arcs that are adjacent to one another. For example the arcs XY,YZ,ZA,AC would be a path from vertex X to vertex C. For simplicity we will denote a path by the sequence of vertices that connects (X,Y,Z,A,C).

• Cycle: A path that starts and ends at the same vertex.

• Score sequence: The set of scores that each player would receive in the tournament, where each win counts as one point and a loss counts as no points. This is achieved by sorting the set of outdegrees in nondecreasing order.

Tournaments

Round Robin

Examples

Conclusion

In conclusion, we see that the graphical theory behind tournaments is not too far separated from traditional graph theory. Tournament theory has been very significant over time in finding ways to fairly determine a winner among several teams in competition. Two main methods for doing so, Single Elimination and Round Robin, arose. The advantages of Single Elimination are that it is a short and uncomplicated design, and eliminates half of the participants at each round. However, the main disadvantage is the “luck” component where one bad round completely eliminates a team and can be unreflective of a team’s overall skill level. Round Robin addresses this concern because every team must play every other team; however, the time and coordination required for this is much greater than that for Single Elimination. Once again, in math we find ourselves at the crossroads of efficiency and equality. The most surprising part is that there is a type of tournament where a clear winner, which is the original reason tournament theory came about. These types of tournaments are called paradoxical tournaments. For further information about tournaments