Определение Гамильтонова пути в графе

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

В качестве примера рассмотрим задачу определения очередности решения на ЭВМ вычислительной программы (алгоритма) А,состоящей из п подпрограмм A_i ; i=1,2,…,n , причем на порядок выполнения подпрограмм накладываются ограничения в виде

A_i → A_j (4.1)

(т.е. выполнение подпрограммы A_i предшествует выполнению подпрограммы A_j , i, j = 1,2,…,n) или

A_i A_j (4.2)

(т.е. порядок выполнения программ A_i и A_j безразличен). Эту задачу удобно геометрически отобразить в виде графа, где каждой i вершине соответствует A_i - подпрограмма, а связи между подпрограммами соответствуют дугам или ребрам. Причем дуга соответствует связи A_i → A_j , а ребро - связи A_i A_j .

Если предполагается, что программа A будет выполнена, когда выполнены все подпрограммы A_i , i=1,2,…,n (без повторений), то определение очередности выполнения подпрограмм A_iсводится к определению на графе Гамильтонова пути. Очевидно, что эту задачу можно решить перебором всех возможных вариантов с одновременной проверкой всех условий (4.1), (4.2). При n = 2 возможно всего два варианта, при n = 3 - шесть, при n=10 существует более трех с половиной миллионов возможных вариантов, из которых надо выбрать допустимые, удовлетворяющие условиям (4.1), (4.2).

Решение поставленной задачи может быть облегчено, если мы воспользуемся алгоритмом Фаулкса, позволяющим во многих случаях значительно уменьшить рассматриваемое количество возможных вариантов [4].

Алгоритм Фаулкса. Рассматривается n операций (вершины графа) A_1, A_2,…, A_n , между которыми существуют соотношения:

A_i → A_j , A_i → A_j , (i, j = 1,2,…,n) (4.3)

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

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

Элементы r^N_ij матрицыR^N, определяются как

Вычисления следует прекратить, если R^N = R^N-1 (т.е. все элементы r^N_ij = r^N-1_ij , i, j = 1,…,n).

Так как все вычисления производятся последовательно, и на каждом цикле вычисления возможны некоторые упрощения матрицы R^Nи исходной матрицы R, то в алгоритме вычисления необходимо задать номер цикла вычисления N и условие перехода к новому циклу вычисления в случае, если R^N ¹ R^N-1и номер нового цикла N=N+1.

Порядок решения задачи:

1. Задаем номер цикла вычислений N=0.

2. Используя соотношения (4.3), составляем граф, вершины которого есть операции, а направленные дуги графа определяются заданными соотношениями между операциями.

3. Составляем матрицу смежности R графа, элементы r_ij которой могут принимать значения 0 либо 1. Если r_ij = 1, то это указывает на то, что за операцией (вершиной) A_i должна следовать операция (вершина) A_j .

Полученная таким образом матрица R является булевой матрицей, поскольку каждый элемент может принимать значения 0 или 1. Эта матрица является исходной для всех дальнейших вычислений.

4. Увеличиваем на единицу номер цикла, т.е. N=N+1 (на первом цикле вычислений N=0+1=1 и матрица R^N= R есть исходная матрица смежности R , которая, кроме того, равна R⁰ ).

5. Используя полученную матрицу R^N-1 , длякаждой операции (вершины графа) проверяем принадлежность ее кначальной или конечной вершине Гамильтонова пути.

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

6. Упрощаем матрицу графа R^N-1 , т.е. получаем матрицу (R^N-1)^' , за счет вычеркивания строк и столбцов, которым соответствует либо начало, либо конец Гамильтонова пути.

7. Получаем матрицу R^N , выполнив булевое умножение матрицы (R^N-1)^' на матрицу (R)^' , которая получается из исходной матрицы смежности графа R вычеркиванием строк и столбцов, соответствующих началу и концу Гамильтонова пути во всех циклах вычислений.

8. Проверяем условие выполнения равенства матриц R^Nи (R^N-1)^', то есть равенство каждого элемента r^N_ij = (r^N-1_ij)^' . Если это условие выполняется, то переходим к п. 10, если нет - к п. 9.

9. Проверяем условие равенства всех элементов матрицы R^Nединице.

Если все элементы матрицы r_ij = 1, то нет необходимости в дальнейших вычислениях матрицы R^N+1 , так как очевидно R^N= R^N+1 , т.е. r^N_ij = 1, для " (i, j) = 1, 2,…, n

Если равенство выполняется, переходим к п. 10, если нет - к п. 4.

10. Составляем матрицу R^b , возвращая в матрицу R^N , строки и столбцы, вычеркнутые в п. 6 (во всех циклах вычислений).

11. Составляем матрицу R^c , перегруппировывая строки и столбцы матрицы R^b таким образом, чтобы все нули были расположены под главной диагональю, а единицы - над ней.

