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

Турнір з 4 вершинами:
вершин $n$,
ребер $(\genfrac{}{}{0ex}{}{n}{2})$

Турнір — це орієнтований граф, отриманий з неорієнтованого повного графа призначенням напрямку кожному ребру. Таким чином, турнір — це орграф, у якому кожна пара вершин з'єднана однією напрямленою дугою.

Багато важливих властивостей турнірів розглянув Ландау (H. G. Landau), досліджуючи модель домінування курчат у зграї. Нині турніри застосовують для досліджень у галузі голосування і Шаблон:Не перекладено серед інших речей. Ім'я турнір походить від графічної інтерпретації результатів кругового турніру, в якому кожен гравець зустрічається в сутичці з кожним іншим гравцем рівно раз, і в якому не може бути нічиєї. В орграфі турніру вершини відповідають гравцям. Дуга між кожною парою гравців орієнтована від переможця до переможеного. Якщо гравець $a$ перемагає гравця $b$, то кажуть, що $a$ домінує над $b$.

Шляхи й цикли

Будь-який турнір зі скінченним числом $n$ вершин містить гамільтонів шлях, тобто орієнтований шлях, що містить усі $n$ вершин. Це легко показати за допомогою математичної індукції за $n$: нехай твердження істинне для $n$, і нехай є якийсь турнір $T$ з $n+1$ вершиною. Виберемо вершину $v_0$ у $T$ і нехай $v_1,v_2,\dots ,v_n$ — напрямлений шлях у $T\setminus \{v_0\}$. Нехай $i\in \{0,\dots ,n\}$ — найбільше число таке, що для будь-якого $j\le i$ є дуга з $v_j$ в $v_0$. Тоді

$v_1,\dots ,v_i,v_0,v_{i+1},\dots ,v_n$

— шуканий орієнтований шлях. Це доведення дає також алгоритм пошуку гамільтонового шляху. Відомий ефективніший алгоритм, що вимагає перебору всього $O(n\log n)$ дуг.

Це означає, що строго зв'язний турнір має гамільтонів цикл. Строгіше: будь-який сильно зв'язний турнір є вершинно панциклічним — для будь-якої вершини v і для будь-якого k від трьох до числа вершин у турнірі є цикл довжини k, що містить v. Більш того, якщо турнір 4-зв'язний, будь-яку пару вершин можна з'єднати гамільтоновим шляхом.

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

Транзитивний турнір з 8 вершинами.

Турнір, у якому $((a\to b)$ і $(b\to c))$ $\Rightarrow$ $(a\to c)$, називають транзити́вним. У транзитивному турнірі вершини можна повністю впорядкувати за досяжністю.

Еквівалентні умови

Такі твердження для турніру з n вершинами еквівалентні:

1. T — транзитивний.
2. T — ациклічний.
3. T не містить циклів довжини 3.
4. Послідовність числа виграшів (множина напіввиходів) T є {0,1,2,…,n − 1}.
5. T містить рівно один гамільтонів шлях.

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

Транзитивні турніри відіграють істотну роль у теорії Рамсея, аналогічну ролі, яку відіграють кліки в неорієнтованих графах. Зокрема, будь-який турнір з n вершинами містить транзитивний підтурнір з $1+\lfloor {\log }_{2}n\rfloor$ вершинами. Доведення просте: виберемо будь-яку вершину v як частину цього підтурніру і побудуємо підтурнір рекурсивно на множині або вхідних сусідів вершини v, або на множині вихідних сусідів, залежно від того, яка множина більша. Наприклад, будь-який турнір зі сімома вершинами містить транзитивний турнір із трьома вершинами. Турнір Пелі зі сімома вершинами показує, що це найбільше, що можна гарантувати. Однак Шаблон:Нп і Шаблон:Нп показали, що ця межа не строга для деяких великих значень числа n.

Ердеш і Шаблон:Нп довели, що існують турніри з n вершинами без транзитивних підтурнірів розміру $2+2\lfloor {\log }_{2}n\rfloor$. Їх доведення використовує Шаблон:Не перекладено: число варіантів, у яких транзитивний турнір з k вершинами може міститися в більшому турнірі з n позначеними вершинами, дорівнює

$(\genfrac{}{}{0ex}{}{n}{k})k!2^{(\genfrac{}{}{0ex}{}{n}{2})-(\genfrac{}{}{0ex}{}{k}{2})},$

і при k, що перевищує $2+2\lfloor {\log }_{2}n\rfloor$, це число занадто мале, щоб транзитивний турнір опинився в кожному з $2^{(\genfrac{}{}{0ex}{}{n}{2})}$ різних турнірів однієї й тієї ж множини з n позначених вершин.

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

Гравець, який виграв усі ігри, природно, буде переможцем турніру. Однак, як показує існування нетранзитивних турнірів, такого гравця може не виявитися. Турнір, у якому кожен гравець програє хоча б одну гру називають 1-парадоксальним турніром. Узагальнюючи, турнір T=(V,E) називають k-парадоксальним, якщо для будь-якої k-елементної підмножини S множини V існує вершина v₀ у $V\setminus S$, така що $v_0\to v$ для всіх $v\in S$. За допомогою імовірнісного методу Ердеш показав, що для будь-якого фіксованого k за умови |V| ≥ k²2^kln(2 + o(1)) майже будь-який турнір на V є k-парадоксальним. З іншого боку, простий аргумент показує, що будь-який k-парадоксальний турнір повинен мати щонайменше Шаблон:Nobr гравців, що покращили до Шаблон:Nobr Шаблон:Нп і Дьйордь Секереші (1965). Існує явний метод побудови k- парадоксальних турнірів з Шаблон:Nobr гравцями, розроблений Гремом і Шаблон:Нп, а саме, турнір Пелі.

Конденсація

Шаблон:Не перекладено будь-якого турніру є транзитивним турніром. Таким чином, навіть якщо турнір не є транзитивним, сильно зв'язні компоненти турніру можуть бути повністю упорядкованими.

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

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

Теорема Ландау (1953) — неспадна послідовність цілих чисел $(s_1,s_2,\cdots ,s_n)$ є послідовністю результатів тоді й лише тоді, коли:

1. $0\le s_1\le s_2\le \cdots \le s_n$
2. $s_1+s_2+\cdots +s_i\ge (\genfrac{}{}{0ex}{}{i}{2}),$ задля $i=1,2,\cdots ,n-1$
3. $s_1+s_2+\cdots +s_n=(\genfrac{}{}{0ex}{}{n}{2}).$

Нехай $s(n)$ — число різних послідовностей результатів розміру $n$. Послідовність $s(n)$ починається з:

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, Шаблон:Num, Шаблон:Num, …

(Шаблон:OEIS)

Вінстон і Клейтман довели, що для досить великих n

$s(n)>c_1{4}^n{n}^{-\frac{5}{2}},$

де $c_1=0.049.$ Шаблон:Нп пізніше показав, використовуючи деяке правдоподібне, але недоведене припущення, що

$s(n)<c_2{4}^n{n}^{-\frac{5}{2}},$

де $c_2<4,858.$

Разом це свідчить про те, що

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

Тут $\mathrm{\Theta }$ відбиває асимптотично строгу межу.

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

Див. також

• Орієнтований граф
• Турнір Пелі
• Гіпотеза Самнера
• Універсальний граф