Турниры — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 57: Строка 57:
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Версия 21:38, 7 ноября 2015

Определение:
Турнир (англ. 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