В отличие от эйлерова цикла, проходящего в точности один раз через каждое ребро, гамильтонов цикл проходит в точности один раз через каждую вершину данного графа. При этом, не известно ни одного простого необходимого и достаточного условия для существования гамильтоновых путей и это несмотря на то, что эта задача - одна из центральных в теории графов. Не известен также алгоритм, который проверял бы существование гамильтонова пути в произвольном графе, используя число шагов, ограниченное многочленом от переменной n (числа вершин в графе). Проблема существования гамильтонова пути принадлежит к классу так называемых NP -полных задач.
Очевидный алгоритм, который мы можем применить, это “полный перебор всех возможностей”: генерируем все n! различных последовательностей вершин и для каждой из них проверяем, определяет ли она гамильтонов путь. Применим теперь алгоритм с возвратом (см. разд. 3.4) для нахождения гамильтонова цикла в графе G = á V, Е ñ. Каждый такой цикл можно представить последовательностью á v1, v2,..., vn+1 ñ, причем v1 = vn+1 = v0, где v0 - некоторая фиксированная вершина графа, а соседние вершины смежны.
Алгоритм 5.3. Нахождение всех гамильтоновых циклов в графе.
Исходные данные: Граф G = á V, Е ñ, представленный соответствиями G [ v ], v Î V.
Результаты: Список всех гамильтоновых циклов графа G.
procedure ГАМИЛЬТ (k);
(*генерирование всех гамильтоновых циклов, являющихся расширением последовательности (v [1],..., v [ k - 1]); массив dop - глобальный *)
Begin
for у Î G [ v [ k -1] ] do begin
if (k = n + 1) and (у = v 0) then напечатать (v [1],..., v [ n ], v 0)
Else
if dop [ у ] then begin
v [ k ]:= у; dop [ у ]:= ложь;
ГАМИЛЬТ (k + 1);
End
dop [ у ]:= истина
End
end; (* ГАМИЛЬТ *)
begin (* главная программа *)
for v Î V do dop [ v ]:= истина; (* инициализация*)
v [1]:= v 0; (v 0 = произвольная фиксированная вершина графа *)
dop [ v 0]:= ложь;
ГАМИЛЬТ (2)
end.
Работу этого алгоритма, так же как и произвольного алгоритма с возвратом, можно проиллюстрировать процессом поиска в некотором дереве перебора. Каждая вершина дерева естественным образом соответствует некоторой последовательности á v1,..., vk ñ. Это дерево отображает перебор всех возможностей. Для алгоритма 5.3 это иллюстрируется рис. 5.2.
Рис. 5.2. Граф и дерево, иллюстрирующие алгоритм с возвратом нахождения всех гамильтоновых циклов в этом графе.
Приведенное на этом рисунке дерево перебора иллюстрирует эффективность алгоритма с возвратом в отношении полного перебора всех возможностей. Следует отметить, что для большинства приложений число шагов алгоритма с возвратом хотя и будет меньше, чем в случае полного перебора, однако же, в наихудшем случае растет по экспоненте с возрастанием размерности задачи. Это справедливо и для случая, когда мы ищем только одно, а не все решения (тогда мы просто прерываем выполнение алгоритма после получения первого решения).
5.5. Лабораторная работа №5.1: “Поиск фундаментальных циклов”
Цель работы:
Исследование и поиск фундаментальных циклов в графе.
Задание:
Используя методические указания раздела 5.1 разработать программу поиска всех фундаментальных циклов в графе от заданной вершины, используя один из алгоритмов поиска по выбранному варианту.
Порядок выполнения работы
Работа рассчитана на 2 часа и должна определять в заданном неориентированном графе следующие элементы:
· цикломатическое число;
· список вершин каждого фундаментального цикла перечислением его вершин;
· список фундаментальных циклов.
Варианты выполнения работы:
1) Использовать рекурсивный алгоритм поиска в графе в глубину.
2) Использовать нерекурсивный алгоритм поиска в графе в глубину.
3) Использовать алгоритм поиска в графе в ширину.
В качестве теста для отладки и исследования использовать связный неориентированный граф из 9 вершин, представленный на рис. 4.1.
Методические указания
Для удобства последующего использования найденных фундаментальных циклов рекомендуем их систематизировать в специальной матрице. Матрица фундаментальных циклов может быть построена по столбцам (или аналогично - по строкам), где строкам соответствуют ребра, а столбцам - циклы. Единичный элемент указывает на наличие данного ребра в данном цикле. Ребра можно задавать в виде пар вершин и представлять их в отдельном массиве.
5.6. Лабораторная работа №5.2: “Поиск всех циклов”
Цель работы:
Исследование и поиск циклов в графе, используя фундаментальные циклы в графе.
Задание:
Используя методические указания раздела 5.2 разработать программу генерирования всех циклов в графе, применяя операцию симметрической разности к ранее найденным фундаментальным циклам.