Вопросы для самоконтроля

1. Что из себя представляет маршрут в графе?

2. Как определяется длина маршрута?

3. Что такое маршрут в графе. Как определяется длина маршрута?

4. Дайте определение цепи, цикла, простого цикла и простой цепи в графе.

5. Какой граф называется связным?

6. Что такое компонента связности?

7. Что такое блок графа?

8. Дайте определение разреза, правильного разреза графа. Приведите примеры.

9. Дайте определение вершинной связности. Приведите примеры.

10. Дайте определение реберной связности. Приведите примеры.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Задайте произвольный граф G = (X, U), |X| = 5, |U| = 7. Определите количество маршрутов длиной 2, 3, 4.

2. Составьте словесный алгоритм определения маршрутов в графе.

3. Составьте структурную схему алгоритма определения маршрутов в графе.

4. Задайте произвольный граф G = (X, U), где ½X½ = 6; ½U½ = 10. Постройте маршрут, цепь, цикл, простую цепь, простой цикл. Покажите на примере отличия между этими видами маршрутов.

5. Составьте структурную схему алгоритма или словесный алгоритм определения связности произвольного неориентированного графа.

6. Задайте произвольный граф G = (X, U), где ½X½ = 6; ½U½ = 18. Приведите пример правильного разреза и разреза графа.

7. Приведите пример графа, имеющего точку сочленения.

8. Приведите пример неразделимого графа.

9. Приведите пример графа блоков.

10. Постройте граф G и покажите на его примере взаимосвязь между числом реберной и вершинной связности и минимальной локальной степенью вершин графа.

 

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

 

Нахождение кратчайших маршрутов (цепей)

Алгоритм Форда

Приведем алгоритм Форда нахождения маршрутов с минимальной суммарной стоимостью ребер. Будет анализироваться помеченный граф с весами на ребрах. Граф с весами на ребрах называется взвешенным.

1°. Строим матрицу R взвешенного графа G.

Если вершины не смежны между собой, то в матрице ставим M. Фиксируем одну вершину x_k и приписываем ей вес V(k) = 0, всем остальным вершинам приписываем вес V(j) = M.

2°. Берем произвольную вершину x_j ¹ x_k и находим смежную с x_j вершину x_i, имеющую вес r_i,j. В начальный момент в качестве вершины x_i берем фиксированную x_k. Для x_j и x_i проверяется выполнение неравенства

                                            V(j) > V(i) + r_i,j.                                 (15.8)

Если оно выполняется, то прежний вес V(j) вершины x_j заменяется суммой V(i) + r_i,j. В противном случае, вес V(j) остается неизменным.

3°. Повторяем пп. 1, 2 пока не рассмотрены все вершины.

4°. Конец работы алгоритма.

Для уменьшения объема вычислений операцию пересчета индексов сначала выполняют для всех x_j, смежных с фиксированной x_k, а затем продолжают это для вершин, смежных с выбранными ранее.

Операция пересчета производится для всех вершин графа до тех пор, пока ни одна из вершин не сможет принимать нового значения V(j). Тогда длинами кратчайших цепей от x_j до x_k будут величины V(j), полученные в результате замен переменных весов V(j) на новые.

Например, для графа G рис. 15.31 выполним алгоритм Форда.

Рис. 15.31. Пример графа G

В матрице R по главной диагонали проставлены нули, так как в графе G нет петель. При отсутствии связи между вершинами проставлен знак М.

Матрица смежности этого графа запишется так:

	1	2	3	4	5	6	7
1	0	4	5	9	M	2	M	.
2	4	0	M	M	M	5	6
3	5	M	0	3	3	M	7
R = 4	9	M	3	0	8	M	M
5	M	M	3	8	0	M	1
6	2	5	M	M	M	0	3
7	M	6	7	M	1	3	0

Принимаем вес вершины х ₁ равным V(1) = 0, V(2) = V(3) = … = V(7) = M = ¥.

1) Фиксированная вершина x_k = x ₁.

2) Просматриваем все пары x_i, x_j и проверяем выполнение неравенства (15.8).

Пусть i = 1, j = 2, тогда имеем V(1) = 0, V(2) = M, r_1,2 = 4.

