Турниры

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

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

Турниром из [math]n[/math] вершин можно изобразить исход игры между [math]n[/math] людьми, где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.

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

Свойства турниров

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

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

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

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

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

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

• [math]T[/math] транзитивен,
• [math]T[/math] ацикличен,
• [math]T[/math] не содержит циклов длины [math]3[/math],
• множества, составленные из [math]\deg^{-}[/math] или [math]\deg^{+}[/math] для каждой вершины [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], либо на множестве исходящих соседей, в зависимости от того, какое множество больше.

Конденсация

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

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

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

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

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

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

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

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

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

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

См. также

• Гамильтоновы графы
• Теорема Редеи-Камиона
• Поиск гамильтонова цикла за [math]O(n\cdot log(n))[/math]

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

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