Графы-3: эйлеровы и гамильтоновы циклы

Цель

Рассмотреть задачу поиска циклов: один раз проходящих по каждому ребру («эйлеров») и один раз проходящих через каждую вершину («гамильтонов»).

Код

Для удобства будем считать, что часть кода из поста «Графы-2» до комментария

// тесты

выделена в отдельный заголовочный файл «Graph2.h».

1. Функция-шаблон findEulerLoop<AdjVec, OutIt> реализует алгоритм, строящий некоторый эйлеров цикл путём отбрасывания рёбер. Принимаемый граф представлен вектором наборов соседей AdjVec (первый параметр; например, в качестве него подходит объект std::vector<std::set<unsigned>>, тж. см. «Графы-1» ), результат в виде последовательности вершин (отождествляемых с индексами в объекте AdjVec) возвращается через объект итератора вывода OutIt (второй параметр).

Для корректной работы алгоритма требуется, чтобы исходный граф был связным, неориентированным,  с чётными степенями всех вершин. Пример использования этой функции дан в TestCase3::testEulerLoop.

2. Класс-шаблон HamiltonianLoopEnumerator<AdjVec> реализует перебор всех гамильтоновых циклов в связном неориентированном графе, заданном вектором наборов соседей (AdjVec, аналогично функции findEulerLoop). Конструктор осуществляет «привязку» к исходному графу и инициализацию внутренних структур данных.

Функция-член next() находит следующий (или первый, если это первый вызов next() после создания объекта HamiltonianLoopEnumerator<AdjVec>) цикл, если таковой существует (в этом случае возвращает true). Если же искомый цикл не существует, то функция возвращает false. Алгоритм поиска основан на рекурсивном переборе с возвратом, переменная k отражает глубину рекурсии — количество вершин в строимой цепи (ещё не замкнутой в цикл).

В случае успешного вызова next() индексы вершин, составляющих цикл лежат в диапазоне (как видно из кода, это вектор), который можно получить с помощью функций-членов begin() и end(). Таким образом, по индексам вершин, составляющих цикл, можно пройтись как по любому STL контейнеру, предоставляющему begin() и end(). В качестве начальной без ограничения общности фиксируется вершина с индексом 0 (она же присутствует в качестве завершающей в каждом построенном цикле).

Для удобства восприятия часть кода вынесена в закрытые функции rollback() (возврат с уменьшением k) и nextK() (увеличение k с инициализаций соответствующих структур данных).

3. Класс-шаблон MinimalHamiltonianLoop<AdjVec> использует класс HamiltonianLoopEnumerator<AdjVec> для перебора гамильтоновых циклов с выбором среди них цикла минимального веса (задаётся матрицей весов). Для запуска перебора всех циклов предназначена функция-член-шаблон run(const WeightMatrix &W), где W(i, j) задаёт вес ребра (i, j).

Есть также «ограниченный» вариант run(const WeightMatrix &W, std::size_t maxloops), перебирающий не больше, чем maxloops, гамильтоновых циклов. Её можно использовать, чтобы перебирать все циклы «пачками». После каждого вызова ограниченного варианта run, текущий цикл (доступный через диапазон итераторов begin(), end()) будет минимальным среди всех циклов, перебранных после создания объекта MinimalHamiltonianLoop<AdjVec>.

Итак, код целиком: codepad.org, paste.org.

Задания и вопросы

  1. Прочитать и понять приведённый код. Почему последние два цикла, выведенные на экран, совпадают?
  2. Что общего у эйлерова и гамильтонова циклов? Пусть дан граф G = (V, E), построим его рёберный граф Г = (V’, E’), такой, что |E| = |V’|, существует взаимно-однозначное отображение p из V’ в E, и E’ = {(a, b) из V’ x V’ | рёбра pa и pb инцидентны в G}. Написать функцию, строящую рёберный граф заданного графа. Реализуема ли обратная операция?
  3. Какие существуют методы оптимизации поиска гамильтонова цикла минимального веса?
Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: