Простой путь, Гамильтонов путь, Гамильтонов цикл

Лемма. В сильно связном турнире существует гамильтонов цикл.

Доказательство. В сильно связном турнире есть циклы. Рассмотрим в нашем турнире максимальный простой цикл Предположим, что в него вошли не все вершины графа, пусть вершина не вошла в этот цикл. Пусть не все стрелки между и циклом ориентированы одинаково. Тогда существуют последовательные вершины цикла и такие, что В этом случае несложно удлинить максимальный цикл вставив вершину между и противоречие.

Пусть из всех вершин цикла стрелки входят в Ввиду сильной связности турнира существует путь от до цикла Пусть впервые пересекает цикл в вершине Тогда, опять же, несложно удлинить наш максимальный цикл, заменив стрелку на путь Противоречие. Случай, когда из выходят ребра ко всем вершинам цикла аналогичен. _________________________________________________________________________________________

Вернемся к доказательству основной задачи. По лемме в есть гамильтонов цикл . Нумерация вершин — циклическая, то есть Пусть длина диагонали цикла — это остаток от деления на числа

Если количество вершин в равно или то почти транзитивен.

Далее Рассмотрим два случая. Будем говорить, что если в ребро между и направлено к

1. Для каждого выполняется

Тогда пусть состоит из всех вершин с нечётными номерами, — из и всех вершин с чётными номерами. Нетрудно видеть, что а индуцированные турниры и — сильно связные.

2. Существует диагональ

Не умаляя общности будем считать, что Докажем, что при диагональ Пусть это не так, тогда выберем диагональ где и — максимально. Понятно, что выполняется хотя бы одно из условий и Пусть (второй случай аналогичен). Тогда следовательно, для множеств и индуцированные турниры и сильно связны, В этом случае утверждение доказано.

Итак, при и мы имеем Осталось разобраться, как направлены стрелки, инцидентные Если существует такое что то множества

таковы, что турниры и сильно связны и В этом случае утверждение доказано.

Остаётся случай, когда для некоторого в нашем графе стрелки ориентированы таким образом:

При турнир почти транзитивен (с порядком ). При турнир почти транзитивен (с порядком ). Если же то Следовательно, множества и таковы, что и сильно связны и