Турнир (теория графов)

Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.

Турнир с 4 вершинами
вершин $n$
рёбер: ${\binom {n}{2}}$

Много важных свойств турниров рассмотрены Ландау (Landau) для того, чтобы исследовать модель доминирования цыплят в стае. Текущие приложения турниров включают исследования в области голосования и коллективного выбора среди других прочих вещей. Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок $a$ побеждает игрока $b$, то говорят, что $a$ доминирует над $b$.

Пути и циклы

Любой турнир с конечным числом $n$ вершин содержит гамильтонов путь, то есть ориентированный путь, содержащий все $n$ вершин. Это легко показать с помощью математической индукции по $n$: пусть утверждение верно для $n$, и пусть имеется некий турнир $T$ с $n+1$ вершинами. Выберем вершину $v_{0}$ в $T$ и пусть $v_{1},v_{2},\ldots ,v_{n}$ — направленный путь в $T\setminus \{v_{0}\}$. Пусть $i\in \{0,\ldots ,n\}$ — максимальное число такое, что для любого $j\leq i$ имеется дуга из $v_{j}$ в $v_{0}$. Тогда

$v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}$

— искомый ориентированный путь. Это доказательство даёт также алгоритм поиска гамильтонова пути. Известен более эффективный алгоритм, требующий перебора всего $\ O(n\log n)$ дуг.

Это означает, что строго связный турнир имеет гамильтонов цикл. Более строго: любой сильно связанный турнир является вершинно панциклическим — для любой вершины v и для любого k от трёх до числа вершин в турнире имеется цикл длины k, содержащий v. Более того, если турнир 4-связен, любая пара вершин может быть соединена гамильтоновым путём.

Транзитивность

Транзитивный турнир с 8 вершинами.

Турнир, в котором $((a\rightarrow b)$ и $(b\rightarrow c))$ $\Rightarrow$ $(a\rightarrow c)$, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.

Эквивалентные условия

Следующие утверждения для турнира с n вершинами эквивалентны:

1. T транзитивен.
2. T ацикличен.
3. T не содержит циклов длины 3 (для n != 3).
4. Последовательность числа выигрышей (множество полуисходов) T есть {0,1,2,…,n − 1}.
5. T содержит ровно один гамильтонов путь.

Теория Рамсея

Транзитивные турниры играют существенную роль в теории Рамсея, аналогичную роли, которую играют клики в неориентированных графах. В частности, любой турнир с n вершинами содержит транзитивный подтурнир с $1+\lfloor \log _{2}n\rfloor$ вершинами. Доказательство просто: выберем любую вершину v как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины v, либо на множестве исходящих соседей, в зависимости от того, какое множество больше. Например, любой турнир с семью вершинами содержит транзитивный турнир с тремя вершинами. Турнир Пэли с семью вершинами показывает, что это максимум, что можно гарантировать. Однако Рейд и Паркер показали, что эта граница не строга для некоторых больших значений числа n.

Эрдёш и Мозер доказали, что существуют турниры с n вершинами без транзитивных подтурниров размера $2+2\lfloor \log _{2}n\rfloor$. Их доказательство использует подсчёт: число вариантов в которых транзитивный турнир с k вершинами может содержаться в большем турнире с n помеченными вершинами, равно

${\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},$

и при k превосходящем $2+2\lfloor \log _{2}n\rfloor$ это число слишком мало, чтобы транзитивный турнир оказался в каждом из $2^{\binom {n}{2}}$ различных турниров одного и того же множества из n помеченных вершин.

Парадоксальные турниры

Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир T=(V,E) называется k-парадоксальным, если для любого k-элементного подмножества S множества V существует вершина v₀ в $V\setminus S$, такая что $v_{0}\rightarrow v$ для всех $v\in S$. Посредством вероятностного метода Эрдёш показал, что для любого фиксированного k при условии |V| ≥ k²2^kln(2 + o(1)) почти любой турнир на V является k-парадоксальным. С другой стороны, простой аргумент показывает, что любой k-парадоксальный турнир должен иметь по меньшей мере 2^k+1 − 1 игроков, что было улучшено до (k + 2)2^k−1 − 1 Эстер и Дьёрдьем Секерешами (1965). Существует явный метод построения k-парадоксальных турниров с k²4^k−1(1 + o(1)) игроками, разработанный Грэмом и Спенсером, а именно, турнир Пэли.

Конденсация

Конденсация любого турнира является транзитивным турниром. Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть полностью упорядочены.

Последовательности результатов и множества результатов

Последовательность результатов турнира — это неубывающая последовательность полустепеней исхода вершин турнира. Множество результатов турнира — это множество целых чисел, являющихся полустепенями исхода вершин турнира.

Теорема Ландау (1953) — неубывающая последовательность целых чисел $(s_{1},s_{2},\cdots ,s_{n})$ является последовательностью результатов тогда и только тогда, когда:

1. $0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
2. $s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},$ для $i=1,2,\cdots ,n-1$
3. $s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.$

Пусть $s(n)$ — число различных последовательностей результатов размера $n$. Последовательность $s(n)$ начинается с:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14 805, 48 107, …

(последовательность A000571 в OEIS)

Уинстон и Клейтман доказали, что для достаточно больших n

$s(n)>c_{1}4^{n}n^{-{5 \over 2}},$

где $c_{1}=0.049.$ Такач позже показал, используя некоторое правдоподобное, но недоказанное предположение, что

$s(n)<c_{2}4^{n}n^{-{5 \over 2}},$

где $c_{2}<4,858.$

Вместе это свидетельствует о том, что

$s(n)\in \Theta (4^{n}n^{-{5 \over 2}}).$

Здесь $\Theta$ отражает асимптотически строгую границу.

Яо показал, что любое непустое множество неотрицательных целых чисел является множеством результатов для некоторого турнира.

См. также

• Ориентированный граф
• Турнир Пэли
• Турнир Штокмейера
• Гипотеза Самнера