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

Турнир
Турнир на 4 вершины
Вершины	$n$
Края	${\binom {n}{2}}$
Таблица графиков и параметров

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

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

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

Пути и циклы

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

Любой турнир на конечное число $n$ вершин содержит гамильтонов путь , т. е. направленный путь на всех $n$ вершины ( Редей , 1934).

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

Другой основной результат турниров состоит в том, что каждый турнир с сильной связностью имеет гамильтонов цикл . Более строго, каждый сильно связный турнир является вершинным панциклическим : для каждой вершины $v$и каждый $k$ в диапазоне от трёх до количества вершин в турнире существует цикл длины $k$ содержащий $v$. Турнир $T$является $k$-сильно связно, если для каждого множества $U$ из $k-1$ вершины $T$, $T-U$ сильно связан. Если турнир 4-сильно связный, то каждую пару вершин можно соединить гамильтоновым путем. Для каждого набора $B$ максимум $k-1$ дуги а $k$-сильно связанный турнир $T$, у нас это есть $T-B$ имеет гамильтонов цикл. Этот результат был расширен Банг-Дженсеном, Гутином и Йео (1997) .

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

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

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

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

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

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

Теория Рэмси

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

Эрдеш и Мозер (1964) доказали, что турниры проводятся на $n$ вершины без транзитивного подтурнира размера $2+2\lfloor \log _{2}n\rfloor$ В их доказательстве используется подсчетный аргумент : количество способов, которыми $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$ есть вершина $v_{0}$ в $V\setminus S$ такой, что $v_{0}\rightarrow v$ для всех $v\in S$. С помощью вероятностного метода Пауль Эрдеш показал, что для любого фиксированного значения $k$, если $|V|\geq k^{2}2^{k}\ln(2+o(1))$, то почти каждый турнир по $V$ является $k$-парадоксально. С другой стороны, простой аргумент показывает, что любой $k$-парадоксальный турнир должен иметь как минимум $2^{k+1}-1$ игроков, который был улучшен до $(k+2)2^{k-1}-1$ Эстер Джордж и Секерес в 1965 году. Существует явная конструкция $k$-парадоксальные турниры с $k^{2}4^{k-1}(1+o(1))$ игроков Грэма и Спенсера (1971), а именно турнир Пейли .

Конденсат

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

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

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

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

1. $0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
2. $s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\text{ for }}i=1,2,\ldots ,n-1$
3. $s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.$

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

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

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

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

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

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

где $c_{2}<4.858.$

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

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

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

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

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

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

По лемме МакГарви каждый турнир по $m$ вершины могут быть получены как мажоритарное отношение не более $m(m-1)$ избиратели. Результаты Стернса , Эрдеша и Мозера позже установили, что $\Theta (m/\log m)$ избиратели необходимы, чтобы стимулировать каждый турнир на $m$ вершины.

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

См. также

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

Ссылки

• Остин-Смит, Д.; Бэнкс, Дж. (1999), Позитивная политическая теория , Издательство Мичиганского университета.
• Банг-Дженсен, Дж.; Гутин Г. ; Йео, А. (1997), «Гамильтоновы циклы, избегающие предписанных дуг в турнирах», Combinatorics, Probability and Computing , 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), «Гамильтоновы пути и схемы полных графов» , 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. Есть. Мэтт. Исследования Int. , 9 : 125–132, МР   0168494
• Фрайсс, П.; Томассен, К. (1987), «Конструктивное решение турнирной проблемы», Graphs and Combinatorics , 3 : 239–250 .
• Грэм, РЛ ; Спенсер, Дж. Х. (1971), «Конструктивное решение турнирной задачи», Canadian Mathematical Bulletin , 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 .
• Хаве, Фредерик (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
• Мун, JW (1966), «О подтурнирах турнира» , Canadian Mathematical Bulletin , 9 (3): 297–301, doi : 10.4153/CMB-1966-038-7 .
• Редей, Ласло (1934), «Ein kombinatorischer Satz», Acta Litteraria Szeged , 7 : 39–43 .
• Рид, КБ; Паркер, ET (1970), «Опровержение гипотезы Эрдеша и Мозера», Journal of Combinatorial Theory , 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), «Экскурсия Бернулли и его различные приложения», « Достижения в области прикладной теории вероятностей » , 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. Бык. , 34 : 804–808 .

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