WikiSort.ru - Не сортированное

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

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

Пути и циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.