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

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

В качестве примера рассмотрим задачу определения очередности решения на ЭВМ вычислительной программы (алгоритма) А,состоящей из п подпрограмм 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сводится к определению на графе гамильтонова пути. Очевидно, что эту задачу можно решить перебором всех возможных вариантов (n! в насыщенном графе) с одновременной проверкой выполнения всех условий (4.1), (4.2). При n = 2 максимально возможно всего два варианта, при n = 3 - шесть, при n=10 существует более трех с половиной миллионов возможных вариантов, из которых надо выбрать допустимые, удовлетворяющие условиям (4.1), (4.2).

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

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

A_i → A_j , A_i → A_j , i, j Î {1,2,…,n} (4.3)

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

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

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

Вычисления следует прекратить, если R^N = R^N-1 .

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

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

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

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

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

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

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

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

6. Увеличиваем на единицу номер цикла, т.е. N=N+1.

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

8. Проверяем условие выполнения равенства матриц (R^N)^' и (R^N-1)^'.

Если это условие выполняется, то переходим к п. 10, Иначе - к п. 9.

9. Проверяем условие равенства всех элементов матрицы R^N единице. Если это условие выполняется, то нет необходимости в дальнейших вычислениях матрицы (R^N)^', так как очевидно, что (R^N+1)^'=(R^N)^', переходим к п. 10. Если нет - к п. 4.

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

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 .

Нахождение Гамильтоновых путей в этом случае значительно упрощается. В соответствии с классами эквивалентности мы получили упорядоченные группы вершин. В качестве начальной выбирается вершина из первого класса эквивалентности. Если их в нем несколько, то следующая выбирается из этого же класса и так до тех пор, пока не будут исчерпаны все вершины этого класса. Затем переходим к вершинам следующего класса и т.д. пока не будут использованы все вершины графа и построен ГП. Следует заметить, что при выборе очередной вершины необходимо обязательно проверять выполнение условий (4.3). Если условия не выполняются, очередность следования вершин из одного класса эквивалентности меняется. Максимальное число возможных вариантов сокращается до произведения B₁ ! ∙ B₂ ! ∙ ,…, ∙ B_m !

Пример. Пусть программа 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₅ , A₆ → A₅

A₂ → A₆ . (4.4)

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

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

1. Зададим номер цикла N = 1.

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

Рис. 4.1

3. Составим матрицу R¹ достижимости не более чем за один шаг.

4. Проверим матрицу R¹ на наличие начальной или конечной вершин в графе.

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

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

6. N=1+1=2.

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

Наличие 1 в матрице означает существование между соответствующими вершинами путей длиной меньшей или равной двум, а 0 - их отсутствие.

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

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

4. Рассмотрим матрицу (R²) ^' .

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

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

(R²) ^' = .

6. N=2+1=3.

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

(R ³) ^' = .

8. (R³) ^' ¹ (R² ) ^'

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

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

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

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

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

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

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

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

Т.е. в гамильтоновом пути вершины A₁, A₂, A₅, A₆ предшествуют вершине A₃ , которая, в свою очередь, предшествует вершине A₄ . Всего возможно 4! ∙ 1! ∙ 1! = 24 вариантов следования вершин.

С учетом необходимости выполнения условий (4.4) определение гамильтонова пути становится достаточно простым делом. В данном примере получим единственный ГП: A₁,A₆,A₅,A₂,A₃,A₄ .

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

Определение связности графа

Неориентированный граф называется связным, если для любой пары вершин х_i,х_jÎX существует хотя бы один маршрут, их соединяющий. В противном случае граф несвязан. Несвязный граф может быть единственным образом разбит на группы взаимосвязанных вершин (на связные компоненты) таким образом, что не существует маршрута, соединяющей какие-либо из вершин различных компонент.

Решим задачу определения связности графа с помощью элементов алгоритма Фаулкса.

Пусть дана матрица смежности R неориентированного графа G (матрица R симметрична относительно главной диагонали), имеющего n вершин. Необходимо определить, является ли этот граф связным. В случае, если граф несвязный, то требуется выделить из него все т связных подграфов G_1, G_2,…, G_m таких, что, например, из любой вершины подграфа G₁ можно найти путь или маршрут, ведущий к любой другой вершине этого же подграфа, но нельзя найти путь или маршрут ни к одной вершине, не принадлежащей данному подграфу G₁. Требуется определить, какие вершины входят в каждый из подграфов.

