1. 概要

任意の相異なる $2$ 頂点 $u,v$ について，$u\to v$ または $v\to u$ のどちらか一方が必ず存在するような単純有向グラフをトーナメントといいます．これは $N$ 人が総当たり戦をしたときの勝敗を，「勝った人から負けた人へ辺を張る」ことで表したものだと考えることができます．

定義は非常に簡潔ですが，トーナメントには一般の有向グラフには見られない強い構造が現れます．例えば，強連結成分同士の間には自然な順序があり，各頂点の入次数だけから強連結成分分解が決定できてしまいます．またトーナメントにはハミルトンパスが必ず存在します．

本記事ではこのような，トーナメントについて成り立つ基礎的な性質を解説します．

2. 前提知識

入次数，出次数，強連結成分，DAG などの有向グラフの用語を仮定します．グラフ理論用語集を参照してください．

なお，強連結成分分解のアルゴリズムは本記事では不要です．

また，6.2 節のみ，ソートアルゴリズムに関する知識を踏まえた解説をしています．（スキップ可能です．）

3. トーナメント

トーナメントの定義（グラフ理論用語集）を復習します．

【定義 1】
単純有向グラフであって，任意の相異なる $2$ 頂点 $u,v$ に対して $u\to v$ または $v\to u$ のうちちょうど一方の辺が存在するものをトーナメント（tournament）といいます．

トーナメントは $\boldsymbol{N}$ 人が総当たり戦をした場合の勝敗結果をグラフ理論的に表したものだといえます．辺 $u\to v$ が「$u$ が $v$ に勝った」という関係を表すと考えるとよいでしょう．

総当たり戦の結果が $N\times N$ の表として表されることが多いのと同様に，トーナメントは隣接行列として入出力されることが多いです．有向グラフの隣接行列とは，$N\times N$ 行列であって，$(i,j)$ 成分が有向辺 $i\to j$ の個数と等しいものをいいます．例えば上の図のトーナメントの隣接行列は次のようになります．

$$ \begin{pmatrix} 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} $$

本記事の以下の部分では，「辺 $\boldsymbol{i\to j}$ が存在する」ことを単に「$\boldsymbol{i\to j}$ である」と書くことにします．

4. 推移的トーナメント

トーナメントのうち，ある意味で最も極端な例が，本節で扱う推移的トーナメントです．これは，力関係がはっきりと順序付けられている $N$ 人の総当たり戦の結果に対応します．

【定義 2】
$N$ 頂点のトーナメント $T$ が推移的（transitive）であるとは，$N$ 頂点を適当な順に $v_1,v_2,\dots,v_{N}$ とすることで，任意の $i < j$ に対して $v_i\to v_j$ であるようにできることをいう．

推移的トーナメントにはいくつかの同値な特徴付けがあります．

【定理 3】
トーナメント $T$ について，次は同値である．

$T$ は推移的である．
$T$ は DAG である．
$T$ は長さ $3$ のサイクルを含まない．
任意の相異なる頂点 $u,v,w$ に対して，$u\to v$ かつ $v\to w$ ならば，$u\to w$ である（推移律）．

1 を仮定して 2 を示します．頂点が $1, \ldots, N$ で，$i<j$ ならば $i\to j$ であるようなトーナメントが DAG であることを示せばよいです．このトーナメントのウォークの頂点列 $i_1,i_2,\ldots,i_k$ について $i_1<i_2<\cdots<i_k$ が成り立つので，$k\geq 2$ について $i_1=i_k$ となることはありません．したがってサイクルが存在しないため，DAG です．

2 が成り立つならば 3 が成り立つことは DAG の定義から明らかです．

3 を仮定して 4 を示します．$u\to v$, $v\to w$ であるとします．このとき $w\to u$ であるとすると長さ $3$ のサイクル $u\to v, v\to w, w\to u$ ができてしまいます．したがって $w\to u$ ではないので，$T$ がトーナメントであることから $u\to w$ です．

最後に 4 （推移律）を仮定して 1 を示します．頂点 $v$ に対して $N ^ +(v)$ を，$v\to w$ であるような $w$ 全体とします．推移律より $u\to v$ であるとき，$N ^ +(v)\cup\lbrace v\rbrace \subseteq N ^ +(u)$ が成り立ちます．

$N ^ +(v)$ の要素数 $|N ^ +(v)|$ について $T$ の頂点全体を降順ソートし，$v_1, v_2, \ldots, v_N$ とします（要素数が等しいときには適当な順でソートします）．

