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

Направленный граф, в котором каждая пара вершин имеет одну дугу

В теории графов турнир — это ориентированный граф с ровно одним ребром между каждыми двумя вершинами в одном из двух возможных направлений. Эквивалентно турнир — это ориентация неориентированного полного графа . (Однако, как ориентированные графы, турниры не являются полными: полные ориентированные графы имеют два ребра в обоих направлениях между каждыми двумя вершинами. ^[1] ) Название турнир происходит от интерпретации графа как результата кругового турнира , игры, в которой каждый игрок встречается с каждым другим ровно один раз. В турнире вершины представляют игроков, а ребра между игроками указывают от победителя к проигравшему.

Многие важные свойства турниров были исследованы Х. Г. Ландау в 1953 году для моделирования отношений доминирования в стаях кур. ^[2] Турниры также активно изучаются в теории голосования , где они могут представлять частичную информацию о предпочтениях избирателей среди нескольких кандидатов и играют центральную роль в определении методов Кондорсе .

Если каждый игрок побеждает одинаковое количество других игроков ( степень захода - степень исхода = 0), турнир называется регулярным .

Пути и циклы

a вставляется между v ₂ и v ₃ .

Любой турнир на конечном числе вершин содержит гамильтонов путь , т. е. направленный путь по всем вершинам ( Rédei 1934). ${\displaystyle n}$ ${\displaystyle n}$

Это легко показать индукцией по : предположим, что утверждение справедливо для , и рассмотрим любой турнир по вершинам. Выберем вершину из и рассмотрим направленный путь в . Существует некоторый такой, что . (Одна из возможностей — позволить быть максимальным таким образом, что для каждого . В качестве альтернативы, пусть будет минимальным таким образом, что .) — ​​это желаемый направленный путь. Этот аргумент также дает алгоритм для нахождения гамильтонова пути. Известны более эффективные алгоритмы, требующие изучения только ребер. Гамильтоновы пути находятся во взаимно однозначном соответствии с минимальными наборами дуг обратной связи турнира. ^[3] Теорема Редея является частным случаем для полных графов теоремы Галлаи–Хассе–Руа–Витавера , связывающей длины путей в ориентациях графов с хроматическим числом этих графов. ^[4] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle T}$ ${\displaystyle n+1}$ ${\displaystyle v_{0}}$ ${\displaystyle T}$ ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ ${\displaystyle T\smallsetminus \{v_{0}\}}$ ${\displaystyle i\in \{0,\ldots ,n\}}$ ${\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)}$ ${\displaystyle i\in \{0,\ldots ,n\}}$ ${\displaystyle j\leq i,v_{j}\rightarrow v_{0}}$ ${\displaystyle i}$ ${\displaystyle \forall j>i,v_{0}\rightarrow v_{j}}$ $${\displaystyle v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}}$$ ${\displaystyle O(n\log n)}$

Другой базовый результат о турнирах заключается в том, что каждый сильно связный турнир имеет гамильтонов цикл . ^[5] Более того, каждый сильно связный турнир является вершинно-панциклическим : для каждой вершины и каждой в диапазоне от трех до числа вершин в турнире существует цикл длины, содержащий . ^[6] Турнир является -сильно связным, если для каждого набора вершин , является сильно связным. Если турнир является 4-сильно связным, то каждая пара вершин может быть связана гамильтоновым путем. ^[7] Для каждого набора из не более чем дуг -сильно связного турнира мы имеем , что имеет гамильтонов цикл. ^[8] Этот результат был расширен Банг-Йенсеном, Гутином и Йео (1997). ^[9] ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle k}$ ${\displaystyle U}$ ${\displaystyle k-1}$ ${\displaystyle T}$ ${\displaystyle T-U}$ ${\displaystyle B}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle T}$ ${\displaystyle T-B}$

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

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

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

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

Следующие утверждения эквивалентны для турнира по вершинам: ${\displaystyle T}$ ${\displaystyle n}$

1. ${\displaystyle T}$является транзитивным.
2. ${\displaystyle T}$является строгим полным порядком.
3. ${\displaystyle T}$является ациклическим .
4. ${\displaystyle T}$не содержит цикла длины 3.
5. Последовательность оценок (набор исходящих степеней) равна . ${\displaystyle T}$ ${\displaystyle \{0,1,2,\ldots ,n-1\}}$
6. ${\displaystyle T}$имеет ровно один гамильтонов путь.

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

Транзитивные турниры играют роль в теории Рамсея, аналогичную роли клик в неориентированных графах. В частности, каждый турнир на вершинах содержит транзитивный подтурнир на вершинах. Доказательство простое: выберите любую вершину , которая будет частью этого подтурнира, и сформируйте остальную часть подтурнира рекурсивно либо на множестве входящих соседей , либо на множестве исходящих соседей , в зависимости от того, что больше. Например, каждый турнир на семи вершинах содержит транзитивный подтурнир из трех вершин; турнир Пейли на семи вершинах показывает, что это самое большее, что можно гарантировать. ^[10] Однако Рид и Паркер (1970) показали, что эта граница не является строгой для некоторых больших значений  . ^[11] ${\displaystyle n}$ ${\displaystyle 1+\lfloor \log _{2}n\rfloor }$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle n}$