Условие неравенства V(2) = M > V(1) + r _1,2 = 0 + 4 = 4. Поэтому вершине x ₂ присваиваем новый вес V(2)¹ = 4.

Для вершин, у которых r_i,j = M, неравенство (15.8) выполняться не будет и вес V(j) останется прежним.

Далее, для x ₃: V(3) = M > V(1) + r _1,3 = 0 + 5 = 5 и V(3)¹ = 5.

Для x ₄: V(4) = M > V(1) + r _1,4 = 0 + 9 = 9 и V(4)¹ = 9.

Для x ₆: V(6) = M > V(1) + r _1,6 = 0 + 2 = 2 и V(6)¹ = 2.

Теперь произведем пересчет индексов для вершин, смежных с x ₁, с учетом пути через другие смежные вершины.

Для x ₂: V(2) = 4 < V(6) + r _2,6 = 2 + 5 = 7, значит, индекс вершины остается без изменения.

Для x ₄: V(4) = 9 > V(3) + r _4,3 = 5 + 3 = 8, следовательно, меняем значение V(4) с 9 на 8 (см рис. 1.31).

Для x ₆: V(6) = 2 < V(2) + r _2,6 = 4 + 5 = 9, здесь индекс остается без изменения.

Произведем пересчет индексов для вершин, несмежных с фиксированной вершиной x ₁.

Вычислим индекс вершины x ₅, его можно найти через x ₃, x ₄ или x ₇. Индекс x ₇ равен М, поэтому для нее неравенство (15.8) не выполняется.

Вычислим индекс вершины x ₅ через x ₄. Получим V(5)₄¹ = M > V(4)¹ + r _4,5 = 8 + 8 = 16.

Приняв V(5)¹ = 16 за старое значение индекса, пересчитаем его через x ₃:

V(5)₃¹= 16 > V(3)¹ + r_3,5 = 5 + 3 = 8.

Так как условие (15.8) выполняется, то значение индекса V(5)¹ = 16 заменяем на V(5)² = 8.

Индекс x ₇ можно определить через x ₂, x ₃, x ₅, x ₆.

V(7)₂¹ = M > V(2)¹ + r_2,7 = 4 + 6 = 10,

V(7)₅¹ = M > V(5)¹ + r_5,7 = 8 + 1 = 9,

V(7)₃¹ = M > V(3)¹ + r_3,7 = 5 + 7 = 12,

V(7)₆¹ = M > V(6)¹ + r_6,7 = 2 + 3 = 5.

Итак, V(1) = 0, V(2) = 4, V(3) = 5, V(4) = 8, V(5) = 8, V(6) = 2, V(7) = 5.

Алгоритм Форда дает кратчайшее расстояние от выбранных вершин до фиксированной вершины, а сами цепи не определяет.

Для определения цепи от выбранной вершины до фиксированной воспользуемся равенством V(j) ─ V(i) = r_i,j.

Например, найдем путь от x ₇ до x ₁. Ищется предпоследний шаг при пересчете индекса V(7)¹. Это x ₇ ─ x ₆. Затем для x ₆ определяется вершина пересчета. Это x ₆ - x1. Следовательно, кратчайший путь x ₇ ─ x ₆ ─ x ₁, а кратчайшее расстояние между вершинами x ₁ и x ₇ определено ранее V(7)¹ = 5.

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

На рис. 15.32 приведен пример, когда необходимо определить путь из вершины

Рис. 15.32. Пример нахождения минимального маршрута

А в В с минимальной стоимостью. При выборе ближайшей вершины 1 из вершины А получим длину маршрута АВ = 13. Например, длины маршрутов А – 1 – 6 – 7 – В или А – 1 – 2 – 7 – 8 – В равны 13. В то же время все другие маршруты (через вершину 3) дают длину маршрута АВ = 8 (например, А – 3 – 4 – 5 – В).

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

Алгоритм Дейкстры

Рассмотрим алгоритм Дейкстры нахождения кратчайшей цепи между двумя заданными вершинами х_s и х_t.

Метод основан на приписывании вершинам временных пометок, причем пометка вершины x_i дает верхнюю границу длины пути от вершины х_s к этой вершине. Значения этих пометок постепенно уменьшаются на основе итерационной процедуры и на каждом шаге итерации точно одна из временных пометок становится постоянной. Это говорит о том, что пометка дает длину кратчайшей цепи от вершины х_s к рассматриваемой вершине.