$i<j$ に対して辺 $v_j\to v_i$ が存在すると，$N ^ +(v_i)\cup\lbrace v_i\rbrace \subseteq N ^ +(v_j)$ より $|N ^ +(v_i)|<|N ^ +(v_j)|$ となり，降順ソートしていたことに矛盾します．したがって $v_j\to v_i$ ではありません．$T$ がトーナメントであることから $v_i\to v_j$ です．

したがってこの頂点順は【定義 2】の条件を満たし，$T$ は推移的です． $\blacksquare$

参考：三すくみ

推移的ではないトーナメントには，長さ $3$ のサイクル $a\to b, b\to c, c\to a$ が存在します．このような $a,b,c$ の関係は三すくみと呼ばれることがあります．

例えばじゃんけんにおける，グー・チョキ・パーの関係が三すくみとして有名です．

5. トーナメントの強連結成分分解

5.1. 強連結成分間の辺

4 節で見たように，トーナメントが DAG である場合には，頂点に上手く番号をつけると辺の向きは番号の大小関係と一致することが分かります．

同じようにトーナメントの強連結成分についても，上手く番号をつけると，成分の間の辺の向きが番号の大小関係と一致することが分かります．

【定理 4】

トーナメント $T$ が $K$ 個の強連結成分を持つとする．これらの強連結成分を適当な順に $C_1,C_2,\dots,C_{K}$ とすることで，次が成り立つようにできる：$i < j$ ならば，任意の $u\in C_i$ と $v\in C_j$ に対して $u\to v$．

各 $C_i$ から頂点をひとつ選び，$c_i$ としましょう．頂点集合 $S=\lbrace c_1,c_2,\ldots,c_{K}\rbrace$ による誘導部分グラフ $T[S]$ はトーナメントであり DAG なので，推移的トーナメントです．よって適当に添字を付けなおすことで，$i<j$ ならば $c_i\to c_j$ であるようにできます．

このとき $i<j$ について $u\in C_i$，$v\in C_j$ とすると，$u$ から $v$ へのウォークが存在します（$u$ から $c_i$ へのウォーク，$c_i$ から $c_j$ への辺，$c_j$ から $v$ へのウォークを結合したもの）．このことと $u, v$ が相異なる強連結成分の頂点であることから，$v\to u$ ではありません．よって $u\to v$ です． $\blacksquare$

本記事の以下の部分では，強連結成分 $C_1, C_2, \ldots, C_{K}$ と書いた場合，【定理 4】のように添字付けられているものとします．

5.2. 強連結成分分解とカット

【定義 5】

$T$ をトーナメント（あるいはより一般の有向グラフ），$S$ を $T$ の頂点からなる集合とするとき，有向辺の集合 $\delta^+(S), \delta^-(S)$ を

$$ \begin{aligned} \delta ^ +(S)&=\lbrace v\to w\mid v\in S, w\notin S\rbrace, \\\ \delta ^ -(S)&=\lbrace v\to w\mid v\notin S, w\in S\rbrace \end{aligned} $$

により定義する．

【定理 6】

$T$ をトーナメント，$C_1, C_2, \ldots, C_{K}$ をその強連結成分とする．このとき，頂点集合 $S$ について次は同値である．

ある $k$ （$0\leq k\leq K$）に対して $S=C_1\cup C_2\cup \cdots \cup C_{k}$ が成り立つ．（ただし，$k=0$ のとき右辺は $\emptyset$ であるとする．）
$\delta ^ -(S)=\emptyset$．

【定理 4】より 1 が成り立つならば 2 も成り立ちます．逆を示します．

$S=\emptyset$ のときは $k=0$ が条件を満たします．$S\neq \emptyset$ のとき $S\cap C_{k}\neq\emptyset$ であるような最大の整数 $k$ をとり，条件を満たすことを示します．

$k$ のとり方から $S\subseteq C_1\cup C_2\cup \cdots \cup C_{k}$ は明らかです．逆の包含を示します．

$v\in C_i$（$1\leq i \leq k$）とすると，$C_{k}$ のすべての頂点に対して $v$ からのウォークが存在します．したがって $v$ から $S$ の頂点へのウォークが存在します．すると $\delta ^ -(S)=\emptyset$ の仮定から $v\in S$ が成り立ちます． $\blacksquare$

