10

Работа № 4. АЛГОРИТМЫ СОГЛАСОВАНИЯ И УПОРЯДОЧЕНИЯ НА ГРАФАХ И ИХ РЕАЛИЗАЦИЯ НА ЭВМ

Цель работы: изучение алгоритмов согласования и упорядочения на графах; овладение навыками реализации их на ЭВМ.

Задание

I. Поиск Гамильтоного пути (ГП) в графе.

1.1. Для заданного графически, ориентированного графа составить матрицу смежности R с единицами на главной диагонали (матрица достижимости за один шаг).

1.2. Найти ГП в графе, используя алгоритм Фаулкса.

1.3. Найти ГП в графе, используя алгоритм Робертса и Флореса (см. лекции) для начальной вершины, выбранной в п. 1.2.

1.4. Найти ГП в графе для начальной вершины, выбранной в п. 1.2, используя стандартную программу на ЭВМ, сравнить результаты.

1.5. Предложить словесное содержание задачи, отвечающей задан-ному графу.

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

2.1. Для заданного с помощью матрицы смежности неориентированного графа найти связные компоненты, используя алгоритм Фаулкса,

2.2. Представить заданный граф графически и предложить словесное содержание задачи, отвечающей указанному графу.

2.3. Найти связные компоненты в графе, используя стандартную программу на ЭВМ, сравнить результаты.

3. Поиск Эйлеровой линии (ЭЛ) в графе.

3.1. Для заданного графически, неориентированного графа составить матрицу смежности с единицами на главной диагонали (матрица достижимости за один шаг).

3.2. Найти ЭЛ в графе, используя алгоритм, приведенный в описании лабораторной работы.

3.3. Найти ЭЛ в графе для начальной вершины, выбранной в п. 3.2, используя стандартную программу на ЭВМ, сравнить результаты.

3.4. Предложить словесное содержание задачи, отвечающей заданному графу.

Методические указания

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

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

Если рассматривается всего одна единица оборудования, на которой выполняются различные работы, задача определения порядка выполнения работ является часто довольно сложной. Подобные проблемы, возникают при определении очередности решения задач на ЭВМ или порядка доставки груза многим потребителям при наличии одной транспортной единицы.

В качестве примера рассмотрим задачу определения очередности решения на ЭВМ вычислительной программы (алгоритма) А, состоящей из п подпрограмм 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 графа.