Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Алгоритм нахождения максимального пути
При решении некоторых практических задач возникает необходимость поиска максимального пути (пути с наибольшей суммой длин дуг). Такая задача сводится к задаче нахождения минимального пути заменой знаков при длинах дуг (в матрице весов C) на противоположные. При этом необходимым является требование отсутствия в ориентированном графе контуров положительной длины. Пример 3.16. С помощью модифицированного алгоритма 3.1 найдем максимальный путь из вершины х1 в вершину х3 в графе, изображенном на рис. 3.11. Рис. 3.11 Шаг 1. Введем число вершин графа n =5. Матрица весов этого графа после замены знаков при длинах дуг на противоположные имеет вид: C = . Шаг 2. Положим k = 0, l1(0) = 0, l2(0) = l3(0) = l4(0) = l5(0) = . Эти значения занесем в первый столбец табл. 3.2. Шаг 3. k = 1. l1(1) = 0. Равенство (3.1) для k = 1 имеет вид: li(1) = {lj(0) + cji}. l2(1) = min{l1(0) + c12; l2(0) + c22; l3(0) + c32; l4(0) + c42; l5(0) + c52;} = min{0 – 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = –1. l3(1) = min{l1(0) + c13; l2(0) + c23; l3(0) + c33; l4(0) + c43; l5(0) + c53;} = min{0 + ¥ ; ¥ – 8; ¥ + ¥; ¥ – 2; ¥ + ¥} = ¥ . l4(1) = min{l1(0) + c14; l2(0) + c24; l3(0) + c34; l4(0) + c44; l5(0) + c54;} = min{0 + ¥ ; ¥ – 7; ¥ + ¥; ¥ + ¥; ¥ – 4} = ¥ . l5(1) = min{l1(0) + c15; l2(0) + c25; l3(0) + c35; l4(0) + c45; l5(0) + c55;} = min{0 – 3; ¥ – 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = –3. Полученные значения li(1) занесем во второй столбец табл. 3.2. Убеждаемся, что второй столбец, начиная со второго элемента, совпадает с первой строкой матрицы весов, что легко объясняется смыслом величин li(1), которые равны длине минимального пути из первой вершины в i-ую, содержащего не более одной дуги. k = 2. l1(2) = 0. Равенство (3.1) для k = 2 имеет вид: li(2) = {lj(1) + cji}. l2(2) = min{0 – 1; –1 + ¥; ¥ + ¥; ¥ + ¥; –3 + ¥} = –1. l3(2) = min{0 + ¥ ; –1 – 8; ¥ + ¥; ¥ – 2; –3 + ¥} = –9 . l4(2) = min{0 + ¥ ; –1 – 7; ¥ + ¥; ¥ + ¥; –3 – 4} = –8 . l5(2) = min{0 – 3; –1 – 1; ¥ + 5; ¥ + ¥; –3 + ¥} = –3. Полученные значения li(2) занесем в третий столбец табл. 3.2. Величины li(2) равны длине минимального пути из первой вершины в i-ую, содержащего не более двух дуг. k = 3. l1(3) = 0. Равенство (3.1) для k = 3 имеет вид: li(3) = {lj(2) + cji}. l2(3) = min{0 – 1; – 1 + ¥; – 9 + ¥; –8 + ¥; – 3 + ¥} = – 1. l3(3) = min{0 + ¥ ; – 1 – 8; – 9 + ¥; –8 – 2; – 3 + ¥} = – 10 . l4(3) = min{0 + ¥ ; – 1 – 7; – 9 + ¥; –8 + ¥; – 3 – 4} = – 8 . l5(3) = min{0 – 3; – 1 – 1; – 9 + 5; –8 + ¥; – 3 + ¥} = – 4. Полученные значения li(3) занесем в четвертый столбец табл. 3.2. Величины li(3) равны длине минимального пути из первой вершины в i-ую, содержащего не более трех дуг. k = 4. l1(4) = 0. Равенство (3.1) для k = 4 имеет вид: li(4) = {lj(3) + cji}. l2(4) = min{0 – 1; – 1 + ¥ ; – 10 + ¥; – 8 + ¥; – 4 + ¥} = – 1. l3(4) = min{0 + ¥ ; – 1 – 8; – 10 + ¥; – 8 – 2; – 4 + ¥} = – 10 . l4(4) = min{0 + ¥ ; – 1 – 7; – 10 + ¥; – 8 + ¥; – 4 – 4} = – 8 . l5(4) = min{0 – 3; – 1 – 1; – 10 + 5; – 8 + ¥; – 4 + ¥} = – 5. Полученные значения li(4) занесем в пятый столбец табл. 3.2. Величины li(4) равны длине минимального пути из первой вершины в i-ую, содержащего не более четырех дуг. Таблица 3.2
Заменив в табл. 3.2 отрицательные числа положительными, получим таблицу индексов максимальных путей (табл. 3.3). При этом li(k) определяет длину максимального пути из первой вершины в i-ую, содержащего не более k дуг. Таблица 3.3
Шаг 5. Восстановление максимального пути производится по тому же правилу, что и для минимального пути. Длина максимального пути равна 10. Этот путь состоит из трех дуг, т. к. li(3) = li(4) = 10. Поэтому в соотношении (3.2) будет выполнено, начиная с n – 1. Учитывая это замечание, для последней вершины x3предшествующую ей вершину xr определим из соотношения (3.2) полученного при s =3: lr(2) + cr3 = l3(3), (3.7) xrÎ G-1(x3), где G-1(x3) - прообраз вершины x3. G-1(x3)= {x2, x4}. Подставим в (3.7) последовательно r = 2 и r = 4, чтобы определить, для какого r это равенство выполняется: l2(2) + c23 = 1 + 8 ¹ l3(4) = 10, l4(2) + c43 = 8 + 2 = l3(4) = 10. Таким образом, вершиной, предшествующей вершине x3, является вершина x4. Для вершины x4предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =4: lr(1) + cr4 = l4(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 это равенство выполняется: l2(1) + c24 = 1 + 7 = l4(3) = 8, l5(1) + c54 = 3 + 4 ¹ l4(3) = 8, Таким образом, вершиной, предшествующей вершине x4, является вершина x2. Для вершины x2предшествующая ей вершина xr определяется из соотношения (3.2) полученного при s =2: lr(0) + cr2 = l2(1), xr G-1(x2), (3.9) где G-1(x2) - прообраз вершины x2. G-1(x2)= {x1}. Подставим в (3.9) r = 1, чтобы определить, выполняется ли это равенство: l1(1) + c12 = 0 + 1 = l2(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 называется цикломатическим числомграфа.
|
|||||||||
Последнее изменение этой страницы: 2016-08-28 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |