Турниры

Определение:

Турнир (англ. Tournament) — ориентированный граф, между любой парой различных вершин которого есть ровно одно ориентированное ребро.

Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок [math]a[/math] побеждает игрока [math]b[/math], то говорят, что [math]a[/math] доминирует над [math]b[/math].

Турниры из трех вершин

Оценка количества турниров в графе

Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из [math]n[/math] вершин равно [math]2^{\frac{n\cdot(n-1)}{2}}[/math].

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

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

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

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

• [math]T[/math] транзитивен.
• [math]T[/math] ацикличен.
• [math]T[/math] не содержит циклов длины 3.
• Последовательность числа выигрышей (множество полуисходов) [math]T[/math] есть [math] 0, 1, 2,..., n - 1 [/math].
• [math]T[/math] содержит ровно один гамильтонов путь.

Транзитивные турниры играют существенную роль в теории Рамсея, изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с [math]n[/math] вершинами содержит транзитивный подтурнир с [math]1+\lfloor\log_2 n\rfloor[/math] вершинами. Для его построения выберем любую вершину [math]v[/math] как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины [math]v[/math], либо на множестве исходящих соседей, в зависимости от того, какое множество больше.

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

Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир [math]T=(V,E)[/math] называется [math]k[/math]-парадоксальным, если для любого [math]k[/math]-элементного подмножества [math]S[/math] множества [math]V[/math] существует вершина [math]v_0[/math] в [math]V\setminus S[/math], такая что [math]v_0 \rightarrow v[/math] для всех [math]v \in S[/math].

Конденсация

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

Сильно связные турниры

Определение:

Турнир называется сильно связным, если из любой вершины существуют пути до всех других.

Определение:

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

Негамильтонов турнир

Не все турниры гамильтоновы. Определение не исключает существование вершины с [math]deg^{-}[/math] или [math]deg^{+}[/math] равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

Теорема Редеи-Камиона устанавливает 2 следующих факта:

1. Все турниры полугамильтоновы.
2. Турнир гамильтонов тогда и только тогда, когда он сильно связен.

См. также

• Гамильтоновы графы
• Теорема Редеи-Камиона

Источники информации

• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы — НИЦ РХД, 2001. — ISBN 5-93972-076-5