Graph Theory Example History of Graph Theory Graph Theory and

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.

### Present Remotely

Send the link below via email or IM

CopyPresent to your audience

Start 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

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

### Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.

You can change this under Settings & Account at any time.

# Copy of Graph Theory: Sports Scheduling

Math project

by

Tweet