5.3. 入次数列と強連結成分分解

5.1, 5.2 節で見たように，トーナメントの強連結成分はかなり強い構造があります．このことから，トーナメントの強連結成分分解も一般の有向グラフの場合よりも簡単に求められる場合がよくあります．（ただしすべての辺が入力で与えられるようなトーナメントでは入力に $\mathrm{O}(N ^ 2)$ 時間がかかるので，そのような場合には計算量オーダーの意味で一般の有向グラフに対するアルゴリズムを上回るわけではありません．）

特に，何らかの基準によって頂点列をソートして，【定理 6】のような境界 $S$ を見つけるという手法が有効になることがあります．ここではそのような一例として，トーナメントにおいては頂点の入次数だけから強連結成分分解が求まることを示します．

頂点 $v$ の入次数を $\deg ^ - (v)$ と書きます．

【補題 7】
$i < j$ かつ $u\in C_i, v\in C_j$ ならば $\deg ^ - (u) < \deg ^ - (v)$ が成り立つ．

【定理 4】から明らかです．

【定理 8】

トーナメント $T$ の頂点を $v_1,v_2, \ldots, v_{N}$ とし，入次数が広義単調増加である，つまり

$$ \deg ^ - (v_1) \leq \deg ^ - (v_2) \leq \cdots \leq \deg ^ - (v _ N) $$

が成り立つとする．このとき次が成り立つ．

$S$ が【定理 6】の条件を満たすならば，ある $k$ に対して $S=\lbrace v_1,v_2,\ldots,v_k\rbrace$ が成り立つ．
$S=\lbrace v_1,v_2,\ldots,v_k\rbrace$ が【定理 6】の条件を満たすことと， $\displaystyle \sum_{v\in S}\deg ^ - (v)=\binom{k}{2}$ が成り立つことは同値である．

1 は補題より明らかです．

2 を示します．$\displaystyle \sum_{v\in S}\deg ^ - (v)$ は，$S$ の頂点を終点とする辺の個数です．これは次の和です．

始点，終点ともに $S$ に含まれる辺の個数．
始点が $S$ に含まれず，終点が $S$ に含まれる辺の個数．つまり $|\delta ^ - (S)|$．

トーナメントにおいて前者の辺の個数は $\binom{k}{2}$ です．よって $\displaystyle \sum_{v\in S}\deg ^ - (v)=\binom{k}{2}$ は $\delta ^ - (S) =\emptyset$ と同値です． $\blacksquare$

【系 9】

トーナメントの強連結成分分解は，各頂点の入次数だけから定まる．

【定理 8】から明らかです． $\blacksquare$

6. ハミルトンパス

6.1. ハミルトンパスの存在証明

【定理 10】（Rédei の定理）
頂点数 $N$ が $1$ 以上のトーナメントにはハミルトンパスが存在する．

$N$ に関する帰納法により示します．$N$ を正整数とし，$N$ について成り立つとして，$N + 1$ の場合に示します．

トーナメントの頂点を $1, 2, \ldots, N, N + 1$ とします．頂点集合 $\lbrace 1, 2, \ldots, N\rbrace$ に関する誘導部分グラフについて帰納法の仮定を用いることで，これら $N$ 頂点すべてを通るパスが存在します．必要があれば頂点番号を入れ替えることで，頂点列 $(1, 2, \ldots, N)$ がパスであるとしてよいです．

$N+1\to 1$ ならば，頂点列 $(N+1, 1, 2, \ldots, N)$ がハミルトンパスになります．
$N \to N+1$ ならば，頂点列 $(1, 2, \ldots, N, N+1)$ がハミルトンパスになります．
このどちらでもないとき，$i\to N+1, N+1 \to i+1$ となる $i$（$1\leq i\leq N-1$）が存在します（例えば $i \to N+1$ となる最大の $i$ が条件を満たします）．このとき，$(1, 2, \ldots, i, N+1, i+1, \ldots, N)$ がハミルトンパスになります．

以上により示されました． $\blacksquare$

アルゴリズム，計算量について

上の証明はそのままハミルトンパスを構築するアルゴリズムになります． $i\to N+1, N+1\to i+1$ となる $i$ を見つけることは，二分探索により $\mathrm{O}(\log N)$ 時間でできます．

