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

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

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

Пути и циклы 
Любой турнир с конечным числом  вершин содержит гамильтонов путь, то есть ориентированный путь, содержащий все  вершин. Это легко показать с помощью математической индукции по : пусть утверждение верно для , и пусть имеется некий турнир  с  вершинами. Выберем вершину  в  и пусть  — направленный путь в . Пусть  — максимальное число такое, что для любого  имеется дуга из  в . Тогда

 

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

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

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

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

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

Теория Рамсея 
Транзитивные турниры играют существенную роль в теории Рамсея, аналогичную роли, которую играют клики в неориентированных графах. В частности, любой турнир с n вершинами содержит транзитивный подтурнир с  вершинами. Доказательство просто: выберем любую вершину v как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины v, либо на множестве исходящих соседей, в зависимости от того, какое множество больше. Например, любой турнир с семью вершинами содержит транзитивный турнир с тремя вершинами. Турнир Пэли с семью вершинами показывает, что это максимум, что можно гарантировать.
Однако Рейд и Паркер показали, что эта граница не строга для некоторых больших значений числа n.

Эрдёш и Мозер доказали, что существуют турниры с n вершинами без транзитивных подтурниров размера . Их доказательство использует : число вариантов в которых транзитивный турнир с k вершинами может содержаться в большем турнире с n помеченными вершинами, равно
 
и при k превосходящем  это число слишком мало, чтобы транзитивный турнир оказался в каждом из  различных турниров одного и того же множества из n помеченных вершин.

Парадоксальные турниры 
Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир T=(V,E) называется k-парадоксальным, если для любого k-элементного подмножества S множества V существует вершина v0 в , такая что  для всех .
Посредством вероятностного метода Эрдёш показал, что для любого фиксированного k при условии |V| ≥ k22kln(2 + o(1)) почти любой турнир на V является k-парадоксальным. С другой стороны, простой аргумент показывает, что любой k-парадоксальный турнир должен иметь по меньшей мере  игроков, что было улучшено до  Эстер и Дьёрдьем Секерешами (1965). Существует явный метод построения k-парадоксальных турниров с  игроками, разработанный Грэмом и Спенсером, а именно, турнир Пэли.

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

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

Теорема Ландау (1953) — неубывающая последовательность целых чисел  является последовательностью результатов тогда и только тогда, когда:
 
  для 
 

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

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, , , …

()

Уинстон и Клейтман доказали, что для достаточно больших n
 
где 
Такач позже показал, используя некоторое правдоподобное, но недоказанное предположение, что
 
где 

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

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

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

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

Примечания 

Семейства графов