Алгоритм:

Пусть l (x_i) ─ пометка x_i.

(блок присвоения начальных значений)

1°. Пусть l (s) = 0. Положим l (x_i) = ¥ для всех x_i ¹ s и считаем их пометки временными; пусть p = s.

(блок обновления пометок)

2°. Для всех x_i Î Г(p), пометки которых временные, изменить пометки в соответствии с выражением

                                 l (x_i) min[ l (x_i); l (p) + r(p, x_i)]                  (15.9)

(блок превращения пометки в постоянную)

3°. Среди всех вершин с временными пометками найти такую, что l (x_i ^*) =     

= min[ l (x_i)].

4°. Считать пометку x_i ^* постоянной и положить p = x_i ^*.

5°.

а) Если надо построить цепь от вершины х_s к вершине х_t:

Если p = t, то l (p) ─ длина кратчайшей цепи, останов.

Если p ¹ t, переход к п. 2°.

б) Если надо построить цепь от вершины х_s ко всем остальным вершинам:

Если все вершины отмечены как постоянные, то эти пометки дают длины кратчайших цепей, останов.

Если некоторые вершины являются временными, переход к п. 2°.

Рассмотрим последовательность выполнения алгоритма Дейкстра на примере построения кратчайших цепей в графе (см. рис. 15.31).

Матрица смежности графа G имеет следующий вид:

	1	2	3	4	5	6	7
1	0	4	5	9	0	2	0	.
2	4	0	0	0	0	5	6
3	5	0	0	3	3	0	7
R = 4	9	0	3	0	8	0	0
5	0	0	3	8	0	0	1
6	2	5	0	0	0	0	3
7	0	6	7	0	1	3	0

Постоянные пометки будем обозначать *, остальные считаются временными.

Вначале нам необходимо выбрать начальную вершину x_s, которую мы будем использовать в дальнейшем, в качестве фиксированной. Примем в качестве такой вершины x ₁. Метки всех остальных вершин, отличных от вершины x _1, считаем равными ¥, а значение p = x ₁.

1°. L(x ₁) = 0^*. L(x_i) = ¥, " x_i ¹ x ₁, p = x ₁.

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

Первая итерация

2°. Для всех вершин, смежных с начальной вершиной x ₁ и имеющих временные метки G(x ₁) = { x ₂, x ₃, x ₄, x ₆}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₂) min[ ¥; 0^*+ 4 ] = 4.

Для l (x ₃) min[ ¥; 0^*+ 5 ] = 5.

Для l (x ₄) min[ ¥; 0^*+ 9 ] = 9.

Для l (x ₆) min[ ¥; 0^*+ 2 ] = 2.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 4, 5, 9, ¥, 2, ¥ ]

         x ₂ x ₃ x ₄ x ₅ x ₆ x ₇

Очевидно, что такой вершиной является вершина x ₆.

4°. Вершина x ₆ получает постоянную пометку l (x ₆) = 2^*, значение p = x ₆.

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

Вторая итерация

2°. Для всех вершин, смежных с текущей вершиной x ₆ и имеющих временные метки G(x ₆) = { x ₂, x ₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток:

Для l (x ₂) min[ 4; 2^*+ 5 ] = 4.

Для l (x ₇) min[ ¥; 2^*+ 3 ] = 5.

Новое значение метки для вершины x ₂ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершины x ₇ заменяем значение l (x ₇) = ¥ на полученное значение l (x ₇) = 5.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min[ 4, 5, 9, ¥, 5]

    x ₂ x ₃ x ₄ x ₅ x ₇

Очевидно, что такой вершиной является вершина x ₂.

4°. Вершина x ₂ получает постоянную пометку l (x ₂) = 4^*, значение p = x ₂.

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

Третья итерация

2°. Для всех вершин, смежных с текущей вершиной x ₂ и имеющих временные метки G(x ₂) = { x ₇}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₇) min[ 5; 4^*+ 6 ] = 5.

Новое значение метки для вершины x ₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки l (x ₇) = 5.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

 Min [ 5, 9, ¥, 5 ]

     x ₃ x ₄ x ₅ x ₇

