Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
Задача 6.1. Как изменить алгоритм Уоршолла-Флойда, чтобы находить не только длины кратчайших путей, но и сами кратчайшие пути? Задача 6.2. Пусть A G матрица смежности графа G = (V, E), рассматриваемая над кольцом целых чисел. Пусть A k G = (a (k) ij ) ее (целочисленная) k-ая степень. Докажите, что a (k) ij это число различных путей длины k изв Задача 6.3. Пусть p это кратчайший путь между вершинами u ив нагруженном ориентированном графе G = (V, E). Останется ли этот путь кратчайшим, если увеличить длину каждого ребра на константу c? Докажите это утверждение или опровергните с помощью контрпримера. Задача 6.4. Предложите алгоритм, который в ориентированном нагруженном графе G = (V, с неотрицательными весами ребер находит цикл минимальной длины. Задача 6.5. Диаметр, радиусы и центры графа Диаметром (неориентированного графа) с весами ребер c : E ? R + назывется максимальное расстояние между вершинами графа d G = max{?(u, v)|u, v ? V Внутренний центр ориентированного графа G это такая вершина v 0 , для которой величина R(v 0 ) = max{?(v 0 , v) | v ? V } минимальна. Внешний центр ориентированного графа G это такая вершина u 0 , для которой величина r(u 0 ) = max{?(v, u 0 ) | v ? V минимальна. R G = и r G = называются внутренними внешним радиусами графа G, соответственно. Заметим, что внутренний и внешний центры могут быть не единственными. а) Докажите, что в графе G существуют внешний и внутренний центры тогда и только тогда, когда G является сильно связным. б) Приведите пример графа G, у которого R G 6= в) Предложите эффективный алгоритм опеределения диаметра d G , радиусов R G , и центров графа G. ( Указание используйте алгоритм Уоршолла-Флойда. Задача 6.6. Где в доказательстве правильности алгоритма Дейкстры используется неотри- цательность весов ребер Приведите пример графа (с отрицательными весами, для которого алгоритм Дейкстры дает неверный ответ. Задача 6.7. Докажите, что на каждом шаге алгоритма Дейкстры кратчайший путь из исходной вершины в любую вершину множества S проходит только через вершины множества Задача 6.8. Сколько раз может меняться для одной вершины v значение D[v] входе работы алгоритма Дейкстры для графа с n вершинами. Привести примерна каждый возможный случай. Задача 6.9. Заменим в строке 10 алгоритма Дейкстры знак неравества на противоположный, Будет ли такой модифицированный алгоритм находить самые длинные простые пути из заданной вершины a ? V ? Докажите это утверждение или приведите контрпример. Задача 6.10. Быстрейшая поездка. Содержательно, задача состоит в том, чтобы по железнодорожному расписанию определить самый быстрый способ добраться из одного пункта в другой. Более формально, задан ориентированный граф G = (V, E), вершины которого представляют станции, а ребра соединяют станции, между которыми ходят поезда. Для каждого ребра (u, v) задано расписание поездов R(u, v) на ветке (u, v), представляющее последовательность троек (n 1 , t u 1 , t v 1 ), . . . , (n r , t u r , t v r ) , в которых n i номер поезда, t u i время его отправления со станции u, t v i время его прибытия на станцию а) Предложите алгоритм, который по станции отправления a ? V , конечной станции b ? и времени появления пассажира на станции a находит расписание самой быстрой поездки этого пассажира изв. (Будем считать, что пересадка времени не занимает). б) Предположим, что для каждой станции u ? V задано время T u , требующееся для пересадки на этой станции. Как найти самый быстрый путь в этом случае? Указание: модифицируйте алгоритм Дейкстры. Задача 6.11. Обобщенное неравенство треугольника. Нагруженный ориентированный граф G = (V, E), c : E ? R удовлетворяет обобщенному неравенству треугольника, если для любой пары вершин u и v и любых двух путей p и q между ними из того, что число ребер вне больше числа ребер в q следует, что c(p) ? c(q) (те. самый короткий путь имеет минимальное число ребер). (а) Предложите алгоритм полиномиальной сложности, проверяющий удовлетворяет ли данный граф обобщенному неравенству треугольника. (б) Покажите, что для нагруженных графов G = (V, E), c : E ? R, удовлетворяющих обобщенному неравенству треугольника, для задачи поиска кратчайших путей из одного источника имеется алгоритм сложности O(|V | + Задача 6.12. Алгоритм Беллмана-Форда позволяет обнаруживать циклы отрицательной длины. Предложите алгоритм, печатающий вершины какого-нибудь такого цикла. Задача 6.13. G = (V, E) - ориентированный граф без циклов отрицательной длины. c - весовая функция на ребрах (ребра могут быть отрицательной длины. Построить алгоритм, который для каждой вершины v ? V находит расстояние до ближайшего соседа) = min u6=v ?(u, Задача 6.14. Валютные операции Пусть на рынке имеется n валют, текущие курсы которых заданы Ч матрицей R: единица ой валюты обменивается на R[i, j] единиц ой валюты. Разработайте алгоритм, который находит такую последовательность валют (цикл) i 1 , i 2 , . . . , i k , i 1 , для которой R[i 1 , i 2 ] · R[i 2 , i 3 ] · . . . · R[i k , i 1 ] > 1 . Оцените время работы этого алгоритма. Задача 6.15. Вложенные ящики. Скажем, что мерный ящик размера (x 1 , x 2 , . . . , x вкладывается в ящик размера (y 1 , y 2 , . . . , y d ) , если существует такая перестановка i 1 , i 2 , . . . , i измерений 1, 2, . . . , d, для которой x i 1 ? y 1 , x i 2 ? y 2 , . . . , x i d ? y d a) Докажите, что отношение "вкладывается в" транзитивно. б) Предложите алгоритм проверки этого отношения. в) Пусть дано n мерных ящиков. Предложите алгоритм для определения самой большой подпоследовательности вложенных ящиков (матрешки из максимально возможного числа ящиков. Оцените его сложность. Системы ограничений на разности. Система ограничений на разности это система неравенств вида i ? x j ? b k 1 ? i, j ? n, 1 ? k ? m ( здесь x i , x j переменные, b k константы ). Свяжем с этой системой графу которого V ? = {v 0 , v 1 , . . . , v n } , E ? = {(v 0 , v i ) | 1 ? i ? n} ? {(v , v j ) неравенство x i ? x j ? b входит в систему (Зададим веса ребер следующим образом, v i ) = 0 (1 ? i ? n) , c(v i , v j ) = b k , если x i ? x j ? b входит в систему (Задача 6.16. Докажите следующее утверждение. Теорема а) Если в графе нет циклов отрицательной длины, то x 1 = ?(v 0 , v 1 ), x 2 = ?(v 0 , v 2 ), . . . , x n = ?(v 0 , v является решением системы (б) Если в графе есть циклы отрицательной длины, то система (*) не имеет решений. Задача 6.17. Используя предыдущую задачу, предложите алгоритм, для проверки разрешимости систем вида (*) и нахождения их решений. 7 Потоки в сетях Потоки и разрезы. Алгоритм Форда-Фалкерсона Понятие (транспортной) сети служит для моделирования задач, связанных с поиском оптимальных планов перемещения или перевозки продуктов от источников (производителей) к их потребителям. Транспортные сети представляются ориентированными графами с нагруженными дугами 2 Определение 22. Сеть N = (V, E, s, t, c) - это связный ориентированный граф без петель = (V, у которого) имеется одна вершина s, в которую не входят дуги (источник) имеется одна вершина t, из которой не исходят дуги (сток) каждой дуге e = (u, v) ? E сопоставлена ее пропускная способность c(e) ? Содержательно, пропускная способность дуги это максимальный объем продукта, который можно переместить по этой дуге, или максимальная скорость его перевозки. План перевозки задается с помощью потока функции, которая определяет объем (скорость) перемещения продукта по каждой дуге. Значение потока на дуге не должно превышать ее пропускной способности и для каждой вершины поток, который в нее втекает, должен совпадать с потоком, который из нее вытекает (закон Киркгофа). Такой поток может описывать- поведение газа или нефти в трубопроводе, потоки автомобильных грузов в сети автострад, пересылку товаров по железной дороге, передачу информации в информационной сети и т.п. 2 В транспортных сетях, как правило, вместо термина ребро используется его синоним дуга Определение 23. Поток f в сети N - это функция f : E ? R такая, что) 0 ? f(e) ? c(e) для каждой дуги e ? E; 2) для каждой вершины v ? V \ {s, t} P{f (e)| e входит в v} = P{f(e)| e выходит из Величина потока f в сети N val(f) = P u?V f (s, Поток с наибольшим значением величины называется максимальным. Следствие. Величина потока val(f) = P u?V f (u, t). (Показать!) Определение 24. Разрез A в сети N - подмножество вершин A такое, что источника сток t ? V \ A. Разрез (и вообще любое подмножество вершин сети) A однозначно задает множество дуг P (A) = {(u, v) | u ? A, v ? V \ A}, ведущих из A "наружу". Пропускная способность разреза A : c(A, V \ A) = P (u,v)?P (A) c(u, Разрез с минимальной пропускной способностью называется минимальным. Поток f через разрез (множество) A: f (A, V \ A) = P (u,v)?P (A) f (u, v) Величина потока связана сего прохождением через разрез. Лемма 7.1. Для произвольного разреза A и любого потока f val(f ) = f (A, V \ A) ? f (V \ A, Доказательство. Из определения потока следует, что (u, v) ? X v?V f (v, u) = val(f если u = если u ? A \ Просуммировав эти равенства по всем u ? A, получим (u, v) ? X u?A X v?V f (v, u) = val(f Для любой пары вершин u ? A, v ? A поток f(u, v) учитывается впервой сумме в левой части с плюсом, а во второй сумме с минусом. Сократив все такие слагаемые, получим \A f (u, v) ? X u?A X v?V \A f (v, u) = val(f или f(A, V \ A) ? f(V \ A, A) = Теорема 7.1 (Форд, Фалкерсон)). (1) Величина любого потока извне превосходит пропускной способности минимального разреза) Существует поток, достигающий этого значения (максимальный поток). Доказательство. (1) Пусть A минимальный разрез. По лемме 7.1 для любого потока f имеем val(f ) = f (A, V \ A) ? f (V \ A, A) ? f (A, V \ A) = ? e?P (A) f (e) ? ? e?P (A) c(e) = c(A, V \ Пример 16. Рассмотрим сеть N и поток f в ней, показанные на рис. 27. Пропускные способности дуг указаны в скобках, а значения потока на этих дугах без скобок. Величина этого потока val(f) = f(s, a) + f(s, b) + f(s, c) = 3 + 6 + 4 = 13. Один из разрезов в сети образует множество вершин A = {s, a, b, c}. Для него P (A) = {(a, f), (b, f), (b, g), (b, e), (c, e)}, P (V \ A) = {(e, a)} , пропускная способность этого разреза c(A, V \ A) = 6 + 3 + 2 + 2 + 5 = поток через A равен f(A, V \ A) = 5 + 2 + 2 + 2 + 4 = 15, а поток в обратном направлении f (V \ A, A) = 2. 57 - 1 P P P P P q - - - - 1 @ @ @ @ @ I P P P P P q 1 P P P P P q s b a c f e g t (6) 5 (5) 4 (2) 2 (3) 2 (2) 2 (4) 2 (8) 7 (2) 2 (6) 4 (8) 6 (6) 3 (6) Рис. 27: Сеть N (пропускные способности в скобках) и поток Основные алгоритмы построения максимального потока основываются на последовательном увеличении потока, причем модификация потока, производится вдоль увеличивающих путей (цепей, определенных Фордом и Фалкерсоном. Определение 25. Пусть N - сеть, f - поток в ней. Увеличивающий путь (увеличивающая цепь) изв относительно f это любой путь P изв в неориентированном графе, полученном из G игнорированием направлений дуг, в котором) для любой дуги (u, v), проходимой в P в прямом направлени (прямой дуги, f(u, v) < c(u, v); 2) для любой дуги (v, u), проходимой в P в обратном направлении (обратной дуги, f(v, u) Увеличивающий путь изв будем просто называть увеличивающим путем. Следующая теорема устанавливает связь между отсутствием увеличивающих путей, максимальностью потока и и совпадением потока через разрез сего пропускной способностью. Теорема 7.2. Следующие условия эквивалентны) поток f изв максимальный) не существует увеличивающего пути для f; 3) для некоторого разреза A val(f) = c(A, V \ Доказательство. (1) =? (2) следует из определения увеличивающего пути. Действительно, предположим, что в сети есть увеличивающий путь p = (s = v 0 e 1 ? v 1 e 2 ? . . . , v l?1 e l ? v l = Положим ?(e i ) = c(e i ) ? f (e если дуга e прямая, и ?(e i ) = f (e если e i обратная дуга. Пусть ? = min{?(e i )|1 ? i ? l} . Тогда ? > 0. Определим новый поток f 0 , который совпадает с f всюду кроме p, а на дугах из p положим f 0 (e i ) = f (e i )+? , если дуга e прямая, и f 0 (e i ) = f (e если дуга e обратная. Нетрудно проверить, что является потоком и что val(f 0 ) = val(f ) + ? (2) =? (3). Положим A = {v ? V существует увеличивающий путь изв. Тогда A разрез (почему?). Для каждой дуги e = (v, u) ? P (A) имеет место f(e) = c(e) (иначе можно было бы продолжить увеличивающий путь до u). По той же причине для каждой дуги e ? P (V \ A) f (e) = 0 . Тогда по лемме 7.1 получаем, что val(f) = f(A, V \ A) ? f(V \ A, A) = c(A, V \ A). (3) =? (1) следует по теореме Определенная в доказательстве этой теоремы для увеличивающего пути p величина ? = определяет максимальное возможное увеличение потока на этом пути. Пример 17. В сети N рис. 27 увеличивающими относительно указанного потока f будут следующие пути с соответствующими значениями ?: p 1 = (s (6)3 ?? a (6)5 ?? b (8)7 ??= t) , ?(p 1 ) = 1; p 2 = (s (6)3 ?? a (4)2 ?? e (6)4 ??= t) , ?(p 2 ) = 2; 58 p 3 = (s (8)6 ?? b (3)2 ?? f (8)7 ??= t) , ?(p 3 ) = 1; p 4 = (s (6)4 ?? c (5)4 ?? e (6)4 ??= t) , ?(p 4 ) = 1; p 5 = (s (6)4 ?? c (5,)4 ?? e (4)2 ?? a (6)5 ?? b (8)7 ??= t) , ?(p 5 ) = Из теоремы 7.2 можно извлечь идею следующего простого алгоритма построения максимального потока. Начиная с нулевого потока (f(e) = 0 для каждой дуги e ? E), ищем увеличивающие пути и увеличиваем вдоль них текущий поток. Завершаем вычисление, когда обнаруживаем отсутствие увеличивающих путей. Этот алгоритм был предложен в работе Форда и Фалкерсона в 1962г. АЛГОРИТМ ФОРДА И ФАЛКЕРСОНА (Ф-Ф) Вход: сеть N = (V, E, s, t, Выход максимальный поток f в Структуры данных- предшественник v в увеличивающем пути- величина дополнительного потока изв очередь вершин. В качестве имен вершин используются их номера (положительные целые числа Инициализация: 1 готово = "нет ALL e ? E DO f(e) := 0 ; % Основной цикл готово="нет" DO 4 { FOR ALL v ? V \ {s} DO { L(v) := 0; ?(v) := 0 }; 5 L(s) := s; ?(s) := ДОБАВИТЬ, s); 7 WHILE Q 6= ? DO 8 {v := НАЧАЛО(Q); 9 УДАЛИТЬ(Q); 10 ПРОСМОТРЕТЬ(v) 11 }; 12 IF L(t) 6= 0 % t помечена, есть увел. путь увеличить поток f вдоль увеличивающего пути {v := t; 14 WHILE v 6= s DO 15 {u := L(v); 16 IF u > 0 17 THEN f(u, v) := f(u, v) + ?(t) % прямая дуга f(v, u) := f(v, u) ? ?(t); % обратная дуга := |u| } 20 } 21 ELSE готово="да" 22 } Процедура ПРОСМОТРЕТЬ) пытается продлить увеличивающий путь изв, проверяя сначала все дуги, выходящие из v, а затем дуги, входящие в v. PROCEDURE ПРОСМОТРЕТЬ(v) Поиск прямых увеличивающих дуг ALL (v, u) ? E DO 2 IF L(u) = 0 AND f(v.u) < c(v, u), 3 THEN % продлить увел. путь до u: 4 { L(u) := v; ?(u) := min{?(v), c(v, u) ? f (v, ДОБАВИТЬ, Поиск обратных увеличивающих дуг ALL (u, v) ? E DO 8 IF L(u) = 0 AND f(u, v) > 0, 9 THEN % продлить увел. путь до u: 10 { L(u) := ?v; ?(u) := min{?(v), f (u, ДОБАВИТЬ, Теорема 7.3. Если алгоритм Ф-Ф останавливается, то полученный поток максимален. Доказательство. Действительно, в момент остановки алгоритма Ф-Ф очередь Q пуста и) = Положим W = {v | L(v) 6= 0} . Тогда W разрез. Для любой дуги (v, u) ? P (W ) f ((u, v) = c((u, иначе при вызове ПРОСМОТРЕТЬ) в цикле 1-6) для u были бы выполнены все условия и эта вершина была бы "помечена L(u) := v. Для любой же обратной дуги (u, v) ? P (V \ W ) f((u, v) = 0 (иначе при вызове ПРОСМОТРЕТЬ) в цикле 7-12) для были бы выполнены все условия и эта вершина была бы "помечена L(u) := ?v). Но тогда по лемме 1 имеем val(f) = f(W, V \ W ) ? f(V \ W, W ) = c(W, V \ W и по теореме 2 f максимальный поток. Следующий пример показывает, что сложность алгоритма Ф-Ф может зависеть от значений пропускных способностей дуг. Пример 18. Рассмотрим следующую сеть i 6 (1) @ @ @ @ @ R t Рис. 28: Сеть с большим временем работы алгоритма Ф-Ф 60 Предположим, что алгоритм Ф-Ф, начав с нулевого потока, поочередно находит и использует для увеличения потока увеличивающие пути p 1 = s ? y ? x ? t и p 2 = s ? x ? y ? Тогда на каждом этапе алгоритма поток увеличивается на 1 и максимальный поток достигается за 2M этапов. ЗАМЕЧАНИЕ. Форд и Фалкерсон показали, что их алгоритм может не найти максимального значения потока. Они построили примеры сетей с иррациональными значениями c(v, на которых алгоритм не останавливается и сходится кот величины максимального потока. Причина этого в том, что в алгоритме Ф-Ф не учитывается порядок перебора увеличивающих путей. Эдмондс и Карп в 1972 г. предложили модификацию алгоритма Ф-Ф, в которой на каждом этапе поток увеличивается вдоль кратчайшего (по числу дуг) увеличивающего пути. Их алгоритм в худшем случае имеет сложность O(|V ||E| 2 ) , что при большом количестве дуг = O(|V дает оценку O(|V | 5 ) 7.2 Алгоритм построения максимального потока за кубическое время В этом разделе мы приведем более эффективный алгоритм сложности O(|V | 3 ) , первоначальная идея которого принадлежала Е.А. Диницу (1970), а затем была уточнена А.В. Карзановым (1974). Вариант этого алгоритма, представленный здесь, является упрощенной формой этого алгоритма, описанной в работе трех авторов Малхортры (Malhotra V. M.), Кумара (Kumar M.P.) и Махешвари (Maheshwari S.N.) в г. Его идея состоит в том, чтобы на каждом этапе производить увеличение потока по всем кратчайшим увеличивающим путям. Определение 26. Пусть N = (V, E, s, t, c) сеть, f поток в N. Вспомогательная сеть (f ) = (V (f ), E(f ), s, t, ac) это такая сеть, вершины которой V (f) разбиты на l слоев {s}, V 1 , ..., t ? так что дуги соединяют вершины соседних слоев V i и и при этом, если t /? V i , то слой и входящие в него дуги определяются следующим образом) если (u, v) ? E, u ? V i , v / ? S i j=0 V j и f(u, v) < c(u, v), то v ? V i+1 , (u, v) ? E(f и ac(u, v) = c(u, v) ? f (u, v); 2) если (v, u) ? E, u ? V i , v / ? S i j=0 V j и f(v, u) > 0, то v ? V i+1 , (u, v) ? E(f и ac(u, v) = f (v, Вообще говоря, возможен и третий случай, когда поток f больше нуля на двух встречных дугах f(u, v) > 0 и f(v, u) > 0. В этом случае можно провести эквивалентное преобразование минимальный из этих потоков заменить на 0, а максимальный из них назначение потока (u, v) ? f (v, Алгоритм ПОВС построения вспомогательной сети основан на поиске в ширину. Пусть) = {u | (v, u) ? E} список "сыновей, M(v) = {u | (u, v) ? E} список "отцов в аи аналогичные списки для AN(f), AV вершины AN(f), ДЛИНА- расстояние от s до v, Q очередь вершин (вначале пустая ПОВС % Инициализация ALL u ? V ДЛИНА) := ?; 3 AM (u) := ?; AL(u) := ?; 4 FOR ALL v ? V DO ac(u, v) := 0; 5 FOR ALL v ? V DO af(u, v) := 0 6 } ; 61 ДОБАВИТЬ, s); AV := ?; ДЛИНА) := 0; % поиск в ширину от s: 8 WHILE Q 6= ? DO 9 { u НАЧАЛО УДАЛИТЬ AV := AV ? {u}; 10 FOR ALL v ? L(u) DO % поиск прямых дуг (ДЛИНА) < ДЛИНА) ? ДЛИНА) AND f(u, v) < c(u, v)) 12 |