Нахождение гамильтонова цикла в строго связном турнире

Правка ru5, от dmkz, 2018-08-23 22:20:09

Понимание того, как простым конструктивом построить гамильтонов цикл в строго связном турнире, основываясь на его свойствах, было критично на региональном этапе всероссийской олимпиады школьников по информатике в сезоне 2014/2015 для получения полного балла по задаче Магические порталы.

Здесь небольшой оффтоп

Пусть дан ориентированный граф, в котором между любыми двумя вершинами есть направленная дуга, а также для любой пары вершин u и v можно дойти из u в v по ориентированным дугам, а затем успешно вернуться также по ориентированным дугам обратно ( строго связный турнир ). Пример такого графа:

Турнир

В таком графе есть гамильтонов путь — путь, проходящий по всем вершинам (например: ), и гамильтонов цикл — гамильтонов путь, в котором из конца есть дуга в начало (например: ). Рассмотрим алгоритм нахождения и того, и того за O(n2).

Гамильтонов путь в строго связном турнире

Удобнее всего строить по индукции. Пусть уже есть путь из k вершин. Надо добавить к нему новую вершину uk + 1. Делаем следующее:

  1. Находим максимальный номер i такой, что из любой вершины u1, u2, ..., ui ведет ребро в uk + 1.

  2. Вставляем новую вершину после ui, получая путь:

Здесь активно используется тот факт, что граф у нас — строго связный турнир, а это значит, что если из u в v нет дуги, то точно есть дуга из v в u.

Начиная с пустого пути, добавляем в него все вершины по очереди, каждая операция вставки требует O(n) действий, всего нужно вставить n вершин, следовательно, спустя O(n2) действий получим гамильтонов путь.

Можно сделать это за O(nlog(n)) — подробнее в прикрепленных источниках.

Гамильтонов цикл в строго связном турнире

Стратегия следующая: раз мы уже умеем находить гамильтонов путь, то сперва найдем его за O(n2), а затем уже преобразуем в гамильтонов цикл за O(n2) действий (можно сделать это за O(n) — подробнее в прикрепленных источниках).

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

Пойдем по всем вершинам пути u3, u4, ..., uk до тех пор, пока есть ребро из uk в u1. Если дошли до конца пути, то цикл найден — это весь путь, иначе есть некий цикл и остаток пути . Далее будем по индукции расширять цикл, добавляя вершины из пути. Рассмотрим два случая:

  1. Если в цикле есть вершина, в которую идет ребро из добавляемой вершины uk + 1, то находим первую такую вершину ui. Теперь мы можем составить новый цикл , а путь будет выглядеть как .

  2. Если в цикле не нашлось вершины, в которую бы шло ребро из добавляемой вершины uk + 1, пройдем по остальным вершинам пути, пока не найдем вершину uj, для которой такая вершина ui все же найдется (такая вершина должна быть, иначе этот граф не строго связный турнир, так как мы нашли способ его разбиения на две компоненты строгой связности). Тогда все вершины из начала пути до uj добавляем в цикл, перестраивая его следующим образом: . От пути либо ничего не остается, либо остается .

На каждой итерации мы увеличиваем длину цикла как минимум на 1, выполняя при этом O(n) операций. Итоговая асимптотика алгоритма O(n2).

Что почитать?

В приведенных источниках есть способ нахождения гамильтонова пути и цикла за O(nlog(n)) со структурой данных Semi-Heap, который можно применять на строго связных турнирах, состоящих из порядка 200.000 вершин, а направление ребер в которых определяется некоторой функцией f(u, v) от номеров вершин:

  1. On Finding a Hamiltonian Path in Tournament Using Semi-Heap (Part 1: Sequential Solution) — Jie Wu

  2. A linear-time algorithm for finding Hamiltonian cycles in tournaments — Y.Manoussakis

Теги графы, сильно связный турнир, турнир, гамильтонов путь, гамильтонов цикл

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru9 Русский dmkz 2018-08-24 17:49:15 26
ru8 Русский dmkz 2018-08-23 22:44:18 4 Мелкая правка: 'ightarrow 3 \rightarrow 4 \rightarr' -> 'ightarrow 4 \rightarrow 3 \rightarr'
ru7 Русский dmkz 2018-08-23 22:23:17 26 Мелкая правка: 'сать либо админу admin@ac' -> 'сать либо Беляеву Сергею Николаевичу admin@ac'
ru6 Русский dmkz 2018-08-23 22:21:56 123
ru5 Русский dmkz 2018-08-23 22:20:09 46 Мелкая правка: 'нова цикла).\n\n<spoi' -> 'нова цикла.\n\n<spoi'
ru4 Русский dmkz 2018-08-23 22:18:41 411 Мелкая правка: ' summary="Оффтоп">\nН' -> ' summary="Здесь небольшой оффтоп">\nН'
ru3 Русский dmkz 2018-08-23 22:04:11 308
ru2 Русский dmkz 2018-08-23 21:57:22 2
ru1 Русский dmkz 2018-08-23 21:56:18 5192 Первая редакция (опубликовано)