Tournaments

Graph Theory · Axiom Academy

Complete directed graphs modeling round-robin competitions and dominance hierarchies 1. Definition: Tournament Graphs A tournament is a directed graph obtained by assigning a direction to each edge in a complete undirected graph. In other words, for every pair of distinct vertices, there is exactly one directed edge (arc) connecting them. For every pair of distinct vertices u, v in V, exactly one of (u,v) or (v,u) is in E No self-loops exist (no vertex points to itself) The total number of arcs is n(n-1)/2 , where n = |V| Interpretation: Think of a round-robin tournament where n players each compete against every other player exactly once. An arc from u to v means "u beats v" or "u dominates v". Watch the animation to see how a tournament is constructed from a complete graph: 2. Remarkable Property: Hamiltonian Paths Always Exist Unlike general graphs where finding Hamiltonian paths is NP-complete, tournaments have a beautiful guarantee: every tournament contains at least one Hamiltonian path . This means we can always rank all competitors in a linear order where each beats the next - though this ranking might not be unique! The animation demonstrates constructing a Hamiltonian path in a tournament: 3. Kings and Emperors: Dominance in Two Steps In a tournament, we can classify vertices by their ability to reach other vertices quickly:

This is the written version of the interactive lesson above. See the full Graph Theory course.