Лабораторная работа 4 ОТКДС (Методичка для 4 лабы по ОТКДС), страница 2

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₄ - после вершин, входящих в первый и второй классы эквивалентности.

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

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

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

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

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

В задаче рассматривается неориентированный граф, у которого в матрице смежности R элементы матрицы r_ij = r_ji , 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 (равенство каждого элемента r^N_ij = r^N-1_{ij ,} i, j = 1,…,n). Если это условие выполняется, переходим к п.6, если нет - к п. 3.

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

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

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

7. В строке с номером i=1 выбираем элементы r^N_ij = 1. Номера тех столбцов j, в которых r^N_ij = 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 = R²

.

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

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

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

N = 1 + 1 = 2.

Умножение R²  R = R³

.

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

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

6. i =1.

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

r³₁₁ = r³₁₂ = r³₁₇ = r³₁₈ = 1.

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

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

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

8. i = 2 + 1 = 3.

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

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

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

r³₃₃ = r³₃₆ = 1 .

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

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

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

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

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

r³₄₄ = r³₄₅ = 1 .

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

8. i = 4 + 1 = 5.

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

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

G₁ = {1, 2, 7, 8}; G₂ = {3, 6}; G₃ = {4, 5}.

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

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

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

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

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

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