Турнір — це орієнтований граф, отриманий з неорієнтованого повного графа призначенням напрямку кожному ребру. Таким чином, турнір — це орграф, у якому кожна пара вершин з'єднана однією напрямленою дугою.
Багато важливих властивостей турнірів розглянув Ландау (H. G. Landau), досліджуючи модель домінування курчат у зграї. Нині турніри застосовують для досліджень у галузі голосування і серед інших речей. Ім'я турнір походить від графічної інтерпретації результатів кругового турніру, в якому кожен гравець зустрічається в сутичці з кожним іншим гравцем рівно раз, і в якому не може бути нічиєї. В орграфі турніру вершини відповідають гравцям. Дуга між кожною парою гравців орієнтована від переможця до переможеного. Якщо гравець перемагає гравця , то кажуть, що домінує над .
Шляхи й цикли Будь-який турнір зі скінченним числом вершин містить гамільтонів шлях, тобто орієнтований шлях, що містить усі вершин. Це легко показати за допомогою математичної індукції за : нехай твердження істинне для , і нехай є якийсь турнір з вершиною. Виберемо вершину у і нехай — напрямлений шлях у . Нехай — найбільше число таке, що для будь-якого є дуга з в . Тоді
— шуканий орієнтований шлях. Це доведення дає також алгоритм пошуку гамільтонового шляху. Відомий ефективніший алгоритм, що вимагає перебору всього дуг.
Це означає, що строго зв'язний турнір має гамільтонів цикл. Строгіше: будь-який сильно зв'язний турнір є вершинно панциклічним — для будь-якої вершини v і для будь-якого k від трьох до числа вершин у турнірі є цикл довжини k, що містить v . Більш того, якщо турнір 4-зв'язний, будь-яку пару вершин можна з'єднати гамільтоновим шляхом.
Транзитивність
Турнір, у якому і , називають транзити́вним. У транзитивному турнірі вершини можна повністю впорядкувати за досяжністю.
Еквівалентні умови Такі твердження для турніру з n вершинами еквівалентні:
T — транзитивний. T — ациклічний. T не містить циклів довжини 3. Послідовність числа виграшів (множина напіввиходів) T є {0,1,2,…,n − 1}. T містить рівно один гамільтонів шлях.
Теорія Рамсея Транзитивні турніри відіграють істотну роль у теорії Рамсея, аналогічну ролі, яку відіграють кліки в неорієнтованих графах. Зокрема, будь-який турнір з n вершинами містить транзитивний підтурнір з вершинами. Доведення просте: виберемо будь-яку вершину v як частину цього підтурніру і побудуємо підтурнір рекурсивно на множині або вхідних сусідів вершини v, або на множині вихідних сусідів, залежно від того, яка множина більша. Наприклад, будь-який турнір зі сімома вершинами містить транзитивний турнір із трьома вершинами. Турнір Пелі зі сімома вершинами показує, що це найбільше, що можна гарантувати. Однак і показали, що ця межа не строга для деяких великих значень числа n.
Ердеш і довели, що існують турніри з n вершинами без транзитивних підтурнірів розміру . Їх доведення використовує : число варіантів, у яких транзитивний турнір з k вершинами може міститися в більшому турнірі з n позначеними вершинами, дорівнює
і при k, що перевищує , це число занадто мале, щоб транзитивний турнір опинився в кожному з різних турнірів однієї й тієї ж множини з n позначених вершин.
Парадоксальні турніри Гравець, який виграв усі ігри, природно, буде переможцем турніру. Однак, як показує існування нетранзитивних турнірів, такого гравця може не виявитися. Турнір, у якому кожен гравець програє хоча б одну гру називають 1-парадоксальним турніром. Узагальнюючи, турнір T=(V,E) називають k-парадоксальним, якщо для будь-якої k-елементної підмножини S множини V існує вершина v0 у , така що для всіх . За допомогою імовірнісного методу Ердеш показав, що для будь-якого фіксованого k за умови |V| ≥ k22kln(2 + o(1)) майже будь-який турнір на V є k-парадоксальним. З іншого боку, простий аргумент показує, що будь-який k-парадоксальний турнір повинен мати щонайменше гравців, що покращили до і Дьйордь Секереші (1965). Існує явний метод побудови k- парадоксальних турнірів з гравцями, розроблений Гремом і , а саме, турнір Пелі.
Конденсація будь-якого турніру є транзитивним турніром. Таким чином, навіть якщо турнір не є транзитивним, сильно зв'язні компоненти турніру можуть бути повністю упорядкованими.
Послідовності результатів і множини результатів Послідовність результатів турніру — це послідовність напівстепенів виходу вершин турніру. Множина результатів турніру — це множина цілих чисел, що є напівстепенями виходу вершин турніру.
Теорема Ландау (1953) — неспадна послідовність цілих чисел є послідовністю результатів тоді й лише тоді, коли:
задля
Нехай — число різних послідовностей результатів розміру . Послідовність починається з:
1, 1, 1, 2, 4, 9, 22, 59, 167, 490, 1486, 4639, , , …
()
Вінстон і Клейтман довели, що для досить великих n
де пізніше показав, використовуючи деяке правдоподібне, але недоведене припущення, що
де
Разом це свідчить про те, що
Тут відбиває асимптотично строгу межу.
Яо показав, що будь-яка непорожня множина невід'ємних цілих чисел є множиною результатів для деякого турніру.
Див. також Орієнтований граф Турнір Пелі Гіпотеза Самнера Універсальний граф
Примітки