Лабораторная работа №4 ОТКДС (Лаб_р_№4_на А4)

Посмотреть архив целиком

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. Предложить словесное содержание задачи, отвечающей заданному графу.



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


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

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

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

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

AiAj (4.1)

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

Ai Aj (4.2)

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

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

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

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

AiAj , AiAj , (i, j = 1,2,…,n) (4.3)

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

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



Э
лементы
rNij матрицы RN, определяются как

Вычисления следует прекратить, если RN = RN-1 (т.е. все элементы rNij = rN-1ij , i, j = 1,…,n).

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

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

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

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

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

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

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

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

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

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

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

8. Проверяем условие выполнения равенства матриц RN и (RN-1)', то есть равенство каждого элемента rNij = (rN-1ij)' . Если это условие выполняется, то переходим к п. 10, если нет - к п. 9.

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

Если все элементы матрицы rij = 1, то нет необходимости в дальнейших вычислениях матрицы RN+1 , так как очевидно RN = RN+1 , т.е. rNij = 1, для (i, j) = 1, 2,…, n

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

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

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

Квадратные матрицы, состоящие из единиц, опирающихся на главную диагональ, образуют классы эквивалентности вершин. Если для данного графа мы получили m классов эквивалентности (m n), то есть B1,…,Bm , и в каждый класс эквивалентности Bd , d = 1,2,…,m входят Sd вершин графа, то можно сказать, что вершины, входящие в класс эквивалентности Bd, расположенные выше и левее класса эквивалентности Bl в матрице Rc будут предшествовать в Гамильтоновом пути вершинам из класса эквивалентности Bl .

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

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

A1A2 , A2A3 , A3A4 , A5A4 , A6A4 ,

A1A4 , A2A4 , A6A5 ,

A1A6 , A2A5 ,

A2 A6 . (4.4)

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

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

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

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






Рис. 4.1


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




4. N=0+1=1.

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

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

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

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

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

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




Рис. 4.2


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

1 0 = 0 - существует прямой путь из A1 в A1, но нет из A1 в A3;

1 1 = 1 - существуют прямые пути из A1 в A2 и из A2 в A3; следовательно, имеется путь длины 2 из A1 в A3;

0 1 = 0 - не существует прямого пути из A1 в A3, но есть из A3 в A3;

0 0 = 0 - нет прямого пути из A1 в A5 и из A5 в A3;

1 0 = 0 - существует прямой путь из A1 в A6, но нет из A6 в A3.

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

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



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

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

4. N=2.

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

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

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


(R2 ) ' = .


7. Производим умножение (R2 ) ' R ' = R3.


R 3 = .


8. R3 (R2 ) '

9. Все элементы R3, равны единице. Очевидно, что и R4 и R5 и т.д. также будут равны, т.е. будут иметь все элементы, равные единице).

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

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




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






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

- в первый класс входят вершины A1 A2 A5 A6;

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

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

Определение гамильтонова пути становится совсем простым делом. С учетом необходимости выполнения условий (4.4) для вершин, входящих в один класс эквивалентности, он может быть таким: A1,A6,A5,A2,A3,A4.

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

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


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

Используя алгоритм Фаулкса, можно предложить алгоритм решения другой задачи на графе, которую можно сформулировать следующим образом.

Пусть дана матрица смежности некоторого графа G , имеющего n вершин. Необходимо определить, является ли этот граф связным. В случае, если граф несвязный, он распадается на определенное число т связных графов G1, G2,…, Gm таких, что, например, из любой вершины графа G1 можно найти путь к любой другой вершине этого же графа G1 по его ребрам, но нельзя найти путь ни к одной вершине, не принадлежащей графу G1.

В предлагаемой задаче требуется выделить из графа G связные графы G1, G2,…, Gm , указав при этом, какие вершины входят в каждый из графов.

В задаче рассматривается неориентированный граф, у которого в матрице смежности R элементы матрицы rij = rji , i, j = 1,…,n , то есть матрица симметрична относительно главной диагонали.

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

1. Задаем матрицу смежности R графа.

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

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

4. Находим матрицу R N, полученную перемножением R N-1 R

5. Проверяем условие равенства матрицы R N и R N-1 (равенство каждого элемента rNij = rN-1ij , i, j = 1,…,n). Если это условие выполняется, переходим к п.6, если нет - к п. 3.

Матрица R N позволяет определить количество связных графов и номера вершин, входящих в каждый связный граф.

