.. _tournament:

Tournament
=============================================================================================

Adjacency Matrix of a Tournament
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: python

    n = 5  # Number of vertices
    adjacency_matrix = [[0 for _ in range(n)] for _ in range(n)]  # Initialize matrix with zeros
    
    # Fill adjacency matrix for tournament
    for i in range(n):
        for j in range(i+1, n):
            if random.random() > 0.5:
                adjacency_matrix[i][j] = 1  # Edge from i to j
            else:
                adjacency_matrix[j][i] = 1  # Edge from j to i

In a tournament graph, for every pair of distinct vertices :math:`i` and :math:`j`, exactly one of the edges :math:`(i,j)` or :math:`(j,i)` exists in the graph. The adjacency matrix of a tournament is a square matrix where:

- :math:`a_{ij} = 1` if there is a directed edge from vertex :math:`i` to vertex :math:`j`
- :math:`a_{ij} = 0` otherwise

with the properties:
1. :math:`a_{ij} + a_{ji} = 1` for all :math:`i \neq j`
2. :math:`a_{ii} = 0` for all :math:`i`

Generating Random Tournament
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: python

    import random

    def generate_random_tournament(n):
        tournament = [[0]*n for _ in range(n)]
        for i in range(n):
            for j in range(i+1, n):
                if random.randint(0, 1):
                    tournament[i][j] = 1
                else:
                    tournament[j][i] = 1
        return tournament

    # Example usage
    random_tournament = generate_random_tournament(5)

.. image:: images/tournament.png

This algorithm generates a random tournament by independently choosing the direction of each edge with equal probability (50%). For each pair of vertices :math:`(i, j)` where :math:`i < j`, we randomly assign the edge direction using a coin flip. This process guarantees the resulting graph will satisfy the tournament property where exactly one directed edge exists between every pair of vertices.

**Definition 3.2.1 (Tournament)**
----------------------------------------------------------------------
A tournament is a simple complete graph with directed edges (Figure 1 shows a tournament with 5 vertices).

.. figure:: /_static/tournament_1.png
 :width: 50%
 :align: left
 :alt: This appears if the internet connection is poor

An 
:math:`n`
-vertex tournament can model a competition among 
:math:`n`
teams where there is a directed edge from vertex 1 to vertex 2 if and only if team 1 has defeated team 2 (as shown in Figure 1).

The King in Tournaments
----------------------------------------------------------------------

A tournament is a complete directed graph where every pair of vertices is connected by a single directed edge. In tournaments, a *king* vertex is a vertex that can reach every other vertex in the graph via a path of length at most 2.

**Algorithm to Find the King in a Tournament**

.. code-block:: python

    def find_king(adj_matrix):
        # Tournament adjacency matrix
        n = len(adj_matrix)
        king = 0
        for v in range(1, n):
            # if v defeats the current king
            if adj_matrix[v][king] == 1:
                king = v
        # verify if the king is indeed a king
        for v in range(n):
            if v != king and adj_matrix[v][king] == 1:
                # if defeated, the king is invalid
                return -1
        return king

.. image:: images/tournament.png
    :alt: A tournament with a king

**Algorithm Description**:  
The above algorithm uses a greedy approach to first identify a potential king vertex and then verifies its validity.

**Definition 3.2.2 (King)**  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
A **king** is a vertex in a tournament that has a directed path of length at most 2 to all other vertices in the tournament. For example, vertex 3 is a king in Figure 1.

**Theorem 3.2.3**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**Theorem Statement:** Every tournament has at least one king.

**Proof:** Let 
:math:`v`
be a vertex with out-degree 
:math:`\Delta^{+}`
in the tournament, i.e., a vertex with the maximum out-degree. If there exists a vertex 
:math:`u`
that cannot be reached from 
:math:`v`
via a path of length at most 2, then 
:math:`u`
must have directed edges to 
:math:`v`
and all vertices 
:math:`w`
where 
:math:`(v,w) \in E`
(Figure 2). This would imply 
:math:`d^{+}(u) \geq \Delta^{+}+1`,
contradicting the maximality of 
:math:`v`'s
out-degree. Hence, no such vertex 
:math:`u`
exists that is unreachable from 
:math:`v`
within at most two edges, and therefore 
:math:`v`
is a king.

.. figure:: /_static/tournament_2.png
 :width: 50%
 :align: left
 :alt: اگه اینترنت یارو آشغال باشه این میاد

