Definition of Tournament Graphs

A directed graph \(G\) without self-loops is called a tournament if there exists exactly one directed edge between every pair of distinct vertices.

Strong Connectivity in Tournament Graphs

After contracting strongly connected components in a tournament graph \(G = (V, E)\), the result is a directed path.

Let’s assign an arbitrary topological order to the strongly connected components. For any two vertices \(u, v \in V\) belonging to different components, if component of \(u\) comes before that of \(v\) in this ordering, then there must be an edge \((u, v) \in E\). Therefore, the contraction of a tournament forms a linear sequence.

Hamiltonian Paths in Tournaments

Tournaments always contain Hamiltonian paths (Redei's Theorem)

Proof

For a tournament \(G = (V, E)\), we can construct a Hamiltonian path through induction.

Assume that a Hamiltonian path \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i - 1}\) has been found for vertiecs \(1\) to \(i - 1\).

If \((p_{i - 1}, i) \in E\), extend the path to \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i - 1} \rightarrow i\).

Otherwise, if \((i, p_1) \in E\), prepend \(i\) to form \(i \rightarrow p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{i -1}\).

Otherwise, find the smallest index \(x\) such that \((i, p_x) \in E\), which must exist since \(x > 1\). Modify the path to \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{x - 1} \rightarrow i \rightarrow p_x \rightarrow \dots \rightarrow p_{i - 1}\).

Starting with \(p_1 \leftarrow 1\), we add points \(2\) to \(n\) sequentially. Once all \(n\) points are included, \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n\) becomes a Hamiltonian path.

This construction takes \(O(n^2)\) time.

Code

fill(next + 1, next + n + 1, 0);
int left = 1, right = 1;
for (int i = 2; i <= n; ++i) {
  if (g[right][i]) {
    next[right] = i;
    right = i;
  } else if (g[i][left]) {
    next[i] = left;
    left = i;
  } else {
    for (int x = left;; x = next[x]) {
      if (g[i][next[x]]) {
        next[i] = next[x];
        next[x] = i;
        break;
      }
    }
  }
}

Strongly Connected Tournaments Contain Hamiltonian Cycles (Camion-Moon Theorem)

Proof

For a strongly connected tournament \(G = (V, E)\), we can build a Hamiltonian cycle from its Hamiltonian path using induction.

We start with a Hamiltonian path and renumber vertices according to their position along the path. After renumbering, \(\forall i \in [1, n - 1] \cap \mathbb{Z}, (i, i + 1) \in E\).

Suppose we have partitioned points \(1\) to \(i - 1\) into a cycle \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k \rightarrow p_1\) and a path \(k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i - 1\), satisfying \(\forall x \in [1, k] \cap \mathbb{Z}, \forall y \in [k + 1, i - 1] \cap \mathbb{Z}, (p_x, y) \in E\).

If \(\forall x \in [1, k] \cap \mathbb{Z}, (p_x, i) \in E\), extend the path to \(k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i - 1 \rightarrow i\).

Otherwise, find \(x\) such that \((i, p_x) \in E \land (p_{x - 1}, k + 1) \in E\). Such an \(x\) exists because \((i - 1, i) \in E\). Replace the cycle with \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_{x - 1} \rightarrow k + 1 \rightarrow k + 2 \rightarrow \dots \rightarrow i \rightarrow p_x \rightarrow \dots \rightarrow p_k \rightarrow p_1\), and update \(k \leftarrow i\).

Begin by finding minimal \(x\) such that \((x, 1) \in E\). Due to strong connectivity, such an \(x\) exists. Initialize \(k \leftarrow x\) and \(\forall i \in [1, x] \cap \mathbb{Z}, p_i \leftarrow i\). Continue adding points \(x + 1\) to \(n\). When complete, \(k = n\), otherwise contradicting strong connectivity. The resulting sequence \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n \rightarrow p_1\) forms a Hamiltonian cycle.

This algorithm runs in \(O(n^2)\) time.

Code

fill(next + 1, next + n + 1, 0);
int left = 1, right = 1;
for (int i = 2; i <= n; ++i) {
  if (g[right][i]) {
    next[right] = i;
    right = i;
  } else if (g[i][left]) {
    next[i] = left;
    left = i;
  } else {
    for (int x = left;; x = next[x]) {
      if (g[i][next[x]]) {
        next[i] = next[x];
        next[x] = i;
        break;
      }
    }
  }
}
right = 0;
for (int i = left; i; i = next[i]) {
  if (!right) {
    if (g[i][left]) right = i;
    continue;
  }
  if (g[i][left]) {
    right = i;
  } else {
    for (int x = left; x != right; x = next[x]) {
      if (g[x][next[right]] && g[i][next[x]]) {
        int temp = next[x];
        next[x] = next[right];
        next[right] = left;
        left = temp;
        right = i;
        break;
      }
    }
  }
}
next[right] = left;

Hamiltonian Cycles Imply Pancyclic Property (Corollary of Camion-Moon Theorem)

A directed graph \(G\) of order \(n\) is pancyclic if it contains cycles of all lengths from \(3\) to \(n\).

Proof

The case \(n \le 3\) holds trivially. We proceed by induction.