見つけた $i,i+1$ の間に $N+1$ を挿入する部分を単純な配列操作で行えば，計算量は $\mathrm{O}(N ^ 2)$ となります．挿入に適切なデータ構造を用いれば $\mathrm{O}(N\log N)$ 時間にもなりますが，$\mathrm{O}(N\log N)$ 時間での構築に拘る場合には 6.2 節の方法の方が実装が簡潔だと思います．

6.2. 参考：比較ソートとの関係

与えられるトーナメント $T$ が推移的な場合には，ハミルトンパスを求める問題は，「$i\to j$ であるときに $i<j$ と見なす」という順序によって頂点をソートする問題と等価です．

このことを踏まえて改めて，$T$ が推移的な場合に 6.1 節のアルゴリズムを見直すと，ソート列の適切な位置に新しい頂点をひとつずつ挿入していくという挿入ソートと同様の手順になっていることが確認できます．言い換えれば，6.1 節のアルゴリズムは，トーナメントの辺の向きを，推移的でない場合にも無理やり大小関係と考えて，挿入ソートを行ったものです．計算量についても挿入ソートと同様になっています．

この考え方は，挿入ソートに限らず，多くの比較ソート（クイックソート，マージソートなど）にも当てはまります．つまり，トーナメントの辺の向きを大小関係と考えて比較ソートを実行すると，得られた出力列 $v_1,v_2,\ldots,v_N$ はハミルトンパスになります．これらのアルゴリズムでは，最終的に隣り合う $2$ 要素 $v_i, v_{i+1}$ はアルゴリズムの過程で比較され，その比較結果と整合する順序で並ぶためです．

例えば，クイックソートを元に考えることで，【定理 10】は次のように証明することもできます．

適当な頂点 $v$ （ピボット）をとり，$x\to v$ となる $x$ 全体を $L$，$v\to x$ となる $x$ 全体を $R$ とする．
頂点集合 $L, R$ について再帰的にハミルトンパスを求める．$L$ のハミルトンパス，$v$，$R$ のハミルトンパスをこの順に結合することで全体のハミルトンパスを得る．

計算量についてもクイックソートと同様で，ピボットを乱択することで期待時間計算量 $\mathrm{O}(N\log N)$ が達成されます．（計算量解析の議論もおおよそ同様ですが，トーナメントの入次数，出次数に関する議論が必要です．）

また，マージソートを元に考えることで，乱択を使わずに時間計算量 $\mathrm{O}(N\log N)$ でハミルトンパスを見つけることもできます．

7. ハミルトンサイクル

トーナメントにはハミルトンパスが存在することを示しましたが，強連結かつ頂点数 $3$ 以上の場合には，より強くハミルトンサイクルも存在します．

【定理 11】（Camion の定理）
頂点数 $N$ が $3$ 以上の強連結なトーナメントにはハミルトンサイクルが存在する．

【定理 10】の証明と似た，サイクルに頂点やパスを挿入していくというタイプの議論により証明します．

まず，ハミルトンパス $v_1\to v_2\to \cdots \to v_N$ をひとつとります．$N\geq 3$ かつ強連結であることから，辺 $v_k\to v_1$ が存在します．このような $k$ をひとつとります．結果，次のような状況が得られています．

$$v_1\to v_2\to \cdots \to v_N,\quad v_k\to v_1$$

$k < N$ であるとして，適当に頂点番号をつけなおすことなどでこの状況が成り立つ $k$ を大きくできることを示せばよいです．

まず，$v _ {k+1}\to v_1$ である場合には，頂点番号をそのまま $k$ を $k+1$ にとりかえてもこの状況が維持されるのでよいです．以下 $v _ 1 \to v _ {k+1}$ であるとします．$v _ {k+1} \to v_p$ となる $p\leq k$ が存在するならば，そのうち最小のものをとれば，$2 \leq p, v _ {p - 1}\to v _ {k + 1}, v _ {k + 1}\to v_p$ が成り立ちます．したがって，$v _ {p-1}$ と $v _ p$ の間に $v _ {k+1}$ を挿入することで，$k$ を大きくすることができます．形式的には，$v_p,\ldots,v_k,v_1,\ldots,v _ {p-1},v _ {k+1}$ を改めて $v_1,v_2,\ldots,v _ {k+1}$ ととりなおし，$k$ を $k+1$ にとりかえればよいです．

