И модифицированная матрица смежности abed.

Матрица Pj почти такая же, как Pg, - только подчеркнутые элементы в Р^ надо заменить нулями. Матрица Рд = В -Pj равна

Гамильтоновы цепи abdce и adcbe, соответствующие элементу (1,4) вышенаписанной матрицы, дают гамильтоновы циклы abdcea и adcbea, если добавить замыкающую дугу (е, а). Все другие гамильтоновы цепи в Р4 приводят к тем же самым двум гамильто-новым циклам, и поэтому в графе G существует только два таких цикла.

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

Рз получается из Р3 после замены подчеркнутых элементов нулями:

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

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

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоре-сом 30, 31]. Начинают с построения {к X ге)-матрицы М = [rriij], где элемент mij есть i-я вершина (скажем Xq), для которой в графе G = (Х, Г) существует дуга (xj, Хд). Вершины Хд в множестве Г (Xj) можно упорядочить произвольно, образовав элементы /-го столбца матрицы М. Число строк к матрицы М будет равно наибольшей полустепени исхода вершины.

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

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

на каждом этапе не обязательно вычислять и хранить всю матрицу Р;, достаточно лишь найти первый столбец из Р;. Эта модификация уменьшает необходимый объем памяти и время вычислений в п раз. Однако даже при использовании этой модификации программа для ЭВМ [14], написанная на языке PL/1, который позволяет построковую обработку литер и переменное распределение памяти, не была способна найти все гамильтоновы циклы в неориентированных графах с более чем примерно 20 вершинами и средним значением степени вершины, большим 4. Использовалась вычислительная машина ИБМ 360/65 с памятью 120 ООО байтов. Более того, даже для графа с вышеуказанными размерами данный метод использовал фактически весь объем памяти и время вычислений равнялось 1,8 минуты. Не такое уж незначительное время для столь небольшого графа.