diskr_edit (1023554), страница 9
Текст из файла (страница 9)
Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид:
C = 
.
Шаг 2. Положим k = 0, 1(0) = 0, 2(0) = 3(0) = 4(0) = 5(0) = 
. Эти значения занесем в первый столбец табл. 3.2.
Шаг 3.
k = 1.
1(1) = 0.
Равенство (3.1) для k = 1 имеет вид:
i(1) = 
{j(0) + cji}.
2(1) = min{1(0) + c12; 2(0) + c22; 3(0) + c32; 4(0) + c42; 5(0) + c52;} = min{0 – 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = –1.
3(1) = min{1(0) + c13; 2(0) + c23; 3(0) + c33; 4(0) + c43; 5(0) + c53;} = min{0 + ¥ ; ¥ – 8; ¥ + ¥; ¥ – 2; ¥ + ¥} = ¥ .
4(1) = min{1(0) + c14; 2(0) + c24; 3(0) + c34; 4(0) + c44; 5(0) + c54;} = min{0 + ¥ ; ¥ – 7; ¥ + ¥; ¥ + ¥; ¥ – 4} = ¥ .
5(1) = min{1(0) + c15; 2(0) + c25; 3(0) + c35; 4(0) + c45; 5(0) + c55;} = min{0 – 3; ¥ – 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = –3.
Полученные значения i(1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин i(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги.
k = 2.
1(2) = 0.
Равенство (3.1) для k = 2 имеет вид:
i(2) = {j(1) + cji}.
2(2) = min{0 – 1; –1 + ¥; ¥ + ¥; ¥ + ¥; –3 + ¥} = –1.
3(2) = min{0 + ¥ ; –1 – 8; ¥ + ¥; ¥ – 2; –3 + ¥} = –9 .
4(2) = min{0 + ¥ ; –1 – 7; ¥ + ¥; ¥ + ¥; –3 – 4} = –8 .
5(2) = min{0 – 3; –1 – 1; ¥ + 5; ¥ + ¥; –3 + ¥} = –3.
Полученные значения i(2) занесем в третий столбец табл. 3.2. Величины i(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг.
k = 3.
1(3) = 0.
Равенство (3.1) для k = 3 имеет вид:
i(3) = {j(2) + cji}.
2(3) = min{0 – 1; – 1 + ¥; – 9 + ¥; –8 + ¥; – 3 + ¥} = – 1.
3(3) = min{0 + ¥ ; – 1 – 8; – 9 + ¥; –8 – 2; – 3 + ¥} = – 10 .
4(3) = min{0 + ¥ ; – 1 – 7; – 9 + ¥; –8 + ¥; – 3 – 4} = – 8 .
5(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ¥; – 3 + ¥} = – 4.
Полученные значения i(3) занесем в четвертый столбец табл. 3.2. Величины i(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг.
k = 4.
1(4) = 0.
Равенство (3.1) для k = 4 имеет вид:
i(4) = {j(3) + cji}.
2(4) = min{0 – 1; – 1 + ¥ ; – 10 + ¥; – 8 + ¥; – 4 + ¥} = – 1.
3(4) = min{0 + ¥ ; – 1 – 8; – 10 + ¥; – 8 – 2; – 4 + ¥} = – 10 .
4(4) = min{0 + ¥ ; – 1 – 7; – 10 + ¥; – 8 + ¥; – 4 – 4} = – 8 .
5(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ¥; – 4 + ¥} = – 5.
Полученные значения i(4) занесем в пятый столбец табл. 3.2. Величины i(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг.
Таблица 3.2
| i(номер вершины) | i(0) i(1) i(2) i(3) i(4) |
| 1 2 3 4 5 | 0 0 0 0 0 ¥ – 1 – 1 – 1 1 ¥ ¥ – 9 – 10 – 10 ¥ ¥ – 8 – 8 – 8 ¥ – 3 –3 – 4 – 5 |
Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом i(k) определяет длину максимального пути из первой вершины в i-ую, содержащего не более k дуг.
Таблица 3.3
| i(номер вершины) | i(0) i(1) i(2) i(3) i(4) |
| 1 2 3 4 5 | 0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 10 10 ¥ ¥ 8 8 8 ¥ 3 3 4 5 |
Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути.
Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. i(3) = i(4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n – 1.
Учитывая это замечание, для последней вершины x3 предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3:
r(2) + cr3 = 3(3), (3.7)
xrÎ G-1(x3), где G-1(x3) - прообраз вершины x3.
G-1(x3) = {x2, x4}.
Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется:
2(2) + c23 = 1 + 8 ¹ 3(4) = 10,
4(2) + c43 = 8 + 2 = 3(4) = 10.
Таким образом, вершиной, предшествующей вершине x3, является вершина x4.
Для вершины x4 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4:
r(1) + cr4 = 4(2), xrÎ G-1(x4), (3.8)
где G-1(x4) - прообраз вершины x4.
G-1(x4) = {x2, x5}.
Подставим в (3.8) последовательно r = 2, r = 3 и r = 5, чтобы определить, для какого r это равенство выполняется:
2(1) + c24 = 1 + 7 = 4(3) = 8,
5(1) + c54 = 3 + 4 ¹ 4(3) = 8,
Таким образом, вершиной, предшествующей вершине x4, является вершина x2.
Для вершины x2 предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2:
r(0) + cr2 = 2(1), xr
G-1(x2), (3.9)
где G-1(x2) - прообраз вершины x2.
G-1(x2) = {x1}.
Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство:
1(1) + c12 = 0 + 1 = 2(1) = 1.
Таким образом, вершиной, предшествующей вершине x2, является вершина x1.
Итак, найден максимальный путь – x1, x2, x4, x3, его длина равна 10.
3.10. Деревья.. Основные определения
Неориентированным деревом (или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения:
а) дерево есть связный граф, содержащий n вершин и n - 1 ребер;
б) дерево есть граф, любые две вершины которого можно соединить простой цепью.
Пример 3.17.
Графы, изображенные на рис. 3.12, являются деревьями.
Рис. 3.12
Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис. 6.1 как лес, состоящий из трех деревьев.
Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Пример 3.18.
Для графа, изображенного на рис. 3.13а), графы на рис. 3.13б) и 3.13в) являются остовными деревьями.
Рис. 3.13
Пусть граф G имеет n вершин и m ребер Так как всякое дерево с n вершинами по определению (см. раздел 6.1) имеет n – 1 ребер, то любое остовное дерево графа G получается из этого графа в результате удаления m – (n – 1) = m – n + 1 ребер. Число g = m – n + 1 называется цикломатическим числом графа.
3.11. Минимальные остовные деревья нагруженных графов
Граф G = (X, A) называется нагруженным, если для каждого ребра (xi,xj) определена его длина (или вес) cij.
Пусть G - связный нагруженный граф. Задача построения минимального остовного дерева заключается в том, чтобы из множества остовных деревьев найти дерево, у которого сумма длин ребер минимальна.
Приведем типичные случаи, когда возникает необходимость построения минимального остовного дерева графа.
а) Нужно соединить n городов железнодорожными линиями (автомобильными дорогами, линиями электропередач, сетью трубопроводов и т.д.) так, чтобы суммарная длина линий или стоимость была бы минимальной.
б)Требуется построить схему электрической сети, в которой клеммы должны быть соединены с помощью проводов наименьшей общей длины.
Задачу построения минимального остовного дерева можно решить с помощью следующего алгоритма.
Алгоритм 3.2 (Алгоритм Краскала).
Шаг 1. Установка начальных значений.
Вводится матрица длин ребер C графа G.
Шаг 2. Выбрать в графе G ребро минимальной длины. Построить граф G2, состоящий из данного ребра и инцидентных ему вершин. Положить i = 2.
Шаг 3. Если i = n, где n - число ребер графа, то закончить работу (задача решена), в противном случае перейти к шагу 4.
Шаг 4. Построить граф Gi +1, добавляя к графу Gi новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно какой-нибудь вершине графа Gi и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в Gi. Вместе с этим ребром включаем в Gi +1 и инцидентную ему вершину, не содержащуюся в Gi. Присваиваем i:= i +1 и переходим к шагу 3.
Пример 3.19.
Найдем минимальное остовное дерево для графа, изображенного на рис. 3.14.
Рис. 3.14
Шаг 1. Установка начальных значений.
Введем матрицу длин ребер C:
С =
.
Шаг 2. Выберем ребро минимальной длины. Минимальная длина ребра равна единице. Таких ребер три: (x1, x2), (x1, x4), (x2, x4). В этом случае можно взять любое. Возьмем (x1, x2). Построим граф G2, состоящий из данного ребра и инцидентных ему вершин x1 и x2. Положим i = 2.
Шаг 3. Так как n = 5, то i ¹ n, поэтому переходим к шагу 4.
Шаг 4. Строим граф G3, добавляя к графу G2 новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно одной из вершин x1, x2 и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G2 т. е. одной из вершин x3, x4, x5. Таким образом, нужно выбрать ребро минимальной длины из ребер (x1, x4), (x1, x5), (x2, x3), (x2, x4), (x2, x5). Таких ребер длины единица два: (x1, x4) и (x2, x4). Можно выбрать любое. Возьмем (x1, x4). Вместе с этим ребром включаем в G3 вершину x4, не содержащуюся в G2. Полагаем i = 3 и переходим к шагу 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