Theorem 3.2.3 can be interpreted as follows: in a tournament competition, there exists an individual 
:math:`v`
such that for every other individual 
:math:`u`,
either 
:math:`v`
has defeated 
:math:`u`
directly or has defeated someone who defeated 
:math:`u`.

.. Hamiltonian Path in Tournaments
----------------------------------------------------------------------

Every tournament contains a Hamiltonian path. We can prove this claim using strong induction. 

**Proof by induction:**

**Base case:** For a tournament with 2 vertices, the Hamiltonian path is trivially the directed edge between them.

**Inductive step:** Assume every tournament with `n` vertices has a Hamiltonian path. Consider a tournament with `n+1` vertices. Remove a vertex `v`, resulting in a tournament of `n` vertices. By the induction hypothesis, this subtournament has a Hamiltonian path, say `v₁ → v₂ → ... → vₙ`. Now, reinsert `v` and find its position in the path:

1. If there's an edge from `v` to `v₁`, prepend `v` to the path: `v → v₁ → v₂ → ... → vₙ`.
2. If there's an edge from `vₙ` to `v`, append `v` to the path: `v₁ → v₂ → ... → vₙ → v`.
3. Otherwise, find the smallest `i` where `vᵢ → v` and `v → vᵢ₊₁`, then insert `v` between `vᵢ` and `vᵢ₊₁`:  
   `v₁ → ... → vᵢ → v → vᵢ₊₁ → ... → vₙ`.

Since tournaments are complete oriented graphs, one of these cases must hold. ∎

**Example:** Find a Hamiltonian path in the following tournament:

.. image:: images/tournament-example.png
   :width: 200px

**Solution:** Using the inductive algorithm:

.. code-block:: python
   :linenos:

   # Tournament adjacency matrix
   # Rows: outgoing edges from vertex i
   # Columns: incoming edges to vertex j
   adjacency_matrix = [
       [0, 1, 0, 0],  # First row: edges from vertex 1
       [0, 0, 1, 1],  # Second row: edges from vertex 2
       [1, 0, 0, 1],  # Third row: edges from vertex 3
       [1, 0, 0, 0]   # Fourth row: edges from vertex 4
   ]

   def find_hamiltonian_path(matrix):
       n = len(matrix)
       if n == 1:
           return [0]
       # Recursive step for n vertices
       path = find_hamiltonian_path([row[:-1] for row in matrix[:-1]])
       v = n - 1  # Last vertex index
       # Check insertion position
       if matrix[v][path[0]]:  # Case 1: prepend
           return [v] + path
       if matrix[path[-1]][v]:  # Case 2: append
           return path + [v]
       # Case 3: find intermediate position
       for i in range(len(path)-1):
           if matrix[path[i]][v] and matrix[v][path[i+1]]:
               return path[:i+1] + [v] + path[i+1:]
       return None  # Shouldn't reach here for tournaments

   # First path: 1 2 3 4 → After inserting vertex 4:
   print(find_hamiltonian_path(adjacency_matrix))  # Output: [3, 1, 2, 4]

**Definition 3.2.4 (Hamiltonian Path in a Directed Graph)**  
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
A Hamiltonian path in a directed graph is a directed path that traverses all vertices.

**Theorem 3.2.5**
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**Statement of the theorem:** Every tournament contains at least one Hamiltonian path.

**Proof of the theorem:** Let the vertices 
:math:`a_1`
to 
:math:`a_k`
form the longest directed path in the tournament (Figure 3).

.. figure:: /_static/tournament_3.png
 :width: 50%
 :align: left
 :alt: اگه اینترنت یارو آشغال باشه این میاد

If 
:math:`k = n`,
the theorem is proved. Otherwise, there exists a vertex 
:math:`v`
not in this path. There cannot be a directed edge from 
:math:`v`
to 
:math:`a_1`
or from 
:math:`a_k`
to 
:math:`v`
(Why?). Thus, let 
:math:`a_i`
be the vertex with the smallest index 
:math:`i`
among all vertices from 
:math:`a_1`
to 
:math:`a_k`
such that 
:math:`v`
has an edge to it. In this case, the vertices
:math:`a_1,...,a_{i-1},v,a_i,...,a_k`
form a path of length 
:math:`k+1`,
contradicting the assumption that the longest path has length 
:math:`k`.
Therefore, 
:math:`k = n`
and 
:math:`a_1`
to 
:math:`a_k`
form a Hamiltonian path.