Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Copy of Graph Theory: Sports Scheduling
Transcript of Copy of Graph Theory: Sports Scheduling
Sports Scheduling Sports Scheduling and Tournaments Questions? First published graph theory paper was by Leonhard Euler in 1736 " Seven Bridges of Konisberg"
Many illustrious names visted upon this topic from Vandermonde to Cauchy, from Cayley to De Morgan and more recently Erdos. Began with determining routes and began to exam various graphs as it related to theoretical chemistry at the time. Since then many different branches of graph, a few are: Enumerative Graph Theory Graph Coloring Random Graph Theory Algorithmic Graph Theory Definintion of Tournament: A tournament T is an orientation of a
complete graph. Thus for every pair of vertices v;w 2 V(T) either
(v;w) or (w;v), not both, is in E+T. Began with Landau who developed this to model the dominance relations in flocks of chickens. This branch of graph theory expanded to include voting theory and social choices theory.
Eventually came to be used in the sports arena especially with "round robin" tournaments. Round Robin Tournaments If there are n number of competitors, a round robin tournament requires
games. If n is even,then in each of (n-1) rounds, games can be run in parallel. If n is odd, there will be n rounds, each with games, and one competitor having no game in that round. We assign each competitor a number and pair them off in the first round. We then can fix one competitor and rotate the others clockwise one postion. When there are an odd number of competitors, a dummy competitor can be added whose scheduled opponent in a given round has a bye. Tournaments A tournament with 4
teams(vertices) Has n vertices
Has nC2 edges Contains a Hamiltonian
path: A direct path on all n
vertices. Is a directed graph Round 1 Round 2 Round 3 Round 4 Round 5 Round 6 Round 7 The complete graph is Kn, n>1. Complete Tournament Games K7 Ranking Win=2 points Loss=1 points If after all the games have been played, you total each teams
total wins and losses, using the above points, and rank them
from highest to lowest. If there is a tie between 2 or more teams, to decide how to
rank them, you look at the games between the tied teams,
and who ever has the largest total gets ranked first, then
the next one second and so on.