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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Турнир с 4 вершинами
вершин n
рёбер: \binom{n}{2}

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

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

Пути и циклы[править | править исходный текст]

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

v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n

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

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

Транзитивность[править | править исходный текст]

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

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

Эквивалентные условия[править | править исходный текст]

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

  1. T транзитивен.
  2. T ацикличен.
  3. T не содержит циклов длины 3.
  4. Последовательность числа выйгрышей (множество полуисходов) T есть {0,1,2,...,n − 1}.
  5. T содержит ровно один гамильтонов путь.

Теория Рамсея[править | править исходный текст]

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

Эрдёш и Мозер [7] доказали, что существуют турниры с n вершинами без транзитивных подтурниров размера 2+2\lfloor\log_2 n\rfloor. Их доказательство использует подсчёт[en]: число вариантов в которых транзитивный турнир с k вершинами может содержаться в большем турнире с n помеченными вершинами, равно

\binom{n}{k}k!2^{\binom{n}{2}-\binom{k}{2}},

и при k превосходящем 2+2\lfloor\log_2 n\rfloor это число слишком мало, чтобы транзитивный турнир оказался в каждом из 2^{\binom{n}{2}} различных турниров одного и того же множества из n помеченных вершин.

Парадоксальные турниры[править | править исходный текст]

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

Конденсация[править | править исходный текст]

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

Последовательности счёта и множества счёта[править | править исходный текст]

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

Теорема Ландау (1953) Неубывающая последовательность целых чисел (s_1, s_2, \cdots, s_n) является последовательностью счёта тогда и только тогда, когда:

  1. 0 \le s_1 \le s_2 \le \cdots \le s_n
  2. s_1 + s_2 + \cdots + s_i \ge {i \choose 2}, для i = 1, 2, \cdots, n - 1
  3. s_1 + s_2 + \cdots + s_n = {n \choose 2}.

Пусть s(n) – число различных последовательностей счёта размера n. Последовательность s(n) начинается с:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14805, 48107, ...

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

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

s(n) > c_1 4^n n^{-{5 \over 2}},

где c_1 = 0.049. Такач позже показал [13], используя некоторое правдоподобое, но недоказанное предположение, что

s(n) < c_2 4^n n^{-{5 \over 2}},

где c_2 < 4.858.

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

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

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

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

Смотрите также[править | править исходный текст]

Замечания[править | править исходный текст]

  1. H.G. Landau On dominance relations and the structure of animal societies. III. The condition for a score structure // Bulletin of Mathematical Biophysics. — 1953. — В. 2. — Т. 15. — С. 143–148. — DOI:10.1007/BF02476378.
  2. Lázló Rédei Ein kombinatorischer Satz // Acta Litteraria Szeged. — 1934. — Т. 7. — С. 39–43..
  3. A. Bar-Noy, J. Naor Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments // SIAM Journal on Discrete Mathematics. — 1990. — В. 1. — Т. 3. — С. 7–20. — DOI:10.1137/0403002.
  4. Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. — 1959. — Т. 249. — С. 2151–2152..
  5. J. W. Moon On subtournaments of a tournament // Canadian Mathematical Bulletin. — 1966. — В. 3. — Т. 9. — С. 297–301. — DOI:10.4153/CMB-1966-038-7. Теорема 1.
  6. Carsten Thomassen Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. — 1980. — В. 2. — Т. 28. — С. 142–163. — DOI:10.1016/0095-8956(80)90061-1.
  7. 1 2 3 Paul Erdős, Leo Moser On the representation of directed graphs as unions of orderings // Magyar Tud. Akad. Mat. Kutató Int. Közl.. — 1964. — Т. 9. — С. 125–132..
  8. K.B. Reid, E.T. Parker Disproof of a conjecture of Erdös and Moser // Journal of Combinatorial Theory. — 1970. — В. 3. — Т. 9. — С. 225–238. — DOI:10.1016/S0021-9800(70)80061-8.
  9. Paul Erdős On a problem in graph theory // The Mathematical Gazette. — 1963. — Т. 47. — С. 220–223..
  10. Esther Szekeres, George Szekeres On a problem of Schütte and Erdős // The Mathematical Gazette. — 1965. — Т. 49. — С. 290–293..
  11. Ronald Graham, Joel Spencer A constructive solution to a tournament problem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathématiques. — 1971. — Т. 14. — С. 45–48..
  12. Frank Harary, Leo Moser The theory of round robin tournaments // American Mathematical Monthly. — 1966. — В. 3. — Т. 73. — С. 231–246. — DOI:10.2307/2315334.
  13. Lajos Takács A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. — 1991. — В. 3. — Т. 23. — С. 557–585. — DOI:10.2307/1427622
  14. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull.. — 1989. — Т. 34. — С. 804–808..

Ссылки[править | править исходный текст]