Эрдёш и Мозер (1964) доказали, что существуют турниры на вершинах без транзитивного подтурнира размера Их доказательство использует подсчетный аргумент : число способов, которыми -элементный транзитивный турнир может возникнуть как подтурнир большего турнира на помеченных вершинах, равно , а когда больше , это число слишком мало, чтобы допустить возникновение транзитивного турнира в каждом из различных турниров на том же наборе помеченных вершин. ^[10] ${\displaystyle n}$ ${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$ ${\displaystyle k}$ ${\displaystyle n}$ $${\displaystyle {\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},}$$ ${\displaystyle k}$ ${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$ ${\displaystyle 2^{\binom {n}{2}}}$ ${\displaystyle n}$

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

Игрок, который выигрывает все игры, естественно, становится победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может и не быть. Турнир, в котором каждый игрок проигрывает хотя бы одну игру, называется 1-парадоксальным турниром. В более общем смысле, турнир называется -парадоксальным , если для каждого -элементного подмножества из существует вершина в такая, что для всех . С помощью вероятностного метода Пол Эрдёш показал, что для любого фиксированного значения , если , то почти каждый турнир на является -парадоксальным. ^[12] С другой стороны, простое рассуждение показывает, что любой -парадоксальный турнир должен иметь не менее игроков, что было улучшено Эстер и Джорджем Секерешами в 1965 году. ^[13] Существует явная конструкция -парадоксальных турниров с игроками Грэмом и Спенсером (1971), а именно турнир Пейли . ${\displaystyle T=(V,E)}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle S}$ ${\displaystyle V}$ ${\displaystyle v_{0}}$ ${\displaystyle V\setminus S}$ ${\displaystyle v_{0}\rightarrow v}$ ${\displaystyle v\in S}$ ${\displaystyle k}$ ${\displaystyle |V|\geq k^{2}2^{k}\ln(2+o(1))}$ ${\displaystyle V}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2^{k+1}-1}$ ${\displaystyle (k+2)2^{k-1}-1}$ ${\displaystyle k}$ ${\displaystyle k^{2}4^{k-1}(1+o(1))}$

Конденсация

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

Последовательности очков и наборы очков

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

Теорема Ландау (1953) Неубывающая последовательность целых чисел является последовательностью очков тогда и только тогда, когда: ^[2] ${\displaystyle (s_{1},s_{2},\ldots ,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},{\text{ for }}i=1,2,\ldots ,n-1}$
3. ${\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}$

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

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

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

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

где Такач позже показал, используя некоторые разумные, но недоказанные предположения, что ${\displaystyle c_{1}=0.049.}$

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

где ^[15] ${\displaystyle c_{2}<4.858.}$

В совокупности они свидетельствуют о том, что:

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

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

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

Отношения большинства

В теории общественного выбора турниры естественным образом возникают как отношения большинства профилей предпочтений. ^[17] Пусть будет конечным набором альтернатив и рассмотрим список линейных порядков по . Мы интерпретируем каждый порядок как рейтинг предпочтений избирателя . Тогда (строгое) отношение большинства по определяется так, что тогда и только тогда, когда большинство избирателей предпочитают , то есть . Если число избирателей нечетно, то отношение большинства образует отношение доминирования турнира на множестве вершин . ${\displaystyle A}$ ${\displaystyle P=(\succ _{1},\dots ,\succ _{n})}$ ${\displaystyle A}$ ${\displaystyle \succ _{i}}$ ${\displaystyle i}$ ${\displaystyle \succ _{\text{maj}}}$ ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle a\succ _{\text{maj}}b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle |\{i\in [n]:a\succ _{i}b\}|>|\{i\in [n]:b\succ _{i}a\}|}$ ${\displaystyle n}$ ${\displaystyle A}$

По лемме МакГарви, каждый турнир на вершинах может быть получен как отношение большинства не более чем избирателей. ^[18] Результаты Стернса и Эрдёша и Мозера позже установили, что избиратели необходимы для индукции каждого турнира на вершинах. ^[19] ${\displaystyle m}$ ${\displaystyle m(m-1)}$ ${\displaystyle \Theta (m/\log m)}$ ${\displaystyle m}$

Ласлиер (1997) изучает, в каком смысле множество вершин можно назвать множеством «победителей» турнира. ^[20] Это оказалось полезным в политологии для изучения в формальных моделях политической экономии того, каким может быть результат демократического процесса. ^[21]

Смотрите также

• Ориентированный граф
• турнир Пейли
• Гипотеза Самнера
• Турнирное решение

Примечания

