элемент множества S, которое каждый раз будет хранить уже найденные вершины строяш;ейся цепи. К S добавляется первая вершина (например, вершина а) в столбце Xi. Затем к множеству S добавляется первая возможная вершина (например, вершина Ь) в столбце а, потом добавляется к S первая возможная вершина (например, вершина с) в столбце Ь и т. д. Под возможной вершиной мы понимаем вершину, еш;е не принадлежаш;ую S. Суш;еству-ют две причины, препятствуюш;ие включению некоторой вершины на шаге г в множестве S = {xi, а, Ь, с, . . ., x-i, х^}. Или (1) в столбце Хг нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в S, имеет длину ге -1, т. е. является гамильтоновой цепью. В случае (2)

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

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

В случаях (1) и (26) следует прибегнуть к возвращению, в то время как в случае (2а) можно прекратить поиск и напечатать результат (если требуется найти только один гамильтонов цикл), или (если нужны все такие циклы) произвести печать и прибегнуть к возвращению. Возвращение состоит в удалении последней включенной вершины Хг из S, после чего остается множество S = = {xi,a,b,c, ...,Xr-i}, и добавлении к S первой возможной вершины, следующей за х^, в столбце Xr i матрицы М. Если не существует никакой возможной вершины, делается следующий шаг возвращения и т. д.

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

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

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

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

Множество S Комментарии

1. а Добавляем первую возможную верши

ну в столбце а (т. е. вершину Ь). 2. а, Ъ Добавляем первую возможную верши-

ну в столбце Ъ (т. е. вершину с).

3. а, Ъ, с Первая вершина (а) в столбце с не

является возможной (а 6 5), добавляем следующую вершину в столбце (т. е. вершину d).

4. а, Ъ, с, d Добавляем вершину /.

5. а, Ъ, с, df f В столбце / нет возможной вершины,

возвращение.

6. а. Ъ, с, d В столбце d не существует возможной

вершины, следующей за /. Возвращение.

1. а, Ъ, с Аналогично предыдущему. Возвраще-

8. а, Ъ Добавляем вершину е.

>9. а, Ь, е Добавляем вершину с.

10. а, Ь, е, с

11. а, fe, е, с, d

12. а, fe, е, с, d, f

13. а, fe, е, с, d

14. а, fe, е, с

15. а, fe, е

16. а, fe, е, d

17. а, fe, е, d, f

Добавляем вершину d.

Добавляем вершину /.

Гамильтонова цепь. Дуга (/, а) дает

гамильтонов цикл. Возвращение.

Возвращение,

Возвращение.

Добавляем вершину d.

Добавляем вершину /.

Добав.тяем вершину с.

18. а, Ь, е, d, /, с

19. а, Ь, е, d, f

20. а, b, е, d

21. а, Ъ, е

22. а, Ъ,

23. а

24. 0

Гамильтонова цепь. Цепь замыкается дугой (с, а). Возвращение. Возвращение. Возвращение. Возвращение. Возвращение. Возвращение. Конец поиска.

2.2.2. Улучшение основного метода. Допустим, что на некотором этапе поиска построенная цепь задается множеством S = = {xi, 2, . . ., х^) и что следующей вершиной, которую предполагается добавить к S, является х* S. Рассмотрим теперь две

Рис. 10.3а. (х g Г (х;.) и Г-1 (х)с: с 5.) Следующей дугой должна быть (хг, х).

Рис. 10.36. (х Г-1 (xi) и Г (х)с: с 5 и {х*}.) Следующей дугой не должна быть (х;., х*).

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

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

(б) Если существует такая вершина х X - S, что х $ Г {х- и Г (х) сг 5 О {х*} для некоторой другой вершины х*, то х* не может быть добавлена к S, так как тогда в остающемся подграфе не может существовать никакой цепи между х и х^. Цепь, определяемая множеством S [} {х*}, не может поэтому привести к гамильтонову циклу, а в' качестве кандидата на добавление к множеству S следует рассмотреть другую вершину, отличную от X* (см. рис. 10.36).