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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Турнир с 4 вершинами
вершин [math]\displaystyle{ n }[/math]
рёбер: [math]\displaystyle{ \binom{n}{2} }[/math]

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

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

Пути и циклы

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

[math]\displaystyle{ v_1,\ldots,v_i,v_0,v_{i+1},\ldots,v_n }[/math]

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

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

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

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

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

Эквивалентные условия

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

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

Теория Рамсея

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

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

[math]\displaystyle{ \binom{n}{k}k!2^{\binom{n}{2}-\binom{k}{2}}, }[/math]

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

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

Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир T=(V,E) называется k-парадоксальным, если для любого k-элементного подмножества S множества V существует вершина v0 в [math]\displaystyle{ V\setminus S }[/math], такая что [math]\displaystyle{ v_0 \rightarrow v }[/math] для всех [math]\displaystyle{ v \in S }[/math]. Посредством вероятностного метода Эрдёш показал, что для любого фиксированного 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].

Конденсация

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

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

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

Теорема Ландау (1953) — неубывающая последовательность целых чисел [math]\displaystyle{ (s_1, s_2, \cdots, s_n) }[/math] является последовательностью результатов тогда и только тогда, когда:

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

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

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

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

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

[math]\displaystyle{ s(n) \gt c_1 4^n n^{-{5 \over 2}}, }[/math]

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

[math]\displaystyle{ s(n) \lt c_2 4^n n^{-{5 \over 2}}, }[/math]

где [math]\displaystyle{ c_2 \lt 4,858. }[/math]

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

[math]\displaystyle{ s(n) \in \Theta (4^n n^{-{5 \over 2}}). }[/math]

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

Яо показал[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. — Т. 15, вып. 2. — С. 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. — Т. 3, вып. 1. — С. 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. — Т. 9, вып. 3. — С. 297—301. — doi:10.4153/CMB-1966-038-7. Архивировано 3 марта 2016 года.
  6. ↑ Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28, вып. 2. — С. 142—163. — doi:10.1016/0095-8956(80)90061-1.
  7. ↑ 7,0 7,1 7,2 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. Архивировано 13 декабря 2013 года.
  8. ↑ K. B. Reid, E. T. Parker. Disproof of a conjecture of Erdös and Moser // Journal of Combinatorial Theory. — 1970. — Т. 9, вып. 3. — С. 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. — JSTOR 3613396. Архивировано 22 декабря 2014 года.
  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. — Т. 73, вып. 3. — С. 231—246. — doi:10.2307/2315334. — JSTOR 2315334.
  13. ↑ Lajos Takács. A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. — 1991. — Т. 23, вып. 3. — С. 557—585. — doi:10.2307/1427622. — JSTOR 1427622.
  14. ↑ T. X. Yao. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull. — 1989. — Т. 34. — С. 804—808.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Турнир_(теория_графов)&oldid=12828817