Для этого необходимо в каждой i - строке матрицы R N найти элементы rNij = 1, i, j = 1, …, n . Номера столбцов j , где rij = 1, и будут номерами вершин, входящих в связный граф. Вполне очевидно, что нет необходимости проверять строки с номерами вершин, образующих этот связный граф, так как полученные номера будут полностью совпадать с номерами вершин, входящих в него.

6. Задаемся номером строки, с которой необходимо начать проверку матрицы i=1.

7. В строке с номером i=1 выбираем элементы rNij = 1. Номера тех столбцов j, в которых rNij = 1, дают нам номера вершин, входящих в один из связных графов.

8. Увеличиваем на единицу номер просматриваемой строки i= i+1.

9. Если среди вершин уже выделенных связных графов есть вершина с номером i , то переходим к п. 10.

10. Если i < n (где n x n - размерность исходной матрицы смежности), то переходим к п. 7, если i = n , то к п. 11.

11. Конец.


Пример.

  1. Пусть задана матрица смежности R некоторого графа G , имеющего n = 8 вершин, и надо проверить этот граф на связность:


.

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

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

3. N= 0+1 =1.

4. Производим умножение R R = R2

.


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

В матрице R2 по сравнению с матрицей R, появилась, например, единица, показывающая связь между вершинами 1 и 7 (и, соответственно, между 7 и 1). Значит, есть путь длиной 2 из 7 в 1 через вершину 8.

5. Проверяем условие равенства R2 и R . Они не равны. Переходим к п. 3.

N = 1 + 1 = 2.

Умножение R2 R = R3


.


Проверяем условие равенства матриц R2 и R3. Так как они равны, то это означает, что путь длиной 2 - максимальный в данной графе, и дальнейшее перемножение матрицы не имеет смысла, так как мы будем получать одну и ту же матрицу.

Наличие нулей в полученной матрице показывает, что между соответствующими элементами отсутствует путь любой длины и, следовательно, данный граф — несвязный.

6. i =1.

7. В строке 1 выбираем все элементы r31j , равные единице 1 (j=1,…,n).

r311 = r312 = r317 = r318 = 1.

Номера столбцов, в которых r3ij = 1 - это номера вершин первого связного подграфа, входящего в данный граф, т.е. вершины 1, 2, 7, 8 образуют связный подграф G1 .

8. Определяем номер очередной вершины i = 1 + 1 = 2.

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

8. i = 2 + 1 = 3.

9. Среди вершин связного графа G1 нет вершины j=3.

10. Номер вершины j=3 меньше числа вершин графа (n=8). Возвращаемся к п. 7.

7. В строке 3 выбираем элементы, равные единице:

r333 = r336 = 1 .

Следовательно, во второй связный подграф G2 входят вершины 3, 6.

8. Определяем номер очередной вершины i = 3 + 1 = 4.

9. Среди вершин связных подграфов G1 и G2 нет вершины j = 4.

10. Так как i < 8 , переходим к п. 7.

7. В строке 4 выбираем элементы, равные единице.

r344 = r345 = 1 .

Следовательно, в третий связный подграф G3 входят вершины 4, 5.

8. i = 4 + 1 = 5.

9. Среди вершин связных графов G1, G2, G3 есть вершина j = 5. Переходим к 8. Аналогично проверяются вершины j = 6, 7, 8.

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

G1 = {1, 2, 7, 8}; G2 = {3, 6}; G3 = {4, 5}.


Определение Эйлеровой линии в графе

Одна из важных задач теории графов заключается в нахождении цикла, содержащего по одному разу все ребра графа. Этот цикл называется Эйлеровой линией или Эйлеровым путем на графе, а задачу называют задачей Эйлера. Графы, на которых существуют Эйлеровы линии, называют Эйлеровыми графами.

На практике задача нахождения Эйлеровой пинии на графе может встретиться, например, при определении порядка регламентных проверок исправности каналов связи между звеньями какой-нибудь достаточно сложной системы, обслуживаемой одной ремонтной единицей.

Ответ на вопрос о существовании Эйлеровой линии на графах дает теорема Эйлера.

Теорема Эйлера для неориентированных графов: для того чтобы на графе существовала Эйлерова линия, необходимо и достаточно, чтобы он был связным и степени всех его вершин были четными.

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

Для нахождения Эйлеровой линии на графе удобнее воспользоваться следующим алгоритмом (рассматривается неориентированный граф):

