Эйлеровы и гамильтоновы графы (стр. 5 из 11)

1. В столбце x_r нет возможной вершины.

2. Цепь, определяемая последовательностью вершин в S, имеет длину n-1, т.е. является гамильтоновой цепью.

В случае 2) возможны следующие случаи:

1. В графе G существует дуга (x_r,x₁), и поэтому найден гамильтонов цикл.

2. Дуга (x_r,x₁) не существует и не может быть получен никакой гамильтонов цикл.

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

Возвращение состоит в удалении последней включенной вершины x_r из S, после чего остается множество S = {x₁,a,b,c, … ,x_r-1}, и добавлении к S первой возможной вершины, следующей за x_r, в столбце x_r-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т.д.

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

Рассмотрим пример поиска гамильтонова цикла в графе переборным методом Робертса и Флореса.

Пример:

"2"
1) S = {1}
2) S = {1, 2}
3) S = {1, 2, 3}
4) S = {1, 2, 3, 4}
5) S = {1, 2, 3, 4, 5} - Г 4→3 4→5
6) S = {1, 2, 3, 4}
7) S = {1, 2, 3} 3→1 3→2 3→4
8) S = {1, 2}

9) S = {1}
"3"
10) S = {1, 3} 3→2
11) S = {1, 3, 2} 2→1
12) S = {1, 3} 2→3
13) S = {1, 3, 4} 3→4 4→5
14) S = {1, 3, 4, 5, 4} 5→нет
15) S = {1, 3, 4}
16) S = {1, 3}
17) S = {1}
"5"
18) S = {1, 5}
19) S = {1, 5, 4}
20) S = {1, 5, 4, 3}
21) S = {1, 5, 4, 3, 2} - Г
22) S = {1, 5, 4, 3}
23) S = {1, 5, 4}
24) S = {1, 5}
25) S = {1}
26) S = Ш

§8. Улучшение метода Робертса и Флореса

Рассмотрим улучшение основного переборного метода Робертса и Флореса. Допустим, что на некотором этапе поиска построенная цепь задается множеством S = {x₁,x₂, … ,x_r} и что следующей вершиной, которую предполагается добавить к S, является x^*

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

1. Если существует такая вершина x

X\S, что x Г(x_r) и Г^-1(x) S, то, добавляя к S любую вершину x^*, отличную от x, мы не сможем в последующем достигнуть вершины x ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае x является единственной вершиной, которую можно добавить к S для продолжения цепи.

2. Если существует такая вершина x

X\S, что x Г^-1(x₁) и Г(x) S {x^*} для некоторой другой вершины x^*, то x^* не может быть добавлена к S, так как тогда в остающемся подграфе не может существовать никакой цепи между x и x₁. Цепь, определяемая множеством S {x^*}, не может поэтому привести к гамильтонову циклу, а в качестве кандидата на добавление к множеству S следует рассмотреть другую вершину, отличную от x^*.

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

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

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

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

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

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

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

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

1. все дуги, оканчивающиеся в x_j или исходящие из e(S₀), за исключением дуги (e(S₀), x_j);

2. все дуги, выходящие из x_j в начальную вершину пути S₀;

3. если окажется, что x_j является начальной вершиной другой цепи S_j, то следует удалить также любую дугу, идущую из конечной вершины цепи S_j в начальную вершину цепи S₀.

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

Если существует вершина x в графе G’_k, не являющаяся конечной ни для одной из цепей S₀, S₁, … и которая после удаления дуг имеет полустепень захода, равную единице, т.е. |Г^-1_k’(x)|=1, то выкинуть все дуги, исходящие из вершины v= Г^-1_k’(x), за исключением дуги (v, x).

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

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

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

3. Удалить из оставшегося графа G’_k все вершины, полустепени захода и исхода которых равны единице, т.е. вершины, которые стали теперь «средними» вершинами цепей. Это удаление производится так, как это было описано выше, в результате чего получается новый редуцированный граф G_k+1, заменяющий предыдущий граф G_k.

Совершенно очевидно, что если добавление вершины x_j к цепи S₀ делает полустепень захода или полустепень исхода (или обе) некоторой вершины x в конце шага 2 равной нулю, то не существует никакого гамильтонова цикла. В этом случае вершина x_j удаляется из множества S₀ и в качестве другой вершины x_j, позволяющей продолжить цепь S₀, выбирается некоторая другая вершина из множества Г_k’[e(S₀)]. И так до тех пор, пока не будет исчерпано все множество Г_k’[e(S₀)] и придется прибегнуть к возвращению (т.е. e(S₀) удаляется из S₀ и заменяется другой вершиной и т.д.). Отметим, что операция возвращения предполагает хранение достаточной информации об удаленных дугах в шагах 1 и 2 на каждом этапе k, чтобы можно было по графу G_k+1 восстановить граф G_k при любых k, если приходится прибегать к возвращению.