Волновой алгоритм построения кратчайшего пути для взвешенного графа

1. Вершина Х_н получает вес V = 0, ее номер вводится в массив М номеров
вершин, изменивших вес. Остальные вершины X_i получают вес V_i = ∞, их номера не
попадают в массив М.

2. Если массив M пуст, то выполняется п. 3, иначе выбирается с исключением
из него очередная вершина X_i, и пересчитываются веса вершин, принадлежащих исходу G(X_i) вершины X_i: "X_i Î G (X_i)(V_j = min (V_j V_i + l_ij)). Если вес V_j уменьшается, то номер j включается в М. Снова выполняется п. 2.

3. Если вес V_i = ∞, то делается вывод, что пути из вершины Х_н к вершине X_k
нет, иначе выполняется процедура выделения дуг, такая же, как в волновом алгоритме
для невзвешенного графа, за исключением того, что разность весов вершин X_i и X_j должна быть равна l_ij.

4. После выделения дуг строятся кратчайшие пути, длины которых равны V_k.
Пример

1. V_i = V₁ = 0, V₂ = V₃ = V₄ = V₃ = V₆ = ∞, M = {1}

2. M ≠ 0, i = 1, M = 0, G(X₁) = {X₂, X₃}; V₂ = min (∞, 0 + 1)=1; M ={2}

V_i = min (∞, 0 + 4) = 4; M ={2,3};

2. M ≠ 0, i = 2, M = {3}, G(X₂) = {X₃, X₄}; V₃ = min (4, 1 + 2)=3; M = {3}; V₄ = min (∞, 1 + 5) = 6; M={3,4};

2. M ≠ 0, i = 3, M = {4}, G(X₃) = {X₄, X₅}; V₄ = min (6, 3 + 2)=5; M = {4}; V₅ = min (∞, 3 + 4) = 7; M={4,5};

2. M ≠ 0, i = 4, M = {5}, G(X₄) = {X₅, X₆}; V₅ = min (7, 5 + 1)=6; M = {5}; V₆ = min (∞, 5 + 4) = 9; M={5,6};

2. M ≠ 0, i = 5, M = {6}, G(X₆) = {X₆}; V₆ = min (9, 6 + 2)=8; M = {6};

2. M ≠ 0, i = 6, M = {0}, G(6) = {0};

3. G^-1(X₆) = {X₄, X₅}; V_x6 - V_x5 = 2; l₆ = 2,* V_x6 - V_x4 = 3, l_4,6 = 4.

G^-1(X₅) = {X₃, X₄}; V_x5 - V_x4 = 1; l_4,5 = 1,* V_x5 - V_x3 = 3, l_5,3 = 4.

G^-1(X₄) = {X₂, X₃}; V_x4 - V_x3 = 2; l_3,4 = 2,* V_x4 - V_x2 = 4, l_2,4 = 5.

G^-1(X₃) = {X₁, X₂}; V_x3 - V_x2 = 2; l_2,3 = 2,* V_x3 - V_x1 = 3, l_1,3 = 4.

G^-1(X₂) = {X₁}; V_x2 - V_x1 = 1; l₁ = 1,*

Построен кратчайший путь (Xн, Xк) длиной 8:

(X_н = Х₁, Х₂)( Х₂, Х₃)( Х₃, Х₄)( Х₄, Х₅)( Х₅, Х₆ = Х_к).

Процесс решения можно оформить в виде таблицы:

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

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

2. Во втором пункте алгоритма V_j = max (V_j, V_i + l_ij)

Обратный ход:

Построены три длиннейшие пути:

1. (Х₁, Х₂)( Х₂, Х₄)( Х₄, Х₆)

2. (Х₁, Х₃)( Х₃, Х₄)( Х₄, Х₆)

3. (Х₁, Х₃)( Х₃, Х₅)( Х₅, Х₆)

Алгоритм нахождения компонент связанности

Вершины Х_i и X_j слабо связны, если существует путь (Х_i и X_j) в графе (G,X).

Вершины X_i и X_j сильно связаны, если существуют пути (Х_i и X_j)и (X_j и Х_i) в графе (G, X).

Если в графе нет путей Х_i и X_jи нет обратного пути из Х_j в X_i, то вершины Х_i и X_j не связаны.

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

Пример 3.2.1

Алгоритм построения компонент связности в неориентированном графе

1. i=0. Все вершины графа не отмечены.

2. i=i+1. Выбираем очередную неотмеченною вершину, отмечаем ее и все
связанные с нею вершины значением индекса i с помощью распространения волны
отметок по ребрам, идущим от уже отмеченных индексом i вершин. Таким образом,
выделяется i компонента связности. Если есть еще неотмеченные вершины, то
выполняется п. 2, иначе выделение компонент связности закончено.

Дерево. Остов.

Деревом называется конечный связный граф без циклов. Из свойств связности и отсутствия циклов следует, что у дерева количество компонент связности р =1 и цикломатическое число g = 0 = m – n + 1, отсюда следует что m = n -1 ; т.е. число ребер в дереве на единицу меньше числа вершин. Ниже приведены примеры деревьев.

Рис.3

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: