WikiDer > Турнир (теория графов) - Википедия

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

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

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

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

Пути и циклы

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

${ 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> я, v_ {0} rightarrow v_ {j}}$.)

${ displaystyle v_ {1}, ldots, v_ {i}, v_ {0}, v_ {i + 1}, ldots, v_ {n}}$

является направленным путем по желанию. Этот аргумент также дает алгоритм нахождения гамильтонова пути. Более эффективные алгоритмы, требующие только изучения ${ Displaystyle О (п журнал п)}$ ребер известны.^[1]

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

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

Переходный турнир на 8 вершин.

Турнир, в котором ${ displaystyle ((а rightarrow b)}$ и ${ displaystyle (b rightarrow c))}$ ${ displaystyle Rightarrow}$ ${ displaystyle (а 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, п-1 }}$.
6. ${ displaystyle T}$ имеет ровно один гамильтонов путь.

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

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

Эрдеш и Мозер (1964) доказал, что есть турниры по ${ displaystyle n}$ вершины без транзитивного субтурнира размера ${ Displaystyle 2 + 2 lfloor log _ {2} п 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} п rfloor}$, это число слишком мало, чтобы допустить переходный турнир в каждом из ${ Displaystyle 2 ^ { binom {п} {2}}}$ разные турниры на одном и том же наборе ${ displaystyle n}$ помеченные вершины.

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

Игрок, выигравший все игры, естественно, становится победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не быть. Турнир, в котором каждый игрок проигрывает хотя бы одну игру, называется 1-парадоксальным турниром. В более общем смысле, турнир ${ Displaystyle Т = (В, Е)}$ называется ${ 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 | В | geq k ^ {2} 2 ^ {k} ln (2 + о (1))}$, то почти каждый турнир по ${ displaystyle V}$ является ${ displaystyle k}$-парадоксально.^[4] С другой стороны, простой аргумент показывает, что любой ${ displaystyle k}$-парадоксальный турнир должен иметь не менее ${ displaystyle 2 ^ {k + 1} -1}$ игроков, который был улучшен до ${ Displaystyle (к + 2) 2 ^ {к-1} -1}$ к Эстер и Джордж Секерес (1965).^[5] Существует явная конструкция ${ displaystyle k}$-парадоксальные турниры с ${ Displaystyle к ^ {2} 4 ^ {к-1} (1 + о (1))}$ игроков Грэм и Спенсер (1971), а именно Пейли турнир.

Конденсация

В конденсация любого турнира сам по себе является переходным турниром. Таким образом, даже для турниров, которые не являются транзитивными, сильносвязные компоненты турнира могут быть полностью упорядочены.^[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}.}$

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

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)$

куда ${ 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 _ {п})}$ из линейные порядки над ${ displaystyle A}$. Мы интерпретируем каждый заказ ${ Displaystyle succ _ {я}}$ как рейтинг предпочтений избирателя ${ displaystyle i}$. (Строгое) отношение большинства ${ displaystyle succ _ { text {maj}}}$ из ${ displaystyle P}$ над ${ displaystyle A}$ затем определяется так, что ${ displaystyle a succ _ { text {maj}} b}$ тогда и только тогда, когда большинство избирателей предпочитают ${ displaystyle a}$ к ${ displaystyle b}$, то есть ${ Displaystyle | {я in [n]: a succ _ {i} b } |> | {i in [n]: b succ _ {i} a } |}$. Если число ${ displaystyle n}$ голосов избирателей нечетно, то отношение большинства образует отношение доминирования турнира на множестве вершин ${ displaystyle A}$.

По лемме МакГарви каждый турнир на ${ displaystyle m}$ вершины могут быть получены как мажоритарное отношение не более чем ${ Displaystyle м (м-1)}$ избиратели.^[7][8] Результаты по Stearns и Erdős & Moser позже установили, что ${ Displaystyle Theta (м / журнал м)}$ избиратели нужны, чтобы побудить каждый турнир ${ displaystyle m}$ вершины.^[9]

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

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

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

Примечания

Рекомендации

• Бар-Ной, А .; Наор, Дж. (1990), "Сортировка, минимальные наборы обратной связи и пути Гамильтона в турнирах", Журнал SIAM по дискретной математике, 3 (1): 7–20, Дои:10.1137/0403002.
• Камион, Пол (1959), "Chemins et Circuit Hamiltoniens des graphes завершает", Comptes Rendus de l'Académie des Sciences de Paris (На французском), 249: 2151–2152.
• Эрдеш, П. (1963), «О проблеме теории графов» (PDF), Математический вестник, 47: 220–223, JSTOR 3613396, МИСТЕР 0159319.
• Эрдеш, П.; Мозер, Л. (1964), «О представлении ориентированных графов в виде объединения порядков» (PDF), Мадьяр Туд. Акад. Мат. Kutató Int. Közl., 9: 125–132, МИСТЕР 0168494.
• Грэм, Р. Л.; Спенсер, Дж. Х. (1971), «Конструктивное решение турнирной задачи», Канадский математический бюллетень, 14: 45–48, Дои:10.4153 / cmb-1971-007-1, МИСТЕР 0292715.
• Харари, Фрэнк; Мозер, Лев (1966), «Теория круговых турниров», Американский математический ежемесячный журнал, 73 (3): 231–246, Дои:10.2307/2315334, JSTOR 2315334.
• Ландау, Х.Г. (1953), "Об отношениях доминирования и структуре обществ животных. III. Условие для оценки структуры", Бюллетень математической биофизики, 15 (2): 143–148, Дои:10.1007 / BF02476378.
• Ласлиер, Ж.-Ф. (1997), Турнирные решения и голосование большинством, Springer.
• Мун, Дж. У. (1966), «О субтурнирах турнира», Канадский математический бюллетень, 9 (3): 297–301, Дои:10.4153 / CMB-1966-038-7.
• Редей, Ласло (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged, 7: 39–43.
• Reid, K.B .; Паркер, Э. (1970), «Опровержение гипотезы Эрдеша и Мозера», Журнал комбинаторной теории, 9 (3): 225–238, Дои:10.1016 / S0021-9800 (70) 80061-8.
• Секереш, Э.; Секереш, Г. (1965), "О проблеме Шютте и Эрдеша", Математический вестник, 49: 290–293, Дои:10.2307/3612854, МИСТЕР 0186566.
• Такач, Лайош (1991), "Экскурсия Бернулли и ее различные применения", Достижения в прикладной теории вероятностей, Applied Probability Trust, 23 (3): 557–585, Дои:10.2307/1427622, JSTOR 1427622.
• Томассен, Карстен (1980), "Гамильтоново-связанные турниры", Журнал комбинаторной теории, Серия B, 28 (2): 142–163, Дои:10.1016/0095-8956(80)90061-1.
• Яо, Т. (1989), «О гипотезе Рида о наборах очков для турниров», Chinese Sci. Бык., 34: 804–808.

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