2.3. Мультицепной метод

После внимательного изучения операций алгоритма перебора Робертса и Флореса становится очевидным, что даже после сделанного улучшения не слишком много внимания уделяется оставшейся части графа, в которой берется последовательность вершин, продолжающих построенную цепь. Обычно построение цепи So в процессе поиска (So рассматривается и как упорядоченное множество вершин, и как обычное множество) подразумевает существование еще каких-то цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее построить гамильтонов цикл, либо указывают на отсутствие такого цикла, содержащего цепь So, что позволяет сразу прибегнуть к возвращению.

Метод, описанный в этом разделе, был предложен первоначально Селби [35] для неориентированных графов; здесь дается его небольшое видоизменение для ориентированных графов. Метод состоит в следующем.

Допустим, что на некотором этапе поиска построена цепь Sg и возможны цепи S-, S2, .... Рассмотрим какую-либо среднюю вершину одной из этих цепей (слово средняя здесь означает любую вершину, отличную от начальной и конечной). Поскольку эта вершина уже включена в цепь с помощью двух дуг, то очевидно, что все другие дуги, входящие или выходящие из такой вершины, могут быть удалены из графа. Для любой начальной вершины вышеуказанных цепей можно удалить все дуги, исходящие из нее (за исключением дуги, включающей эту вершину в цепь), а для любой конечной вершины можно удалить все дуги, оканчивающиеся в ней (опять-таки за исключением дуги, включающей ее в цепь). Кроме того, за исключением слу-

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

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

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

Удаление всех этих дуг даст граф со многими вершинами - всеми средними вершинами цепей.- в котором только одна дуга оканчивается в каждой вершине и только одна дуга исходит из нее. Все эти средние вершины и дуги, инцидентные им, удаляются из G, а вместо них для каждой цепи вводится единственная дуга, идущая от начальной вершины цепи до ее конечной вершины. В результате всего этого получается редуцированный граф Gfe = (Xft, Г^), где к - индекс, показывающий номер шага поиска.

Рассмотрим теперь продолжение цепи Sg (сформированной в результате поиска), осуществляемое путем добавления вершины Xj, которая является возможной в смысле алгоритма Робертса и Флореса, т. е. в G существует дуга, исходящая из конечной вершины цепи Sg - обозначим эту вершину е (So) - и входящая в вершину Xj. Добавление Xj к So осуществляется так:

(1) Сначала удаляются из G все необходимые дуги, т. е.

(а) все дуги, оканчивающиеся в Xj или исходящие из е {So), за исключением дуги (е {So), Xj);

(б) все дуги, выходящие из Xj в начальную вершину пути So,

(в) если окажется, что Xj является начальной вершиной другой цепи Sj, то следует удалить также любую дугу, ведущую из конечной вершины цепи Sj в начальную вершину цепи So.

(2) Обозначим граф, оставшийся после удаления всех дуг, через Gk = {Х^, Т^).

Если существует вершина х в графе Gh, не являющаяся конечной ни для одной из цепей So, S, . . . vl которая после удаления дуг имеет полустепень захода, равную единице, т. е. Г^ (х) \ = = 1, то выкинуть все дуги, исходящие из вершины v = Г^} (х), за исключением дуги {v, х).

Если существует вершина х графа G, не являющаяся начальной ни для какой цепи и которая после удаления дуг имеет полустепень исхода, равную единице, т. е. Ги- {х) = 1, то выкинуть все дуги, исходящие из вершины х, за исключением дуги {X, Т,. {X)).

Перестроить все цепи и удалить дуги, ведущие из конечных в начальные вершины.

Повторять шаг 2 до тех пор, пока можно удалять дуги.

(3) Удалить из оставшегося графа G все вершины, полустепени захода и исхода которых равны единице, т. е. вершины, которые стали теперь средними вершинами цепей. Это удаление производится так, как это было описано выше, в результате чего

) Здесь луга, замыкающая гамильтонову цепь.- Прим. ред.

получается новый редуцированный граф G+i, заменяющий предыдущий граф Gft.

Совершенно очевидно, что если добавление вершины xj к цепи Sg делает полустепень захода или полустепень исхода (или обе) некоторой вершины х в конце шага 2 равной нулю, то не существует никакого гамильтонова цикла. В этом случае вершина xj удаляется из множества Sg и в качестве другой вершины xj, позволяющей продолжить цепь .So, выбирается некоторая другая вершина из множества Г^ [е (Sg)], и так до тех пор, пока не будет исчерпано все множество Г^ [е (Sg)] и придется прибегнуть к возвращению (т. е. е (So) удаляется из So и заменяется другой вершиной и т. д.). Отметим, что операция возвращения предполагает хранение достаточной информации об удаленных дугах в шагах 1 и 2 на каждом этапе к, чтобы можно было по графу Gft+i восстановить граф Gk при любых к, если приходится прибегать к возвращению.

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

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

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

2.3.1. Пример. В настоящем примере будет показано, как итеративный процесс шага 2 приводит ко многим цепям, получающимся из основной цепи So, и как эти цепи могут привести к быстрому окончанию производимого поиска.

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