Очевидно, что в качестве начального значения матрицы P (т.е. P1) следует взять матрицу смежности A графа, положив все ее диагональные элементы равными нулю.

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

Небольшая модификация вышеприведенного метода позволяет во много раз уменьшить необходимый объем памяти и время вычислений. Так как нас интересуют только гамильтоновы циклы и, как было отмечено выше, они могут быть получены из членов внутреннего произведения любой диагональной ячейки матрицы B*Pn-1, то необходимо знать только элемент pn-1(1,1). При этом на каждом этапе не обязательно вычислять и хранить всю матрицу PL, достаточно лишь найти первый столбец PL. Эта модификация уменьшает необходимый объем памяти и время вычислений в n раз. Однако даже при использовании этой модификации программа для ЭВМ, написанная на языке PL/1, который позволяет построчную обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4. Использовался компьютер IBM 360/65 с памятью 120 000 байтов. Более того, даже для графа с вышеуказанными «размерами» данный метод использовал фактически весь объем памяти и время вычислений равнялось 1.8 минуты. Не такое уж незначительное время для столь небольшого графа.

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

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом. Начинают с построения (k×n)-матрицы M=[mij], где элемент mij есть i-я вершина (скажем xq), для которой в графе G(X,Г) существует дуга (xj,xq). Вершины xq во множестве Г(xj) можно упорядочить произвольно, образовав элементы j-го столбца матрицы M. Число строк k матрицы M будет равно наибольшей полустепени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем, x1) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например, вершина a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину, еще не принадлежащую S. Существуют две причины, препятствующие включению некоторой вершины на шаге r во множество S = {x1,a,b,c, … ,xr-1,xr}:

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

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

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

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

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

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

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

Поиск заканчивается в том случае, когда множество S состоит только из вершины x1 и не существует никакой возможной вершины, которую можно добавить к 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 = {x1,x2, … ,xr} и что следующей вершиной, которую предполагается добавить к S, является x*S. Рассмотрим теперь две следующие ситуации, в которых вершина является изолированной в подграфе, остающемся после удаления из G(X,Г) всех вершин, образующих построенную до этого цепь.

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