Квадратные матрицы, состоящие из единиц, опирающихся на главную диагональ, образуют классы эквивалентности вершин. Если для данного графа мы получилиm классов эквивалентности (m £ n), то есть B₁,…,B_m , и в каждый класс эквивалентности B_d , d = 1,2,…,mвходят S_dвершин графа, то можно сказать, что вершины, входящие в класс эквивалентности B_d, расположенные выше и левее класса эквивалентности B_l в матрице R^cбудут предшествовать в Гамильтоновом пути вершинам из класса эквивалентности B_l .

Нахождение Гамильтоновых путей в этом случае значительно упрощается.

Рассмотрим пример. Считаем, что программа A состоит из 6 операций (подпрограмм) A_1, A_2,…, A₆ , между которыми существуют следующие соотношения:

A₁ → A₂ , A₂ → A₃ , A₃ → A₄ , A₅ → A₄ , A₆ → A₄ ,

A₁ → A₄, A₂ → A₄, A₆ → A₅ ,

A₁ → A₆, A₂ → A₅ ,

A₂ → A₆ . (4.4)

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

Для решения задачи воспользуемся приведенным алгоритмом.

1. Номер цикла N = 0.

2. Составим граф (рис. 4.1), соответствующий соотношениям (4.4).

Рис. 4.1

3. Составим матрицу смежности R графа.

4. N=0+1=1.

5. Рассмотрим матрицу R.

Очевидно, что A₄ есть конечная вершина каждого гамильтонова пути, поскольку никакая дуга не имеет эту вершину своим началом, тогда как дуга, исходящая из любой другой вершины, достигает вершину A_4.

Это свойство выражается наличием единиц во всем столбце A₄ и нулей во всей строке A₄ (за исключением их пересечения).

6. Вычеркиваем столбец и строку A₄. Получаем матрицу R ^' .

7. Произведем умножение матриц R ^' Ä R ^' = R² .

В качестве примера рассмотрим получение элемента r²_1,3 матрицы R² , т.е. элемента, расположенного в первой строчке и в третьем столбце матрицы R² r²_1,3 = 1× 0 Ú 1× 1 Ú 0 × 1 Ú 0 × 0 Ú 1 × 0 = 1 (см. рис. 4.2).

Рис. 4.2

Каждый член этой суммы означает следующее. Пусть мы хотим попасть из A₁ в A₃. Тогда:

1 × 0 = 0 - существует прямой путь из A₁ в A₁, но нет из A₁ в A₃;

1 × 1 = 1 - существуют прямые пути из A₁ в A₂ и из A₂ в A_3; следовательно, имеется путь длины 2 из A₁ в A₃;

0 × 1 = 0 - не существует прямого пути из A₁ в A₃, но есть из A₃ в A₃;

0 × 0 = 0 - нет прямого пути из A₁ в A₅ и из A₅ в A₃;

1 × 0 = 0 - существует прямой путь из A₁ в A₆, но нет из A₆ в A_3.

Таким образом, мы получили все пути из A₁ в A₃ длиной меньшей или равной 2.

Проделав это для всех элементов, мы получим матрицу R² , все единицы которой обозначают существование путей длиной меньшей или равной 2, а 0 - их отсутствие.

8. Проверяем условие равенства R² и R ^' . Так как они не равны, переходим к п. 9.

9. Проверяем условие равенства всех элементов матрицы единицы; так как оно не выполняется, то снова возвращаемся к п.4.

4. N=2.

5. Рассматриваем матрицу R² .

Вершина A₃ , является конечной вершиной гамильтонова пути на данном цикле вычислений.

6. Вычеркиваем столбец и строку A₃. Оставшаяся матрица имеет вид

(R² ) ^' = .

7. Производим умножение (R² )^'Ä R ^' = R³.

R ³ = .

8. R³ ¹ (R² ) ^'

9. Все элементы R³, равны единице. Очевидно, что и R⁴ и R⁵ и т.д. также будут равны, т.е. будут иметь все элементы, равные единице).

Переходим к п.10.

10. Матрицу R ^b получаем возвращением строк и столбцов, вычеркнутых в п. 6.

11. Матрицу R ^c получаем группировкой строк и столбцов матрицы R ^b(п.10), чтобы все нули были расположены под главной диагональю, а единицы - над ней:

Таким образом, мы получили три класса эквивалентности:

- в первый класс входят вершины A₁ A₂ A₅ A₆;

- во второй - вершина A₃;

- в третий - вершина A_4.

Определение гамильтонова пути становится совсем простым делом. С учетом необходимости выполнения условий (4.4) для вершин, входящих в один класс эквивалентности, он может быть таким: A_1,A_6,A_5,A_2,A_3,A_4.

Алгоритм Фаулкса в общем случае не решает однозначно задачу определения Гамильтонова пути, он только частично упорядочивает множество вершин, снижая тем самым размерность решаемой задачи. В данном примере видно, что в Гамильтоновом пути вершина A₃ обязательно должна быть после вершин, входящих в первый класс эквивалентности, а вершина A₄ - после вершин, входящих в первый и второй классы эквивалентности.

В случае, когда в каждый класс эквивалентности входит одна вершина, алгоритм Фаулкса определяет Гамильтонов путь однозначно.