2.2. Метод перебора Робертса и Флореса

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом [30, 31]. Начинают с построения -матрицы где элемент есть вершина (скажем для которой в графе существует дуга Вершины в множестве можно упорядочить произвольно, образовав элементы столбца матрицы Число строк к матрицы будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем, выбирается в качестве отправной и образует первый

элемент множества которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина а) в столбце Затем к множеству добавляется первая возможная вершина (например, вершина в столбце а, потом добавляется к первая возможная вершина (например, вершина с) в столбце Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую Существуют две причины, препятствующие включению некоторой вершины на шаге в множестве Или (1) в столбце нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в имеет длину является гамильтоновой цепью.

В случае (2)

(а) в графе существует дуга и поэтому найден гамильтонов цикл, или

(б) дуга не существует и не может быть получен никакой гамильтонов цикл.

В случаях (1) и (26) следует прибегнуть к возвращению, в то время как в случае (2а) можно прекратить поиск и напечатать результат (если требуется найти только один гамильтонов цикл), или (если нужны все такие циклы) произвести печать и прибегнуть к возвращению. Возвращение состоит в удалении последней включенной вершины из после чего остается множество и добавлении к первой возможной вершины, следующей за в столбце хтматрицы Если не существует никакой возможной вершины, делается следующий шаг возвращения и т. д.

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

2.2.1. Пример.

Рассмотрим граф, изображенный на рис. 10.2. Матрица приводится ниже, вершины в каждом столбце расположены в алфавитном порядке:

Рис. 10.2. Граф из примера 2.2.1.

Поиск всех гамильтоновых циклов производится так (вершина а берется в качестве отправной вершины):

(см. скан)

(см. скан)

2.2.2. Улучшение основного метода.

Допустим, что на некотором этапе поиска построенная цепь задается множеством и что следующей вершиной, которую предполагается добавить к является

Рис. 10.3а. Следующей дугой должна быть

Рис. 10.36. Следующей дугой не должна быть

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

(а) Если существует такая вершина что (см. рис. 10.3а), то, добавляя к любую вершину отличную от мы не сможем в последующем достигнуть вершины х ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае х является единственной вершиной, которую можно добавить к для продолжения цепи.

(б) Если существует такая вершина что и для некоторой другой вершины то х не может быть добавлена к так как тогда в остающемся подграфе не может существовать никакой цепи между Цепь, определяемая множеством не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству следует рассмотреть другую вершину, отличную от х (см. рис. 10.36).

В только что приведенном примере ситуация (а) возникает на шаге 2, когда множество есть Если заметить теперь, что для вершины справедливо соотношение то становится ясным, что следует добавить в качестве очередной вершины к множеству Поэтому в приведенном примере можно опустить шаги 3—8 и сразу от шага 2 перейти, как показано стрелкой, к шагу 9.

Проверка условий (а) и (б) будет, конечно, замедлять итеративную процедуру, и для небольших графов (менее чем с 20 вершинами) не получается никакого улучшения первоначального алгоритма Робертса и Флореса. Но для больших графов эта проверка приводит к заметному сокращению необходимого времени вычислений, уменьшая его обычно в 2 или более раз. Подробные результаты вычислений для различных методов приводятся на рис. 10.7 в разд. 3.