2. °) Необходимость. Если x и y взаимодостижимы, то для любой вершины z 2 X, ввиду транзитивности отношения взаимодостижимости, из z 2 D(x) следует z 2 D(y), а из z 2 D(y) следует z 2 D(x), поэтому D(x) = D(y). £

7.3.1 Нахождение компонент и бикомпонент

Рассмотрим матрицу смежности R графа G над булевой алгеброй Bf0; 1g; обозначим через E единичную матрицу порядка n(G) и образуем последовательность матриц

E + R; (E + R)2; : : : ; (E + R)l,

элементы которых отражают наличие маршрутов (ормаршрутов) длины не более l. Для некоторого l0 (а именно для цепи (пути) наибольшей длины) выполняется условие

(E + R)l0 = (E + R)l+1 = (E + R)l0+2 = : : : .

Каждой системе одинаковых строк (или столбцов) “установившейся” матрицы соответствует компонента (бикомпонента) связности.

Введем еще несколько терминов, которые понадобятся нам в дальнейшем.

Перешеек (точка сочленения или шарнир) – это ребро (вершина), при удалении которого (которой) число компонент связности увеличивается на 1.

Максимальный связный подграф, не имеющий своих точек сочленения, называется блоком графа.

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

7.4Кратчайшие цепи

Вэтом pазделе pассматpивается несколько алгоpитмов нахождения кpатчайших цепей между заданной паpой веpшин, а также между всеми паpами веpшин гpафа.

чайшую цепь (по вершинам) [t g b s] или [t g e s]. В прямом направлении им соответствуют цепи [s b g t] и [s e g t]; обе эти цепи – кратчайшие; длина кратчайшей цепи равна 3. J

7.4.2Кратчайшая цепь между заданными вершинами (взвешенный граф)

Пусть задан граф G = (X; U) и отображение f : U 7!C, ставящее в соответствие каждому ребру u, соединяющему пару вершин xi; xj, число cij – вес или длину ребра. Таким образом, задается матрица весов ребер C = kcijk, размерности n £ n.

Если последовательность вершин и ребер

su1x1u2 : : : xl¡1ult

есть маршрут, соединяющий вершины s и t, то длина маршрута определяется как

c(s; t) = Pl cuk ,

k=1

где cuk = c(xi; xj) = cij; cij – вес ребра, соединяющего вершины xi; xj; рассматривается случай cij ¸ 0.

З а м е ч а н и В. данной задаче имеет смысл рассматривать униграф, так как если пару вершин xi; xj соединяет более чем одно ребро, можно заранее выбрать из них ребро с наименьшим весом.

I

Требуется найти кратчайший по длине маршрут (а мы показали, что это цепь), соединяющий вершины s и t.

Алгоритмы, приводимые ниже, используют разметку вершин. Составная метка при вершине x имеет вид L(x) = [p; l(x)], где p – метка предшествования, а l(x) – метка расстояния вершины x от s.

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

Шаг 0. Инициализация.

Назначим вершине s метку L(s) = [s; 0]. Для всех вершин x, отличных от s, x 6= s назначим метки L(x) = [x; 1].

Шаг 1. Разметка вершин. Основной цикл. Находим такое ребро (x; y), для которого

l(y) ¡ l(x) > c(x; y)

и заменяем метку вершины y на L0(y) = [x; l(x) + c(x; y)]. При этом метка l0(y) = l(x) + c(x; y) может только уменьшиться:

l0(y) < l(y) и l0(y) > 0 при y 6= s.

Этот процесс продолжаем до тех пор, пока имеется хотя бы одно ребро, для которого можно уменьшить метку.

Шаг 2. Нахождение кратчайшей цепи.

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

Начинаем с вершины t. Если ее метка есть [xk; l(t)], то xk есть вершина в искомой цепи, предшествующая t; при этом l(t) = l(xk)+ c(xk; t).

Далее итеративно: если метка вершины xk есть [xk¡1; l(xk)], то xk¡1 есть вершина в искомой цепи, предшествующая xk и

l(xk) = l(xk¡1) + c(xk; t)

В самом деле, метка l(t) в процессе разметки уменьшалась, а xk – последняя вершина, от которой уменьшалась метка l(t). Точно так же, найдется вершина xk¡1, для которой

l(xk) = l(xk¡1) + c(xk¡1; xk) и так далее.

Последовательность l(t); l(xk); l(xk¡1); : : : строго убывающая, поэтому в некоторый момент будет x0 = s.

Теорема 7.3 l(t) – длина кратчайшего маршрута из s в t и

M = [s = x0; : : : ; xk¡1; xk; : : : ; t]

этот кратчайший маршрут.

Д о к а з а т е л ь с т в о . Пусть в размеченном с помощью алгоритма графе имеется произвольный маршрут

s = x0; xk1 ; xk2 ; : : : ; xkn = t

длины c(s; t). Тогда

l(xkn ) ¡ l(xkn¡1 ) · c(xkn¡1 ; xkn )

Просуммировав левые и правые части неравенств, получим:

Таким образом, длина произвольного маршрута не меньше длины маршрута, полученного с помощью алгоритма; следовательно, этот маршрут – кратчайший. £

228 Глава 7. Связность графов

Пример 7.7.

Цифры в столбце слева от массива меток показывают начальную вершину x, цифра в строке на верху таблицы – конечную вершину y ребра (x; y), выбранного для разметки. Таким образом, длина кратчайшего маршрута равна 13, а сам маршрут, начиная