68
правок
Изменения
Нет описания правки
[[Файл:Tournament_transitive.png|300px|thumb|right|Транзитивный турнир с 8 вершинами]]
Турнир, в котором <tex>((a \rightarrow , b)\&land(b \rightarrow , c)) \Rightarrow (a \rightarrow , c)</tex>, где <tex>a \rightarrow b</tex> обозначает ориентированное ребро из <tex>a</tex> в <tex>b</tex>, называется транзитивным. В транзитивном турнире вершины могут быть полностью упорядочены в порядке достижимости.
Следующие утверждения для турнира <tex>T</tex> с <tex>n</tex> вершинами эквивалентны:
*<tex>T</tex> содержит ровно один гамильтонов путь.
===Теория Рамсея===Транзитивные турниры играют существенную роль в [https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%A0%D0%B0%D0%BC%D1%81%D0%B5%D1%8F [Теория_Рамсея | теории Рамсея]], изучающей условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. В частности, любой турнир с <tex>n</tex> вершинами содержит транзитивный подтурнир с <tex>1+\lfloor\log_2 n\rfloor</tex> вершинами. Для его построения выберем любую вершину <tex>v</tex> как часть этого подтурнира и построим подтурнир рекурсивно на множестве либо входящих соседей вершины <tex>v</tex>, либо на множестве исходящих соседей, в зависимости от того, какое множество больше.
<br clear="all">
Не все турниры гамильтоновы. Определение не исключает существование вершины с <tex>\deg^{-}</tex> или <tex>\deg^{+}</tex> равной нулю — в первую нельзя войти, а из второй — выйти. Однако отсутствие таких вершин не означает, что турнир гамильтонов (пример — на рисунке справа).
[[Теорема Редеи-Камиона]] устанавливает 2 два следующих факта:
# Все турниры полугамильтоновы.
# Турнир гамильтонов тогда и только тогда, когда он сильно связен.
* [[Гамильтоновы графы]]
* [[Теорема Редеи-Камиона]]
* [http://epubs.siam.org/doi/abs/10.1137/0403002 Поиск гамильтонова цикла за <tex>O(n\cdot log(n))</tex>]
==Источники информации==
