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

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

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

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

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

Удаление всех этих дуг даст граф со многими вершинами — всеми «средними» вершинами цепей — в котором только одна дуга оканчивается в каждой вершине и только одна дуга исходит из нее. Все эти «средние» вершины и дуги, инцидентные им, удаляются из а вместо них для каждой цепи вводится единственная дуга, идущая от начальной вершины цепи до ее конечной вершины. В результате всего зтого получается редуцированный граф где k — индекс, показывающий номер шага поиска.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.1. Пример.

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

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

Первая итерация. Начнем с вершины 1 как начальной вершины строящейся цепи и попробуем добавить к например, вершину 6, так что цепь будет

Шаг 1 описанного метода удалит тогда из дуги (1,2), (1,3), (1,10), (2,6).

Шаг 2 укажет теперь вершину 10, как имеющую полустепень захода 1 и дающую возможную цепь после чего удаляется дуга (4,2).

Рис. 10.4. Граф из примера разд. 2.3.1.

Второе применение шага 2 дает вершину 2 с полустепенью захода 1 и возможную цепь после чего удаляются дуги (3,12), (3,5) и (3,4). Третье применение шага 2 даст вершину 4 с полустепенью захода 1 и приводит к продолжению цепи после добавления дуги (11,4), так что цепь есть теперь В силу шага 2 дуга (11,9) удаляется, и то же относится к дуге (10,11), замыкающей цепь Четвертое применение шага 2 не приводит к дальнейшим удалениям, и первый редуцированный граф, получающийся в конце шага 3, показан на рис. 10.5 а, где цепи изображены жирными линиями.

Вторая итерация. Так как существует более чем одна цепь и так как полустепени захода и исхода всех вершин ненулевые,

то мы продолжаем расширять цепь дальше. Пусть, например, из множества выбрана вершина 8, так что цепь превратится в цепь Шаг 1 даст теперь вершину 5, обе полустепени которой равны 1, и вершину 1 с полустепенью захода, равной 1.

Рис. 10.5а. Первый редуцированный граф

Взяв сначала вершину 5 и сделав два раза шаг 2, придем к добавлению дуг (2,5) и (5,13) для расширения цепи которая превращается теперь в Дуги (2, 13), (12,13) и дуга возврата (13, 3) удаляютсяг). Второе применение шага 2 дает вершину 3 с полустепенью захода 1, а также вершину 1 (с полустепенью захода 1), полученную на предыдущем этапе. Взяв вершину 3, добавим к дугу (12, 3), после чего получим цепь и удалим дугу (12, 11). Третье применение шага 2 все еще дает вершину 1 с полустепенью захода 1 и больше не дает никаких вершин. К цепи добавляется дуга (9,1), цепь превращается в а дуги (9,14) и дуга

возврата (8,9) удаляются. Четвертое применение шага 2 укажет две вершины 9 и 7 с полустепенями захода 1. Взяв сначала вершину 9, добавим дугу (10,9), соединяющую цепи и дающую новую цепь Дуга (10, 7) удаляется.

Рис. 10.56. Граф после четвертого применения шага 2 на второй итерации.

Пятое применение шага 2 дает вершину 7 с полустепенью захода 0. Это говорит о том, что описанный поиск не может привести ни к какому гамильтонову циклу.

Граф получающийся в конце четвертого применения шага 2, показан на рис. 10.56. Теперь следует восстановить все удаленные во время второй итерации дуги, чтобы вернуться к графу из рис. 10.5а, и произвести операцию возвращения, т. е. удалить из вершину 8, заменить ее другой возможной вершиной (5 или 7) и продолжать применять шаги 1, 2, 3 и т. д.

Из приведенного примера видно, что это очень сильный метод поиска. После двух итераций он позволяет сделать вывод, что никакой гамильтонов цикл не может содержать в качестве своей части цепь Это 1/12 всех попыток поиска, поскольку полустепень исхода вершины 1 равна 4, а вершины Конечно, указанный вывод относится только к части графа, изображенной на рис. 10.4, которая сама может принадлежать к намного большему графу. Можно поэтому ожидать, что при заданном

среднем значении степеней вершин поиск лишь слабо зависит от размера (числа вершин) графа. Этот факт будет продемонстрирован на экспериментальных данных в следующем разделе.

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