Изменения

 Имя турнир исходит Турниром из графической интерпретации исходов кругового турнира, в котором каждый игрок встречается в схватке с каждым другим игроком ровно раз, и в котором не может быть ничьих. В орграфе турнира вершины соответствуют игрокам. Дуга между каждой парой игроков ориентирована от выигравшего к проигравшему. Если игрок <tex>an</tex> побеждает игрока вершин можно изобразить исход игры между <tex>bn</tex>людьми, то говорят, что <tex>a</tex> доминирует над <tex>b</tex>где каждый играет с каждым. Тогда ребро будет ориентировано от выигравшего человека к проигравшему.

==Свойства турниров=====Оценка количества турниров в графе===

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

Турнир, в котором <tex>((a \rightarrow , b)\&land(b \rightarrow , c)) \Rightarrow (a \rightarrow , c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.{{Теорема|id=theorem1|statement=Пусть <tex>T=\langle V, E\rangle</tex> — турнир, <tex>| V| = n</tex>. Тогда следующие утверждения эквивалентны:#<tex>T</tex> транзитивен;#<tex>T</tex> не содержит циклов длины <tex>3</tex>;#<tex>T</tex> ациклический;# множества, составленные из <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> для каждой вершины <tex>T</tex>, есть <tex>\{ 0, 1, 2,..., n - 1\} </tex>;#<tex>T</tex> содержит ровно один гамильтонов путь.|proof= <tex>1 \Rightarrow 2:</tex> Пусть существует цикл длины <tex>3: (u, v), (v, w), (w, u). </tex> Однако по транзитивности должно существовать ребро <tex>(u, w)</tex>, т.е. между <tex>u, w</tex> есть <tex>2</tex> противоположно направленных ребра, что невозможно по определению турнира. <tex>2 \Rightarrow 3:</tex> Пусть в графе содержится цикл длины <tex>k \neq 3</tex>. Это не может быть цикл длины <tex>2</tex> (противоречит определению турнира). Обозначим его вершины в порядке обхода <tex>v_1, v_2, \ldots, v_k, k \geqslant 4</tex>. Заметим, что т.к. нет циклов длины <tex>3</tex>, выполнена транзитивность (в противном случае существовали бы ребра <tex>(u, v), (v, w), (w, u)</tex>). Докажем по индукции, что существует ребро <tex>(v_1, v_{k - 1}).</tex>  '''База индукции''' <tex>k = 3</tex>: <tex>(v_1, v_2) , (v_2, v_3) \in E \Rightarrow (v_1, v_3) \in E </tex> (по транзитивности).  '''Переход индукции''' Пусть доказано для всех <tex>i < k - 1</tex>, что <tex>(v_1, v_i) \in E</tex>, также известно, что <tex>(v_i, v_{i+1}) \in E</tex>, тогда по транзитивности <tex>(v_1, v_{i+1}) \in E</tex>. Таким образом, в транзитивном турнире содержится цикл длины <tex>3</tex> — противоречие (см. предыдущий пункт). <tex>3 \Rightarrow 4: </tex> Обозначим множество значений степеней исхода как <tex>Deg^{+}(T)</tex>. Докажем индукцией по <tex>n</tex>.

Следующие утверждения для турнира с '''База индукции''' <tex>n вершинами эквивалентны= 1</tex>:верно, т.к. есть одна вершина степени <tex>0</tex> *'''Переход индукции''' Пусть доказано для <tex>n - 1</tex>. В ациклическом графе существует сток <tex>t, deg^{+}t = 0</tex>. Рассмотрим граф <tex>T-t</tex> транзитивен. <tex>Deg^{+}(T - t) = \{0, 1, \ldots, n - 2\}</tex> . Т.к. из каждой <tex>v \in V \setminus \{t\}</tex> ведет одно ребро в <tex>t</tex>, <tex> Deg^{+}(T)=\{deg^{+}t\} \cup \{x + 1 \mid x \in Deg^{+}(T -t)\} = \{0, 1, \ldots, n - 1\}</tex>. Для степеней захода можно доказать аналогично, рассмотрев исток вместо стока.*<tex>T4 \Rightarrow 5: </tex> По [[Теорема Редеи-Камиона|теореме Редеи-Камиона]], в любом турнире есть гамильтонов путь, докажем индукцией по <tex>n</tex> ацикличен, что этот путь единственный.*'''База индукции''' <tex>Tn = 1</tex> не содержит циклов длины 3: верно, путь из одной вершины.*Последовательность числа выигрышей '''Переход индукции''' Рассмотрим вершину <tex>s: deg^{-}(s) = 0</tex>. Она будет первой в гамильтоновом пути (множество полуисходовиначе мы в нее не зайдем) . Рассмотрим граф <tex>T- s</tex> есть . Т.к. <tex>s</tex> была соединена со всеми его вершинами, их степени меньше на <tex>1</tex> соответствующих степеней в исходном турнире, значит <tex> Deg^{-}(T-s)=\{0, 1, \ldots, n - 2\}</tex>, следовательно в <tex>T-s</tex> существует единственный гамильтонов путь <tex>v_1, v_2, \ldots v_{n -1}</tex> (по предположению). Пусть существуют <tex>2</tex> гамильтонова пути, начинающиеся на <tex>s</tex>, но тогда существуют 2 пути в <tex>T-s</tex> {{---}} противоречие. <tex>5 \Rightarrow 1: </tex> Пусть <tex>P=v_1, v_2, \ldots, v_n</tex> — единственный гамильтонов путь. Пусть найдется <tex>m</tex> — наименьший индекс такой, что в вершину <tex>v_m</tex> идет ребро из вершины с большим индексом, а <tex>v_k</tex> — вершина с наибольшим индексом,из которой ребро ведет в <tex>v_m</tex>.Возможно несколько случаев:# <tex> m \neq 1, k \neq n: </tex> Из <tex>v_{m -1}</tex> ведет ребро в <tex>v_{m+1}</tex> (по минимальности <tex>m</tex>), а из <tex>v_m</tex> ведет ребро в <tex>v_{k +1}</tex> (по максимальности <tex>k</tex>).Тогда будет существовать еще один гамильтонов путь <tex>P_1 = v_1, \ldots, v_{m-1}, v_{m+1}, \ldots, v_{k}, v_m, v_{k+1}, \ldots, v_n</tex>.# <tex> m \neq 1, k = n : </tex> <tex>P_1 = v_1, \ldots, v_{m- 1 }, v_{m+1}, \ldots, v_{n}, v_m</tex>.# <tex> m = 1, k \neq n:</tex> <tex>P_1 = v_2, \ldots, v_{k}, v_1, v_{k+1}</tex>#<tex> m = 1, k = n:</tex> <tex>P_1 = v_2, \ldots, v_n, v_1</tex>'''Замечание''' Может достигаться равенство <tex>m + 1 = n</tex>, в этом случае нужно исключить из пути <tex>2</tex> последовательных вхождения <tex>v_n</tex>.*Во всех случаях получаем противоречие с единственностью гамильтонова пути, значит не существует такого <tex>Tm</tex>, т.е <tex>(v_i, v_j) \in E \Leftrightarrow i < j</tex>. Значит <tex>\forall i, j, k: 1 \leqslant i, j, k \leqslant n</tex> <tex> (v_i, v_j) \in E \land (v_j, v_k) \in E \Rightarrow i < j \land j < k \Rightarrow (v_i, v_k) \in E </tex>.}} ===Теория Рамсея===Транзитивные турниры играют существенную роль в [[Теория_Рамсея | теории Рамсея]], изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит ровно один гамильтонов путьтранзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.

==Парадоксальные турниры=Конденсация==={{УтверждениеИгрок, выигравший все игры, естественно, будет победителем |statement = Конденсация любого турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным является транзитивным турниром. Обобщая, Турнир |proof = Рассмотрим <tex>T=(V,E)2</tex> называется компоненты сильной связности <tex>kU, V</tex>-парадоксальным, если для любого найдутся <tex>ku \in U, v \in V: (u, v) \in E</tex>-элементного подмножества , либо <tex>S(v, u) \in E </tex> множества , значит в конденсации есть либо ребро <tex>(U,V)</tex> существует вершина <tex>v_0</tex> в , либо <tex>(V\setminus S,U)</tex>. Т.к. мы рассмотрели произвольную пару вершин конденсации турнира, она является турниром. Конденсация любого орграфа ациклична, а по доказанной [[#theorem1|теореме]], это означает, такая что <tex>v_0 \rightarrow v</tex> для всех <tex>v \in S</tex>она транзитивна. }}Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть [[Отношение порядка|вполне упорядочены]]. В самом деле, по [[#theorem1|теореме]], в турнире существует гамильтонов путь, значит вершины могут быть упорядочены по своим позициям в этом пути.

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

Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).

[[Теорема Редеи-Камиона]] устанавливает 2 два следующих факта: