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

Теорема Оре: Если в графе с вершинами для любых двух несмежных вершин и выполняется условие

то содержит гамильтонов цикл(проходящий по всем вершинам по разу).

Доказательство. Предположим противное: пусть граф удовлетворяет условию теоремы, но не является гамильтоновым.

Рассмотрим максимальный по длине путь в Все соседи и лежат на так как иначе путь можно было бы продлить. Докажем, что его можно замкнуть в цикл.

Пусть вершины и не смежны, иначе мы бы замкнули путь в цикл. Обозначим:

Заметим, что и

Из условия теоремы:

По принципу Дирихле множества и пересекаются: существует Тогда в графе существует цикл:

Этот цикл содержит все вершины пути Если то – гамильтонов цикл, что противоречит предположению.

Пусть из условия на степень, окрестности любых двух несмежных вершин пересекаются, поэтому граф связен. Рассмотрим вершину от нее есть путь до что позволяет построить путь длины хотя бы получаем противоречие с максимальностью пути что доказывает теорему.

_________________________________________________________________________________________________________________________________________________________________________________

Вернемся к решению задачи, в построенном графе выполняются условия теоремы Оре, поэтому в нём есть гамильтонов цикл. Гамильтонов цикл длины можно разбить на два совершенных паросочетания:

• Первый тур: рёбра с чётными номерами в цикле,
• Второй тур: рёбра с нечётными номерами в цикле.

Эти паросочетания не пересекаются и покрывают все команды, что доказывает возможность составления расписания ещё двух туров.