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

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

Турнир с 4 вершинами
вершин
рёбер:

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

Пути и циклы

Любой турнир с конечным числом вершин содержит гамильтонов путь, то есть ориентированный путь, содержащий все вершин[2]. Это легко показать с помощью математической индукции по : пусть утверждение верно для , и пусть имеется некий турнир с вершинами. Выберем вершину в и пусть  — направленный путь в . Пусть  — максимальное число такое, что для любого имеется дуга из в . Тогда

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

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

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

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

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

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

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

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

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

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

и при k превосходящем это число слишком мало, чтобы транзитивный турнир оказался в каждом из различных турниров одного и того же множества из n помеченных вершин.

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

Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир T=(V,E) называется k-парадоксальным, если для любого k-элементного подмножества S множества V существует вершина v0 в , такая что для всех . Посредством вероятностного метода Эрдёш показал, что для любого фиксированного 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) — неубывающая последовательность целых чисел является последовательностью результатов тогда и только тогда, когда:

  2. для

Пусть  — число различных последовательностей результатов размера . Последовательность начинается с:

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

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

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

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

где

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

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

Яо показал[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.
  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. 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. — Т. 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. — .
  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. — .
  13. Lajos Takács. A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. — 1991. — Т. 23, вып. 3. — С. 557—585. — doi:10.2307/1427622. — .
  14. T. X. Yao. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull. — 1989. — Т. 34. — С. 804—808.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.