В данном случае две вершины имеют одинаковые метки l (x ₃) = l (x ₇) = 5 и мы можем выбрать любую из них. Пусть это будет вершина x ₃.

4°. Вершина x ₃ получает постоянную пометку l (x ₃) = 5^*, значение p = x ₃.

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

Четвертая итерация

2°. Для всех вершин, смежных с текущей вершиной x ₃ и имеющих временные метки G(x ₃) = { x ₄, x ₅, x ₇} пересчитываем в соответствии с выражением (1.9) действующие значения их меток:

для l (x ₄) min[ 9; 5^*+ 3 ] = 8,

для l (x ₅) min[ ¥; 5^*+ 3 ] = 8,

для l (x ₇) min[ 5; 5^*+ 7 ] = 5.

Новое значение метки для вершины x ₇ оказалось больше текущего, поэтому оставляем текущее значение временной метки, а для вершин x ₄ и x ₅ заменяем текущие значения меток на новые.

3°. Выбираем из списка вершин с временными метками, вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 8, 5 ]

     x ₄ x ₅ x ₇

Очевидно, что такой вершиной является вершина x ₇.

4°. Вершина x ₇ получает постоянную пометку l (x ₇) = 5^*, значение p = x ₇.

5°. Не все вершины имеют постоянные пометки, переходим к п. 2°.

Пятая итерация

2°. Для всех вершин, смежных с текущей вершиной x ₇ и имеющих временные метки G(x ₇) = { x ₅}, пересчитываем в соответствии с выражением (15.9) действующие значения их меток.

Для l (x ₅) min[ 8; 5^*+ 1 ] = 6.

3°. Выбираем из списка вершин с временными метками вершину с временной меткой, имеющей минимальное значение:

Min [ 8, 6 ]

     x ₄ x ₅

Такой вершиной является вершина x ₅.

4°. Вершина x ₅ получает постоянную пометку l (x ₅) = 6^*, значение p = x ₅.

5°. Поскольку не все вершины имеют постоянные пометки, переходим к п. 2°.

Шестая итерация

2°. Из вершин, смежных с текущей вершиной x ₃ и имеющих временные метки осталась только вершина x ₄: G(x ₁) = { x ₄}. Пересчитываем значение ее метки в соответствии с выражением (15.9):

для l (x ₄) min[ 8; 6^*+ 8 ] = 8.

Новое значение метки для вершины x ₄ оказалось больше текущего, поэтому оставляем текущее значение временной метки.

3°. В списке вершин с временными метками только один элемент:

Min [ 8, ]

     x ₄

4°. Вершина x ₄ получает постоянную пометку l (x ₄) = 8^*, значение p = x ₄.

5°. Поскольку все вершины графа имеют постоянные метки, конец алгоритма.

Таким образом, мы построили кратчайшие пути от вершины x ₁ до вершин x ₂, x ₃, x ₆ напрямую:

x ₁ ® x ₂(4^*), x ₁ ® x ₃(5^*), x ₁ ® x ₆(2^*),

а до вершин x ₄, x ₅, x ₇ через промежуточные:

x ₁ ® x ₃ ® x ₄(8^*);

x ₁ ® x ₆ ® x ₇ ® x ₅(6^*);

x ₁ ® x ₆ ® x ₇(5^*).

Длину цепи x_s ® x_i, т.е. суммарную стоимость весов пройденных ребер, можно получить при помощи рекурсивной процедуры:

l (x_s) + r (x_s, x_j) = l (x_i),

т.е. проверяется, какая из вершин, смежных вершине x_s, дает вместе с весом ребра r (x_s, x_j) сумму, равную l (x_i).

Например: l (x ₄)= 8. Поскольку вершина x ₄ напрямую не связана с вершиной x ₁, то определим кратчайший путь из x ₁ в x ₄:

l (x ₁) = l (x ₄)─ r (x ₃, x ₄) = 8 – 3 = 5 = l (x ₃) - r (x ₁, x ₃) = 5 – 5 = 0.

Таким образом, построена кратчайшая цепь между вершинами x ₁ и x ₄: x ₁ ® x ₃ ® x ₄.