Гамильтоновы цепи и циклы

Пусть G – псевдограф. Цепь (цикл) в G называется гамильтоновой (гамильтоновым), если она (он) проходит через каждую вершину псевдографа G ровно один раз. Простейшим достаточным условием существования гамильтоновых цепей и циклов в графе является его полнота. Граф G называется полным, если каждая его вершина смежна со всеми остальными вершинами. Необходимым условием существования гамильтоновых цепей и циклов в графе G является связность данного графа.

Приведем некоторые наиболее простые методы выделения гамильтоновых цепей и циклов в графе G =(V,X), где V = { v₁,v₂,…,v_n }. Самым простым является метод перебора всевозможных перестановок v_i₁,v_i₂,…,v_in множества V. Для каждой из них проверяем, является ли v_i₁v_i₂…v_in маршрутом в G. Если является, то v_i₁v_i₂ …v_in - гамильтонова цепь в G, в противном случае переходим к другой перестановке. Тогда по окончании перебора будут выделены все гамильтоновы цепи в графе G. Аналогично для выделения гамильтоновых циклов перебираем всевозможные перестановки v₁v_i₁v_i₂ …v_in_-1 множества V, для каждой из которых проверяем, является ли v₁v_i₁v_i₂…v_in_-1v₁ маршрутом в G. Если является, то v₁v_i₁v_i₂…v_in_-1v₁ – гамильтонов цикл в G, в противном случае переходим к следующей перестановке. Тогда по окончании перебора будут выделены все гамильтоновы циклы в графе G. Очевидно, что при выделении гамильтоновых цепей придется перебрать n! перестановок, а при выделении всех гамильтоновых циклов - (n -1)! перестановок. При этом в случае полного графа ни одна из перестановок не окажется отброшенной, т.е. данный метод является эффективным для графов, близких к полным.

Отметим, что описанный метод не учитывает информации об исследуемом графе G и является как бы ориентированным на самый “худший” случай, когда G – полный граф.

Для того, чтобы сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности < v ₁ ,... v _n>. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение < v₁, ... v _i>, ищем такое допустимое значение v _i+1, которое еще не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения < v ₁ ,... v _i+1>. В противном случае, если такого значения v _i+1 не существует, возвращаемся к предыдущему частичному решению < v ₁,... v _i-1> и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение v _k. Такие алгоритмы носят название “алгоритмы с возвратом” (англ.: backtracking).

2 1

1 5 3 12 14

123 125 143 145

1234 1235 1253 1254 1432 1435 1452 1453

14321 14352

12341 12354 12534

14325 14521 14532

12345 12541 12543 14523

123541 125341 143521 145321

Рис. 2

Процесс поиска с возвращением удобно проиллюстрировать в терминах обхода в глубину в некотором дереве поиска, которое строится следующим образом. Каждая вершина дерева соответствует некоторому частичному решению < v ₁, ...v _i>, причем вершины, соответствующие последовательностям вида < v ₁, .. v _i, y >, и являются преемниками вершины < v ₁,... v _i>. Корнем данного дерева является пустая последовательность. В случае построения гамильтонова цикла в качестве корня может выступать любая вершина.

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