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

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

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

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

Название турнира происходит от такой интерпретации графика как результат кругового турнира, в котором каждый игрок встречается с каждым другим игроком ровно один раз и в котором ничьи не происходят. В орграфе турнира вершины соответствуют игрокам. Разница между каждой парой игроков ориентирована от победителя к проигравшему. Если игрок побеждает игрока , то говорят, что он доминирует . Если каждый игрок побеждает одинаковое количество других игроков ( indegree = outdegree ), турнир называется регулярным .${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$ ${\ displaystyle b}$

Пути и циклы [ править ]

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

${\ displaystyle a}$вставляется между и .${\ displaystyle v_ {2}}$${\ displaystyle v_ {3}}$

Это легко показать индукцией по : предположим, что утверждение верно для , и рассмотрим любой турнир по вершинам. Выберите вершину из и рассмотрим ориентированный путь в . Есть такие, что . (Одна из возможностей состоит в том, чтобы быть максимальным таким образом, чтобы для каждого . В качестве альтернативы, пусть будет минимальным, чтобы .)${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle T}$${\ displaystyle n + 1}$${\ displaystyle v_ {0}}$${\ displaystyle T}$${\ displaystyle v_ {1}, v_ {2}, \ ldots, v_ {n}}$${\ Displaystyle Т \ setminus \ {v_ {0} \}}$${\ Displaystyle я \ в \ {0, \ ldots, п \}}$${\ Displaystyle (я = 0 \ vee v_ {i} \ rightarrow v_ {0}) \ клин (v_ {0} \ rightarrow v_ {i + 1} \ vee i = n)}$${\ Displaystyle я \ в \ {0, \ ldots, п \}}$${\ 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}}$

является направленным путем по желанию. Этот аргумент также дает алгоритм нахождения гамильтонова пути. Известны более эффективные алгоритмы, требующие проверки только ребер. ^[1]${\displaystyle \ O(n\log n)}$

Это означает, что турнир с сильной связью имеет гамильтонов цикл (Camion 1959). Более того, каждый сильно связанный турнир является вершинным панциклическим : для каждой вершины и каждой в диапазоне от трех до числа вершин в турнире существует цикл длины, содержащий . ^[2] Более того, если турнир 4-связный, каждая пара вершин может быть связана гамильтоновым путем (Thomassen 1980).${\displaystyle v}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$

Транзитивность [ править ]

Переходный турнир на 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}$ имеет ровно один гамильтонов путь.

Теория Рэмси [ править ]

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

Эрдеш и Мозер (1964) доказали, что существуют турниры по вершинам без транзитивного субтурнира размера. Их доказательство использует счетный аргумент : количество способов, которыми транзитивный турнир -элемент может происходить как субтурнир более крупного турнира по помеченным вершинам, равен${\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-парадоксальным турниром. В целом, турнир называется -paradoxical , если для каждого элементного подмножества из найдется вершина в такой , что для всех . С помощью вероятностного метода , Эрдёш показал , что для любого фиксированного значения , если , то почти каждый турнир на это -paradoxical. ^[4] С другой стороны, простой аргумент показывает, что любой${\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}$-paradoxical турнир должен иметь по крайней мере игроков, которая была улучшена , чтобы на Эстер и Джордж Szekeres (1965). ^[5] Грэм и Спенсер (1971) явным образом построили парадоксальные турниры с игроками, а именно турнир Пейли .${\displaystyle 2^{k+1}-1}$${\displaystyle (k+2)2^{k-1}-1}$${\displaystyle k}$${\displaystyle k^{2}4^{k-1}(1+o(1))}$

Конденсация [ править ]

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

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

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

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

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

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

куда ${\displaystyle c_{2}<4.858.}$

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

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

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

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

Отношения большинства [ править ]

В теории общественного выбора турниры естественно возникают как отношения большинства профилей предпочтений. ^[7] Пусть конечное множество альтернатив, а также рассмотреть список из линейных порядков над . Мы интерпретируем каждый порядок как рейтинг предпочтений избирателя . (Строгое) большинство отношение в течение затем определяется таким образом , что , если и только если большинство избирателей предпочитают , чтобы , то есть . Если число избирателей нечетное, то отношение большинства формирует отношение доминирования турнира по множеству вершин .${\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}$

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

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Бар-Ной, А .; Наор, J. (1990), "Сортировка, Minimal Feedback Множество и Гамильтон Дорожка в турнирах", SIAM журнал по дискретной математике , 3 (1): 7-20, DOI : 10,1137 / 0403002.
• Камион, Поль (1959), «Chemins et Circuit Hamiltoniens des Graphes Complete» , 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.
• Erdős, P .; Мозер, Л. (1964), "О представлении ориентированных графов в виде объединения порядков" (PDF) , Magyar Tud. Акад. Мат. Kutató Int. Közl. , 9 : 125–132, MR  0168494.
• Graham, RL ; Спенсер, JH (1971), "Конструктивное решение проблемы турнира", Канадский математический вестник , 14 : 45-48, DOI : 10,4153 / CMB-1971-007-1 , МР  0292715.
• Харари, Фрэнк ; Moser, Лео (1966), "Теория круглых турниров по круговой системе ", American Mathematical Monthly , 73 (3): 231-246, DOI : 10,2307 / 2315334 , JSTOR  2315334.
• Ландау, HG (1953), "О доминантности отношений и структура обществ животных III , условие для нот структуры.." Бюллетень математической биофизики , 15 (2): 143-148, DOI : 10.1007 / BF02476378.
• Ласлиер, Ж.-Ф. (1997), Турнирные решения и голосование большинством , Springer.
• Луна, JW (1966), "О subtournaments турнира , " , Канадский математический вестник , 9 (3): 297-301, DOI : 10,4153 / CMB-1966-038-7.
• Редей, Ласло (1934), «Ein kombinatorischer Satz», Acta Litteraria Szeged , 7 : 39–43.
• Рид, КБ; Паркер, Е. Т. (1970), "опровержение гипотезы Эрдеша и Moser", Журнал комбинаторной теории , 9 (3): 225-238, DOI : 10.1016 / S0021-9800 (70) 80061-8.
• Секерес, Э .; Шекереса, G. (1965), "Об одной задаче Шютте и Эрдеша", Математическая газета , 49 : 290-293, DOI : 10,2307 / 3612854 , МР  0186566.
• Takács, Лайош (1991), "Бернулли экскурсии и ее различные приложения", Прогресс в области прикладной вероятности , прикладная вероятность траст, 23 (3): 557-585, DOI : 10,2307 / 1427622 , JSTOR  1427622.
• Thomassen, Карстен (1980), "Гамильтониан-Connected Турниры", Журнал комбинаторной теории , серии 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 License .