It suffices to show that every strongly connected tournament of order \(n \ge 4\) contains a cycle of length \(n - 1\). This follows because the subgraph induced by such a cycle is itself a strongly connected tournament of order \(n - 1\), and by induction, it contains cycles of all lengths up to \(n - 1\). Since we already know that \(n\)-order tournaments have Hamiltonian cycles, the full statement is proven.

Consider a Hamiltonian cycle \(p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_n \rightarrow p_1\) in a tournament. Removing vertex \(p_1\) results in a subgraph that is either strongly connected or consists of a chain after contraction.

The remaining part is composed of Hamiltonian paths from each component ordered by topology. If any path has length greater than one, we can skip its first or last node. Otherwise, all components are singletons, so we can skip an intermediate singleton.

Thus, we remove a node from the cycle to form a cycle of length \(n - 1\).

Degree Sequences in Tournament Graphs

Valid Outdegree Sequences (Landau's Theorem)

Given a non-decreasing sequence \(p_1 \le p_2 \le \dots \le p_n\) where \(\sum_{i = 1}^n p_i = \binom{n}{2}\), there exists a tournament with outdegrees \(p_1, p_2, \dots, p_n\) if and only if \(\forall i \in [1, n] \cap \mathbb{Z}, \sum_{j = 1}^i p_j \ge \binom{i}{2}\).

Necessity Proof

In any induced subgraph of vertices \(1\) to \(i\), there are \(\binom{i}{2}\) edges. Thus, \(\sum_{j = 1}^i p_j \ge \binom{i}{2}\).

Suffficiency Proof

Start with a tournament where edges go from higher-numbered to lower-numbered nodes. The initial outdegree sequence is \(q_i = i - 1\). Since \(\sum_{j = 1}^i q_j = \binom{i}{2} \le \sum_{j = 1}^i p_j\), adjust \(q\) until it matches \(p\).

Find minimal \(x\) such that \(q_x \neq p_x\). Then \(q_x < p_x\). Find minimal \(y > x\) such that \(q_y > p_y\). Adjust the graph by reversing edges to balance degrees. This process ensures \(q\) converges to \(p\) within finite steps.

Tournament Strong Components Count (Corollary of Landau's Theorem)

Let \(p_1 \le p_2 \le \dots \le p_n\) be the outdegree sequence of a tournament \(G\). The number of strongly connected components equals \(\sum_{i = 1}^n [\sum_{j = 1}^i p_j = \binom{i}{2}]\).

Proof

After contraction, the components form a path. Let \(S\) and \(T\) be adjacent components, with \(S\) preceding \(T\). There exists a unique \(x\) such that \(p_1\) to \(p_x\) correspond to \(T\) and components following \(T\). Then \(\sum_{i = 1}^x p_i = \binom{x}{2}\). Hence, the count is at least the number of components.

Also, each condition \(\sum_{i = 1}^x p_i = \binom{x}{2}\) uniquely defines a boundary between components. Therefore, the sum equals the component count.

Using bucket sort, the component count can be computed in \(O(n)\) time.

Minimum Cuts in Tournament Graphs

To compute the minimum \(s - t\) cut in a tournament \(G = (V, E)\), initialize \(S \leftarrow \{s\}, T \leftarrow V \backslash \{s\}\). Move vertices from \(T\) to \(S\) until a minimum cut is formed. Define \(cst_u\) as the change in cut value when moving \(u\) from \(T\) to \(S\):

[\begin{aligned} cst_u &= \sum_{i \in T} [(u, i) \in E] - \sum_{i \in S} [(i, u) \in E] \ &= \sum_{i \in T} [(u, i) \in E] - (|S| - \sum_{i \in S} [(u, i) \in E]) \ &= (\sum_{i = 1}^n [(u, i) \in E]) - |S| \end{aligned} ]Thus, \(cst_u\) depends only on \(u\)'s outdegree and \(|S|\).

Sort vertices excluding \(s, t\) by outdegree. The optimal cut moves a prefix of these sorted vertices. The minimum cut value is:

[\sum_{i = 1}^n [(s, i) \in E] + \min_{i = 0}^{n - 2} \sum_{j = 1}^i (p_j - j) ]

With bucket sorting, this can be computed in \(O(n)\) time. With sparse table preprocessing, \(O(1)\) queries are possible.

Example Problems

POI2017 Turysta

After contraction, the tournament becomes a path. Each component has a Hamiltonian cycle.

Compute the cycle for each component. Traverse each component’s nodes via its cycle, followed by subsequent components in topological order.

CF1268D Invertation in Tournament

Observation shows that a single operation often makes the graph strongly connected if it isn’t already.

If contraction yields more then two components, perform an operation on a middle component to make it connected.

If a component size exceeds 3, it must contain a cycle of size \(x - 1\). Perform an operation outside this cycle to achieve strong connectivity.

Otherwise, \(n \le 6\). Enumerate all operations to check for strong connectivity.

Time complexity: \(O(n^2)\).

CTT2020 Day2 C Basic Graph Theory Exercise

By Landau's theorem, for each edge, compute the new component count after flipping it. This involves calculating \(\sum_{i = 1}^n [\sum_{j = 1}^i p_j = \binom{i}{2}]\).

Flipping an edge changes the degree sequence by constant amounts. Use prefix sums to compute the required value efficiently.

Time complexity: \(O(n^2)\).