На основании матрицы смежности R получим матрицу достижимости не более чем за один шаг R¹.

Затем, в соответствии с алгоритмом Фаулкса, найдем матрицу R^N путем булевского перемножения матриц (R^N = R^N-1 Ä R¹ ) до тех пор, пока не достигнем R^N = R^N-1. Полученная матрица R^N является матрицей достижимости графа G. Она позволяет выявить связные подграфы и номера вершин, входящих в связные подграфы. Для этого необходимо в некоторой i - строке матрицы R^N найти элементы r^N_ij = 1, i, j = 1,…,n. Номера столбцов j, где r_ij = 1, и будут номерами вершин, входящих в связный подграф, включающий в себя i-ю вершину. Рассматривая последовательно все несовпадающие строки матрицы можно выявить все т связных подграфов исходного графа G.

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

Пример.

Пусть задана матрица R¹ достижимости не более чем за один шаг неориентированного графа G , имеющего n = 8 вершин.

Необходимо проверить граф на связность и выявить все связные подграфы.

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

2. N= N +1 =2.

3. Производим умножение R¹ Ä R¹ = R²

.

4. Проверяем условие равенства R² и R¹. Они не равны. Переходим к п. 2.

2) N = 2 + 1 = 3.

3) Умножение R² Ä R¹= R³.

.

4) Проверяем условие равенства матриц R² и R³. Так как они равны, то это означает, что путь длиной 2 - максимальный в данной графе, и дальнейшее перемножение матрицы не имеет смысла, так как мы будем получать одну и ту же матрицу. Найденная матрица R³ есть матрица достижимости исходного графа. Наличие нулей в полученной матрице показывает, что между соответствующими элементами отсутствует путь любойдлины и,следовательно, данный граф — несвязный.

5. Выбираем начальную вершину для выявления связных подграфов: i =1.

6. В строке i =1 выбираем все элементы r³_1j , равные единице (j=1,…,n). r³₁₁ = r³₁₂ = r³₁₇ = r³₁₈ = 1. Номера столбцов, в которых r³_ij = 1 - это номера вершин первого связного подграфа, входящего в данный граф. То есть вершины 1, 2, 7, 8 образуют связный подграф G₁ .

7. Определяем номер очередной вершины i = 1 + 1 = 2. Так как 2 ≤ 8, то на 8 (иначе на 9).

8. Проверим – входит ли данная вершина в найденные связные подграфы. Если среди вершин найденных связных подграфов есть данная вершина, то на 7, иначе на 6.

Так как среди вершин связного подграфа G₁ есть вершина j=2, то возвращаемся к п.7.

7) i = 2 + 1 = 3. Так как 3 ≤ 8, то на 8.

8) Среди вершин связного графа G₁ нет вершины j=3. Возвращаемся к п. 6.

6.) В строке 3 выбираем элементы, равные единице: r³₃₃ = r³₃₆ = 1. Следовательно, во второй связный подграф G₂ входят вершины 3, 6.

7) Определяем номер очередной вершины i = 3 + 1 = 4. Так как 4 ≤ 8, то на 8.

8.) Среди вершин связных подграфов G₁ и G₂ нет вершины j = 4. Возвращаемся к п. 6.

6.) В строке 4 выбираем элементы, равные единице. r³₄₄ = r³₄₅ = 1. Следовательно, в третий связный подграф G₃ входят вершины 4, 5.

7) i = 4 + 1 = 5. Так как 4 ≤ 8, то на 8.

8) Среди вершин связных графов G_1, G_2, G₃ есть вершина j = 5. Переходим к п.7.

Аналогично проверяются вершины j = 6, 7, 8. Они входят в уже полученные выше подграфы.

9. Если проверены все вершины, то все связные подграфы найдены. Конец.

Таким образом в результате работы алгоритма найдены три связных подграфа:

G₁ = {1, 2, 7, 8}; G₂ = {3, 6}; G₃ = {4, 5} (см. рисунок 4.2)

.

Рис 4. 2.