1. Вайсштейн, Эрик В. , «Турнир», MathWorld
2. Ландау (1953).
3. Бар-Ной и Наор (1990).
4. Хавет (2013).
5. Камион (1959).
6. Мун (1966), Теорема 1.
7. Томассен (1980).
8. Фрейсс и Томассен (1987).
9. Банг-Дженсен, Гутин и Йео (1997).
10. Erdős & Moser (1964).
11. Рид и Паркер (1970).
12. Эрдёш (1963)
13. Секереш и Секереш (1965).
14. Харари и Мозер (1966), следствие 5b.
15. Такач (1991).
16. Яо (1989).
17. Брандт, Брилл и Харренштайн (2016).
18. МакГарви (1953); Брандт, Брилл и Харренштайн (2016)
19. Стернс (1959); Эрдеш и Мозер (1964)
20. Ласлиер (1997).
21. Остин-Смит и Бэнкс (1999).

Ссылки

• Остин-Смит, Д.; Бэнкс, Дж. (1999), Позитивная политическая теория , Издательство Мичиганского университета
• Банг-Дженсен, Дж.; Гутин, Г .; Йео, А. (1997), «Гамильтоновы циклы, избегающие предписанных дуг в турнирах», Комбинаторика, вероятность и вычисления , 6 : 255–261
• Бар-Ной, А.; Наор, Дж. (1990), «Сортировка, минимальные наборы обратной связи и гамильтоновы пути в турнирах», SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi :10.1137/0403002
• Брандт, Феликс; Брилл, Маркус; Харренштейн, Пол (2016), «Глава 3: Турнирные решения», Брандт, Феликс; Конитцер, Винсент; Эндрисс, Улле; Ланг, Жером; Прокачча, Ариэль Д. (ред.), Справочник по вычислительному социальному выбору , Cambridge University Press, ISBN 9781107060432
• Камион, Поль (1959), «Chemins et Circuits hamiltoniens desgraphes complets», Comptes Rendus de l'Académie des Sciences de Paris (на французском языке), 249 : 2151–2152.
• Эрдёш, П. (1963), «Об одной проблеме в теории графов» (PDF) , The Mathematical Gazette , 47 : 220–223, JSTOR  3613396, MR  0159319
• Эрдеш, П .; Мозер, Л. (1964), «О представлении ориентированных графов как объединений порядков» (PDF) , Magyar Tud. Акад. Мат. Кутато Междунар. Кёзл. , 9 : 125–132, МР  0168494
• Фрейсс, П.; Томассен, К. (1987), «Конструктивное решение турнирной задачи», Графы и комбинаторика , 3 : 239–250.
• Грэм, Р. Л.; Спенсер , Дж. Х. (1971), «Конструктивное решение турнирной задачи», Канадский математический вестник , 14 : 45–48, doi :10.4153/cmb-1971-007-1, MR  0292715.
• Харари, Фрэнк ; Мозер, Лео (1966), «Теория круговых турниров», American Mathematical Monthly , 73 (3): 231–246, doi :10.2307/2315334, JSTOR  2315334.
• Havet, Frédéric (2013), «Раздел 3.1: Теорема Галлаи–Руа и связанные с ней результаты» (PDF) , Ориентации и раскраска графов , Конспект лекций для летней школы SGT 2013 в Олероне, Франция, стр. 15–19
• Ландау, Х. Г. (1953), «Об отношениях доминирования и структуре сообществ животных. III. Условие для структуры оценок», Бюллетень математической биофизики , 15 (2): 143–148, doi :10.1007/BF02476378.
• Ласлиер, Ж.-Ф. (1997), Решения турниров и голосование большинства , Springer
• МакГарви, Дэвид К. (1953), «Теорема о построении парадоксов голосования», Econometrica , 21 (4): 608–610, doi :10.2307/1907926, JSTOR  1907926
• Мун, Дж. В. (1966), «О подтурнирах турнира», Канадский математический вестник , 9 (3): 297–301, doi : 10.4153/CMB-1966-038-7.
• Редей, Ласло (1934), «Ein kombinatorischer Satz», Acta Litteraria Szeged , 7 : 39–43.
• Рид, КБ; Паркер, ЕТ (1970), «Опровержение гипотезы Эрдёша и Мозера», Журнал комбинаторной теории , 9 (3): 225–238, doi : 10.1016/S0021-9800(70)80061-8
• Стернс, Ричард (1959), «Проблема голосования», The American Mathematical Monthly , 66 (9): 761–763, doi :10.2307/2310461, JSTOR  2310461
• Секерес, Э. ; Секерес, Г. (1965), «К проблеме Шютте и Эрдеша», The Mathematical Gazette , 49 : 290–293, doi : 10.2307/3612854, MR  0186566.
• Такач, Лайош (1991), «Экскурсия Бернулли и ее различные приложения», Advances in Applied Probability , 23 (3), Applied Probability Trust: 557–585, doi : 10.2307/1427622, ​​JSTOR  1427622.
• Томассен, Карстен (1980), «Гамильтоново-связанные турниры», Журнал комбинаторной теории , Серия B, 28 (2): 142–163, doi : 10.1016/0095-8956(80)90061-1.
• Яо, Техас (1989), «О гипотезе Рида о наборах очков для турниров», Chinese Sci. Bull. , 34 : 804–808.

В данной статье использованы материалы турнира PlanetMath , лицензированные по лицензии Creative Commons Attribution/Share-Alike License .