ROUGH DRAFT authorea.com/109020
Main Data History
Export
Show Index Toggle 0 comments

Tournament Graphs       

Tournament graphs are used in discrete mathematics to represent a winning vertex in a graph. A tournament is a complete graph in which every pair of vertices are connected by a directed edge. These types of graphs are referred to as tournaments because each of the \(n\) players competes against the other \(n-1\) players where ties are not allowed and the winner can be represented on a graph. These graphs are created by assigning every player a vertex and if player \(1\) beats player \(2\), then a directed edge can be drawn with the arrow pointing from \(1\) to \(2.\) Tournaments graphs create Hamiltonian paths that go through each vertex. The Hamiltonian path theorem states that for every tournament there is a Hamiltonian path for \(n\ge1,\) for any tournament consisting of \(n\) vertices in which there is always a sequence of vertices \(v_1,v_2,...,v_n\) such that \(v_1\rightarrow v_2\rightarrow...\rightarrow v_n.\)
For example, 
This tournament consists of four players \(a,b,c\) and \(d.\) Notice that in the tournament creates a direct Hamiltonian path going through each vertex where \(A\rightarrow B\rightarrow C\rightarrow D.\)
A widely known tournament graph is based off of the king chicken theorem where \(x\) is known to be a king chicken if for each opponent \(y,\) we either have the case  \(x\rightarrow y\) or there exists another player \(z\) in which case \(x\rightarrow y\rightarrow z.\) A king exists if a player can walk to a designated vertex in at most two steps. For example,