0. Задается начальный шаг итерации k =0. Проверяется условие существования Эйлерова пути. Задается начальная (она же и конечная) вершина Эйлерова пути V0 . Если, например, V0 = A3, то это означает, что начальной вершиной Эйлерова пути на шаге k = 0 выбрана третья вершина графа.

1. k=k+1. Определяются все вершины, непосредственно связанные непомеченными ребрами с вершиной Vk-1.

2. Определяется число Sk этих непомеченных ребер. Если Sk= 1, то вторая вершина, инцидентная этому ребру, становится очередной вершиной Vk Эйлерова пути, и это ребро помечается. Возвращаемся на п. 1.

При Sk >1, среди вершин, смежных Vk-1, выбирается вершина с наименьшим номером k, которая становится очередной вершиной Vk Эйлерова пути. Ребро, соединяющее эту вершину с вершиной Vk-1, помечается. Возвращаемся на п. 1.

При Sk = 0, для каждой, уже найденной вершины, принадлежащей Эйлеровому пути и имеющей непомеченные инцидентные ребра, строится цикл по этим ребрам. Определение каждой вершины этого цикла начинается с п. 1.

Каждый построенный таким образом цикл объединяется с ранее построенными, и они образуют Эйлерову линию.

Отметим, что выбор вершины с наименьшим номером нужен для того, чтобы была определенность при выборе вершины на каждом шаге. Можно, однако, предложить выбор вершин и с наибольшим номером.

В качестве примера рассмотрим задачу нахождения Эйлеровой линии для графа (рис. 4.3) с начальной вершиной 3.

0. k = 0. Эйлерова линия существует, так как степени всех вершин четные. Выберем начальную вершину номер 3, т.е. V0 = 3. Число непомеченных ребер n = 11.

1. k = 1. С вершиной 3 связаны вершины 1, 2.

2. S1 = 2. Следующей вершиной Эйлерова пути является вершина 1. Ребро 3-1 помечается. Возвращаемся к 1.

1. k = 2. С вершиной 1 связаны вершины 2, 4, 6.

2. S2 = 3. Вершина 2. Помечается ребро 1-2. Возвращаемся к 1.

1. k = 3. С вершиной 2 связаны вершины 3, 5, 7.




Рис. 4.3


2. S3 = 3. Вершина 3. Помечается ребро 2-3. Возвращаемся к 1.

1. k = 4. С вершиной 3 связаны вершины 1, 2.

2. S4 = 0. Вершин таких нет. Следовательно, получен цикл 3-1-2-3, который еще не является Эйлеровой линией.

Вершины 1 и 2, входящие в этот цикл, имеют непомеченные инцидентные ребра. Рассмотрим вершину 1 в качестве начальной точки следущего цикла A4 = 1.

1. k = 5. Вершины 4, 6.

2. S5 = 2. Вершина 4. Ребро 1-4.

1. k = 6. Вершина 5.

2. S6 = 1. Вершина 5. Ребро 4-5.

1. k = 7. Вершины 2, 7, 8.

2. S7 = 3. Вершина 2. Ребро 5-2.

1. k = 8. Вершина 7.

2. S8 = 1. Вершина 7. Ребро 2-7.

1. k = 9. Вершины 5, 6, 8.

2. S9= 3. Вершина 5. Ребро 7-5.

1. k = 10. Вершина 8.

2. S10 = 1. Вершина 8. Ребро 5-8.

1. k = 11. Вершина 7.

2. S11 = 1. Вершина 7. Ребро 8-7.

1. k = 12. Вершина 6.

2. S12 = 1. Вершина 6. Ребро 7-6.

1. k = 13. Вершина 1.

2. S13 = 1. Вершина 1. Ребро 6-1.

1. k = 14. Вершин, связанных непомеченными ребрами, нет.

2. S14 = 0. В найденных циклах нет вершин, имеющих инцидентные непомеченные ребра. Следовательно, работа алгоритма заканчивается и для нахождения Эйлеровой линии необходимо объединить два найденных цикла 3-1-2-3 и 1-4-5-2-7-5-8-7-6-1 в вершине_1. Результатом объединения будет Эйлерова линия 3-1-4-5-2-7-5-8-7-6-1-2-3.


Контрольные вопросы

1. Как определить по матрице смежности начальные и конечные вершины графа?

2. Какое максимальное число классов эквивалентности может быть в графе?

3. Чему равно число Гамильтоновых путей в насыщенном графе?

4. Что такое связный граф?

5. Как по матрице смежности неориентированного графа определить существование Эйлерова пути?

6. Во всяком ли связном графе существует Эйлеров путь?