68
правок
Изменения
Нет описания правки
}}
[[Файл:Tournament_1_3.png|415px|thumb|left|Турниры из трех вершин]]
==Оценка количества турниров в графе==
Если в турнире опустить ориентацию ребер, то мы получим полный граф. А так как существует два варианта ориентации каждого ребра, то количество турниров в графе из <tex>n</tex> вершин равно <tex dpi=150>2^{\frac{n\cdot(n-1)}{2}}</tex>.
==Транзитивность==
[[Файл:Tournament_transitive.png|300px|thumb|right|Транзитивный турнир с 8 вершинами]]
Турнир, в котором <tex>((a \rightarrow b)\&(b \rightarrow c)) \Rightarrow (a \rightarrow c)</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
Следующие утверждения для турнира с n вершинами эквивалентны:
*<tex>T</tex> транзитивен.
*<tex>T</tex> ацикличен.
*<tex>T</tex> не содержит циклов длины 3.
*Последовательность числа выигрышей (множество полуисходов) <tex>T</tex> есть <tex> 0, 1, 2,..., n - 1 </tex>.
*<tex>T</tex> содержит ровно один гамильтонов путь.
<br clear="all">
==Парадоксальные турниры==
Игрок, выигравший все игры, естественно, будет победителем турнира. Однако, как показывает существование нетранзитивных турниров, такого игрока может не оказаться. Турнир, в котором каждый игрок проигрывает хотя бы одну игру называется 1-парадоксальным турниром. Обобщая, Турнир <tex>T=(V,E)</tex> называется <tex>k</tex>-парадоксальным, если для любого <tex>k</tex>-элементного подмножества <tex>S</tex> множества <tex>V</tex> существует вершина <tex>v_0</tex> в <tex>V\setminus S</tex>, такая что <tex>v_0 \rightarrow v</tex> для всех <tex>v \in S</tex>.
==Конденсация==
Конденсация любого турнира является транзитивным турниром. Таким образом, даже если турнир не является транзитивным, сильно связанные компоненты турнира могут быть полностью упорядочены.
==Сильно связные турниры==
{{Определение|definition = Турнир называется [[Отношение связности, компоненты связности#sc_def |сильно связным]], если из любой вершины существуют пути до всех других.}}
Не все турниры гамильтоновы. Определение не исключает существование вершины с полустепенью исхода <tex>deg^{-}</tex> или захода <tex>deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
[[Теорема Редеи-Камиона]] устанавливает 2 следующих факта:
