Турнир (теория графов)
Направленный граф, в котором каждая пара вершин имеет одну дугу
Турнир
Турнир на 4 вершинах
Вершины н {\displaystyle n}
Края ( н 2 ) {\displaystyle {\binom {n}{2}}}
Таблица графиков и параметров

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

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

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

Пути и циклы

a вставляется между v 2 и v 3 .

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

Это легко показать индукцией по : предположим, что утверждение справедливо для , и рассмотрим любой турнир по вершинам. Выберем вершину из и рассмотрим направленный путь в . Существует некоторый такой, что . (Одна из возможностей — позволить быть максимальным таким образом, что для каждого . В качестве альтернативы, пусть будет минимальным таким образом, что .) — ​​это желаемый направленный путь. Этот аргумент также дает алгоритм для нахождения гамильтонова пути. Известны более эффективные алгоритмы, требующие изучения только ребер. Гамильтоновы пути находятся во взаимно однозначном соответствии с минимальными наборами дуг обратной связи турнира. [3] Теорема Редея является частным случаем для полных графов теоремы Галлаи–Хассе–Руа–Витавера , связывающей длины путей в ориентациях графов с хроматическим числом этих графов. [4] н {\displaystyle n} н {\displaystyle n} Т {\displaystyle Т} н + 1 {\displaystyle n+1} в 0 {\displaystyle v_{0}} Т {\displaystyle Т} в 1 , в 2 , … , в н {\displaystyle v_{1},v_{2},\ldots,v_{n}} Т ∖ { в 0 } {\displaystyle T\smallsetminus \{v_{0}\}} я ∈ { 0 , … , н } {\displaystyle i\in \{0,\ldots ,n\}} ( я = 0 ∨ в я → в 0 ) ∧ ( в 0 → в я + 1 ∨ я = н ) {\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)} я ∈ { 0 , … , н } {\displaystyle i\in \{0,\ldots ,n\}} дж ≤ я , в дж → в 0 {\displaystyle j\leq я,v_{j}\rightarrow v_{0}} я {\displaystyle я} ∀ дж > я , в 0 → в дж {\displaystyle \forall j>i,v_{0}\rightarrow v_{j}} в 1 , … , в я , в 0 , в я + 1 , … , в н {\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 к} к {\displaystyle к} в {\displaystyle v} Т {\displaystyle Т} к {\displaystyle к} У {\displaystyle U} к − 1 {\displaystyle к-1} Т {\displaystyle Т} Т − У {\displaystyle TU} Б {\displaystyle Б} к − 1 {\displaystyle к-1} к {\displaystyle к} Т {\displaystyle Т} Т − Б {\displaystyle ТБ}

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

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

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

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

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

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

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

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

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

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

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

Конденсация

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

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

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

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

  1. 0 ≤ s 1 ≤ s 2 ≤ ⋯ ≤ s n {\displaystyle 0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}}
  2. s 1 + s 2 + ⋯ + s i ≥ ( i 2 ) ,  for  i = 1 , 2 , … , n − 1 {\displaystyle s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\text{ for }}i=1,2,\ldots ,n-1}
  3. s 1 + s 2 + ⋯ + s n = ( n 2 ) . {\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Tournament_(graph_theory)&oldid=1249350702"