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

Турнір з 4 вершинами:
вершин ${\displaystyle n}$,
ребер ${\displaystyle {\binom {n}{2}}}$

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

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

Шляхи й цикли

Будь-який турнір зі скінченним числом ${\displaystyle n}$ вершин містить гамільтонів шлях, тобто орієнтований шлях, що містить усі ${\displaystyle n}$ вершин^[2]. Це легко показати за допомогою математичної індукції за ${\displaystyle n}$: нехай твердження істинне для ${\displaystyle n}$, і нехай є якийсь турнір ${\displaystyle T}$ з ${\displaystyle n+1}$ вершиною. Виберемо вершину ${\displaystyle v_{0}}$ у ${\displaystyle T}$ і нехай ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ — напрямлений шлях у ${\displaystyle T\setminus \{v_{0}\}}$. Нехай ${\displaystyle i\in \{0,\ldots ,n\}}$ — найбільше число таке, що для будь-якого ${\displaystyle j\leq i}$ є дуга з ${\displaystyle v_{j}}$ в ${\displaystyle v_{0}}$. Тоді

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},}$

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

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

Гравець, який виграв усі ігри, природно, буде переможцем турніру. Однак, як показує існування нетранзитивних турнірів, такого гравця може не виявитися. Турнір, у якому кожен гравець програє хоча б одну гру називають 1-парадоксальним турніром. Узагальнюючи, турнір T=(V,E) називають k-парадоксальним, якщо для будь-якої k-елементної підмножини S множини V існує вершина v₀ у ${\displaystyle V\setminus S}$, така що ${\displaystyle v_{0}\rightarrow v}$ для всіх ${\displaystyle v\in S}$. За допомогою імовірнісного методу Ердеш показав, що для будь-якого фіксованого k за умови |V| ≥ k²2^kln(2 + o(1)) майже будь-який турнір на V є k-парадоксальним^[9]. З іншого боку, простий аргумент показує, що будь-який k-парадоксальний турнір повинен мати щонайменше 2^k+1 − 1 гравців, що покращили до (k + 2)2^k−1 − 1 Естер^[en] і Дьйордь Секереші (1965)^[10]. Існує явний метод побудови k- парадоксальних турнірів з k²4^k−1(1 + o(1)) гравцями, розроблений Гремом і Спенсером^[en], а саме, турнір Пелі^[11].

Конденсація

Конденсація^[en] будь-якого турніру є транзитивним турніром. Таким чином, навіть якщо турнір не є транзитивним, сильно зв'язні компоненти турніру можуть бути повністю упорядкованими^[12].

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

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

Теорема Ландау (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},}$ задля ${\displaystyle i=1,2,\cdots ,n-1}$
3. ${\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}$

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

1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, 14 805, 48 107, …

(послідовність A000571 з Онлайн енциклопедії послідовностей цілих чисел, OEIS)

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

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

де ${\displaystyle c_{1}=0.049.}$ Такач^[en] пізніше показав^[13], використовуючи деяке правдоподібне, але недоведене припущення, що

${\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 }$ відбиває асимптотично строгу межу.

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

Див. також

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

Примітки

1. H. G. Landau. On dominance relations and the structure of animal societies. III. The condition for a score structure // Bulletin of Mathematical Biophysics. — 1953. — Т. 15, вип. 2 (17 грудня). — С. 143—148. — DOI:10.1007/BF02476378.
2. Lázló Rédei. Ein kombinatorischer Satz // Acta Litteraria Szeged. — 1934. — Т. 7 (17 грудня). — С. 39—43.
3. A. Bar-Noy, J. Naor. Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments // SIAM Journal on Discrete Mathematics. — 1990. — Т. 3, вип. 1 (17 грудня). — С. 7—20. — DOI:10.1137/0403002.
4. Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. — 1959. — Т. 249 (17 грудня). — С. 2151—2152.
5. J. W. Moon. On subtournaments of a tournament // Canadian Mathematical Bulletin. — 1966. — Т. 9, вип. 3 (17 грудня). — С. 297—301. — DOI:10.4153/CMB-1966-038-7. Архівовано з джерела 3 березня 2016. Процитовано 2022-03-09. [Архівовано 2016-03-03 у Wayback Machine.]
6. Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28, вип. 2 (17 грудня). — С. 142—163. — DOI:10.1016/0095-8956(80)90061-1.
7. Paul Erdős, Leo Moser. On the representation of directed graphs as unions of orderings // Magyar Tud. Akad. Mat. Kutató Int. Közl. — 1964. — Т. 9 (17 грудня). — С. 125-132.
8. K. B. Reid, E. T. Parker. Disproof of a conjecture of Erdös and Moser // Journal of Combinatorial Theory. — 1970. — Т. 9, вип. 3 (17 грудня). — С. 225—238. — DOI:10.1016/S0021-9800(70)80061-8.
9. Paul Erdős. On a problem in graph theory // The Mathematical Gazette. — 1963. — Т. 47 (17 грудня). — С. 220—223.
10. Esther Szekeres, George Szekeres. On a problem of Schütte and Erdős // The Mathematical Gazette. — 1965. — Т. 49 (17 грудня). — С. 290—293.
11. Ronald Graham, Joel Spencer. A constructive solution to a tournament problem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathématiques. — 1971. — Т. 14 (17 грудня). — С. 45—48.
12. Frank Harary, Leo Moser. The theory of round robin tournaments // American Mathematical Monthly. — 1966. — Т. 73, вип. 3 (17 грудня). — С. 231—246. — DOI:10.2307/2315334.
13. Lajos Takács. A Bernoulli Excursion and Its Various Applications // Advances in Applied Probability. — 1991. — Т. 23, вип. 3 (17 грудня). — С. 557—585. — DOI:10.2307/1427622.
14. T. X. Yao. On Reid Conjecture Of Score Sets For Tournaments // Chinese Sci. Bull. — 1989. — Т. 34 (17 грудня). — С. 804—808.