次に，任意の $p$ （$p\leq k$）について $v_p\to v _ {k+1}$ であると仮定します．強連結性の仮定から，$v_q\to v_p$ となる $p\leq k, k+2\leq q$ が存在します．$p=1$ であれば，頂点番号をそのまま $k$ を $q$ にとりかえることができます．$2\leq p$ であるとします．$v _ {p-1}\to v _ {k+1}, v_q\to v_p$ であることから，$v _ {p-1}$ と $v_p$ の間にパス $v _ {k+1}\to \cdots\to v_q$ を挿入することができます．形式的には $v_p,\ldots,v_k,v_1,\ldots,v _ {p-1},v _ {k+1},\ldots,v_q$ を改めて $v_1,v_2,\ldots,v_q$ ととりなおし，$k$ を $q$ にとりかえればよいです． $\blacksquare$

アルゴリズム，計算量について

上の証明はそのままハミルトンサイクルを構築するアルゴリズムになります．

$v_q$ を見つけるときに，手前側の頂点から順に調べることで，同じ組 $(i,j)$ 間での辺の存在判定回数が $\mathrm{O}(1)$ 回になり，適切に実装すれば，$\mathrm{O}(N ^ 2)$ 時間でハミルトンサイクルを構築することができます．

8. 2-king

最後に，トーナメントに関するこれまでとは少し方向性の異なる定理として，$2$-king と呼ばれる頂点の存在を紹介します．

【定理 12】（Landau の定理）

空でないトーナメントについて，ある頂点 $v$ が存在して次が成り立つ：任意の頂点 $x$ について，$v$ から $x$ への距離は $2$ 以下である．つまり，$x\neq v$ ならば次のどちらかが成り立つ．

$v\to x$．
ある頂点 $y$ に対して $v\to y, y\to x$．

$v$ が出次数最大の頂点であるときに，この条件が成り立つことを示します．反例となる頂点 $x$ が存在したと仮定します．

このとき，$v\to y, y\to x$ となる $y$ が存在しないことから，$v\to y$ ならば $x\to y$ が成り立ちます．つまり $N ^ +(v)\subseteq N ^ +(x)$ が成り立ちます．さらに $v\to x$ ではないことから $x\to v$ なので，$N ^ +(v)\cup\lbrace v\rbrace \subseteq N ^ +(x)$ が成り立ちます．したがって $v$ の出次数よりも $x$ の出次数の方が大きいことになりますが，これは $v$ が出次数最大の頂点であることに矛盾します． $\blacksquare$

9. 関連問題

問題について

1 は三すくみを見つける問題です．

2, 3 はトーナメントの強連結成分分解に関する問題です．2 はインタラクティブ問題なのですが，質問 $0$ 回で解けてしまいます．4 は厳密にはトーナメントではないのですが，トーナメントと似た設定で，やはり強連結成分境界を探すという解法が想定されています．

5, 6, 7 はトーナメントの強連結成分分解の構造をもとにした数え上げ問題です．

8, 9 はトーナメントのハミルトンパスを見つける問題です．

10, 11 は 2-king を題材とした問題です．

12, 13, 14, 15, 16 はトーナメントを題材とした難易度が高めの問題です．

10. まとめ

本記事では，トーナメントについて成り立つ基本的な定理を解説しました．

一般の有向グラフではハミルトンパスやハミルトンサイクルの存在判定は非常に難しい問題ですが，トーナメントはそれらの存在判定や構築が比較的簡潔に行えるグラフの代表例です．

また，強連結成分分解の構造やハミルトンパス・ハミルトンサイクルの構成では，トーナメントにおける辺の向きが順序を表すかのように振る舞う場合があることが感じられたと思います．このことは，トーナメントが $N$ 人で総当たり戦をした場合の勝敗結果を表したものだと考えると，自然に感じられるかもしれません．

11. 参考文献

Wikipedia．Tournament (graph theory)．https://en.wikipedia.org/wiki/Tournament_(graph_theory)．（閲覧日: 2026-04-01）．
Yannis Manoussakis．A linear-time algorithm for finding Hamiltonian cycles in tournaments．Discrete Applied Mathematics．Vol. 36．pp. 199–201．1992．DOI: 10.1016/0166-218X(92)90233-Z．https://doi.org/10.1016/0166-218X(92)90233-Z．
Amotz Bar-Noy, Joseph Naor．Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments．SIAM Journal on Discrete Mathematics．Vol. 3．No. 1．pp. 7–20．1990．DOI: 10.1137/0403002．https://doi.org/10.1137/0403002．

トップページ：AtCoder Algorithm Lectures