Главная
Новости
Строительство
Ремонт
Дизайн и интерьер




13.02.2021


07.02.2021


24.01.2021


24.01.2021


24.01.2021





Яндекс.Метрика

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

02.01.2022

Турнир — это ориентированный граф, полученный из неориентированного полного графа путём назначения направления каждому ребру. Таким образом, турнир — это орграф, в котором каждая пара вершин соединена одной направленной дугой.

Много важных свойств турниров рассмотрены Ландау (Landau) для того, чтобы исследовать модель доминирования цыплят в стае. Текущие приложения турниров включают исследования в области голосования и коллективного выбора среди других прочих вещей. Имя турнир исходит из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок a {displaystyle a} побеждает игрока b {displaystyle b} , то говорят, что a {displaystyle a} доминирует над b {displaystyle b} .

Пути и циклы

Любой турнир с конечным числом n {displaystyle n} вершин содержит гамильтонов путь, то есть ориентированный путь, содержащий все n {displaystyle n} вершин. Это легко показать с помощью математической индукции по n {displaystyle n} : пусть утверждение верно для n {displaystyle n} , и пусть имеется некий турнир T {displaystyle T} с n + 1 {displaystyle n+1} вершинами. Выберем вершину v 0 {displaystyle v_{0}} в T {displaystyle T} и пусть v 1 , v 2 , … , v n {displaystyle v_{1},v_{2},ldots ,v_{n}} — направленный путь в T ∖ { v 0 } {displaystyle Tsetminus {v_{0}}} . Пусть i ∈ { 0 , … , n } {displaystyle iin {0,ldots ,n}} — максимальное число такое, что для любого j ≤ i {displaystyle jleq i} имеется дуга из v j {displaystyle v_{j}} в v 0 {displaystyle v_{0}} . Тогда

v 1 , … , v i , v 0 , v i + 1 , … , v n {displaystyle v_{1},ldots ,v_{i},v_{0},v_{i+1},ldots ,v_{n}}

— искомый ориентированный путь. Это доказательство даёт также алгоритм поиска гамильтонова пути. Известен более эффективный алгоритм, требующий перебора всего   O ( n log ⁡ n ) {displaystyle O(nlog n)} дуг.

Это означает, что строго связный турнир имеет гамильтонов цикл. Более строго: любой сильно связанный турнир является вершинно панциклическим — для любой вершины v и для любого k от трёх до числа вершин в турнире имеется цикл длины k, содержащий v. Более того, если турнир 4-связен, любая пара вершин может быть соединена гамильтоновым путём.

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

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

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

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

  • T транзитивен.
  • T ацикличен.
  • T не содержит циклов длины 3.
  • Последовательность числа выигрышей (множество полуисходов) T есть {0,1,2,…,n − 1}.
  • T содержит ровно один гамильтонов путь.
  • Теория Рамсея

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

    Эрдёш и Мозер доказали, что существуют турниры с n вершинами без транзитивных подтурниров размера 2 + 2 ⌊ log 2 ⁡ n ⌋ {displaystyle 2+2lfloor log _{2}n floor } . Их доказательство использует подсчёт: число вариантов в которых транзитивный турнир с k вершинами может содержаться в большем турнире с n помеченными вершинами, равно

    ( n k ) k ! 2 ( n 2 ) − ( k 2 ) , {displaystyle {inom {n}{k}}k!2^{{inom {n}{2}}-{inom {k}{2}}},}

    и при k превосходящем 2 + 2 ⌊ log 2 ⁡ n ⌋ {displaystyle 2+2lfloor log _{2}n floor } это число слишком мало, чтобы транзитивный турнир оказался в каждом из 2 ( n 2 ) {displaystyle 2^{inom {n}{2}}} различных турниров одного и того же множества из n помеченных вершин.

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

    Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир T=(V,E) называется k-парадоксальным, если для любого k-элементного подмножества S множества V существует вершина v0 в V ∖ S {displaystyle Vsetminus S} , такая что v 0 → v {displaystyle v_{0} ightarrow v} для всех v ∈ S {displaystyle vin S} . Посредством вероятностного метода Эрдёш показал, что для любого фиксированного k при условии |V| ≥ k22kln(2 + o(1)) почти любой турнир на V является k-парадоксальным. С другой стороны, простой аргумент показывает, что любой k-парадоксальный турнир должен иметь по меньшей мере 2k+1 − 1 игроков, что было улучшено до (k + 2)2k−1 − 1 Эстер и Дьёрдьем Секерешами (1965). Существует явный метод построения k-парадоксальных турниров с k24k−1(1 + o(1)) игроками, разработанный Грэмом и Спенсером, а именно, турнир Пэли.

    Конденсация

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

    Последовательности результатов и множества результатов

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

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

  • 0 ≤ s 1 ≤ s 2 ≤ ⋯ ≤ s n {displaystyle 0leq s_{1}leq s_{2}leq cdots leq s_{n}}
  • s 1 + s 2 + ⋯ + s i ≥ ( i 2 ) , {displaystyle s_{1}+s_{2}+cdots +s_{i}geq {i choose 2},} для i = 1 , 2 , ⋯ , n − 1 {displaystyle i=1,2,cdots ,n-1}
  • s 1 + s 2 + ⋯ + s n = ( n 2 ) . {displaystyle s_{1}+s_{2}+cdots +s_{n}={n choose 2}.}
  • Пусть 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, 14 805, 48 107, …

    (последовательность A000571 в OEIS)

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

    s ( n ) > c 1 4 n n − 5 2 , {displaystyle s(n)>c_{1}4^{n}n^{-{5 over 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 over 2}},}

    где 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 over 2}}).}

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

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