Потоки в сетях Теорема о максимальном потоке и минимальном разрезе Лекция 6. - презентация

1 Потоки в сетях Теорема о максимальном потоке и минимальном разрезе Лекция 6

2 Сеть Ориентированный граф G с пропускными способностями дуг u: E(G) R + и две выделенные вершины s (источник) и t (сток). Четверка (G, u, s, t) называется сетью. Главная задача транспортировать так много единиц продукта, как возможно, одновременно из s в t. Решение этой задачи назовем максимальным потоком.

3 Поток Определение 6.1. Дан орграф G с пропускными способностями (вместимостями) u: E(G) R +, потоком называется функция f : E(G) R + с f(e) u(e) для всех e E(G). Будем говорить, что f удовлетворяет закону сохранения в вершине v, если Поток, удовлетворяющий закону сохранения в каждой вершине называется циркуляцией.

4 s-t-Поток Дана сеть (G, u, s, t), s-t-потоком называется поток, удовлетворяющий закону сохранения во всех вершинах кроме s и t. Определим величину s-t-потока функцией

5 Задача «Максимальный Поток» Дано: Сеть (G, u, s, t). Найти s-t-поток максимальной величины.

6 s-t-Разрез s-t-разрез в графе разрез X для некоторого X V(G) с s X и t V(G)\ X. пропускной способностью s-t-разреза называется сумма вместимостей его дуг (ребер). Под минимальным s-t-разрезом в (G,u,s,t) мы понимаем s-t-разрез с минимальной пропускной способностью (относительно u) в G.

7 s-t-Поток и s-t-разрез Лемма 6.2 Для всех A V(G) таких, что s A, t A, и любого s-t-потока f. Величина максимального потока не превосходит пропускной способности минимального разреза.

8 Доказательство (а)

9 s-t-Поток и s-t-разрез Лемма 6.2 Для всех A V(G) таких, что s A, t A, и любого s-t-потока f.

10 Обратные дуги и остаточные пропускные способности Определение 6.3 Для орграфа G определим Ğ:=(V(G), E(G) U {ĕ: e E(G)}), где для каждого e = (v,w) E(G) определим ĕ как новое ребро из w в v. Назовем ĕ обратной дугой к e и, наоборот. Заметим, что если e = (v,w), e = (w,v), то ĕ и e два параллельных ребра в Ğ. Дан орграф G с вместимостями u: E(G) R + и поток f, определим остаточные пропускные способности u f : E(Ğ) R + как u f (e):= u(e) f (e) и u f (ĕ) := f (e) для всех e E(G). Остаточным графом G f называется граф (V(G), {e E(Ğ): u f (e) > 0}).

11 Остаточный граф S t S t G GfGf

12 Увеличивающий Путь Даны поток f и путь (или цикл) P в G f, увеличение f вдоль P на γ означает следующее для каждой e E(P): если e E(G), то увеличим f(e) на γ, если e = ĕ 0, e 0 E(G), то уменьшим f(e 0 ) на γ. Дана сеть (G, u, s, t) и s-t-поток f, f–увеличивающим путем называется s-t-путь в остаточном графе G f.

13 Увеличивающий Путь S t S t G GfGf S t

14 Алгоритм Форда-Фалкерсона Input: Сеть (G, u, s, t). Output: s-t-поток f максимальной величины. 1.Положим f(e) = 0 для всех e E(G). 2.Найти f-увеличивающий путь P. If такого пути нет then stop. 3.Вычислить Увеличить f вдоль P на γ и go to 2.

15 Замечание Найти увеличивающий путь легко (любой s-t-путь в G f ). Если выбирать произвольный увеличивающий путь в G f, то –Существует пример с иррациональными вместимостями дуг, когда алгоритм никогда не остановится. –Существует пример с целыми вместимостями дуг, на котором алгоритм производит экспоненциальное от размера входа число увеличений.

16 Пример c бесконечным числом итераций (все линии представляют ребра, то есть поток может идти в оба направления) S t u(x 1, y 1 )=1, u(x 2, y 2 )=σ, u(x 3, y 3 )= u(x 4, y 4 )= σ 2 x1x1 y1y1 x2x2 x3x3 x4x4 y2y2 y3y3 y4y4 Пропускная способность остальных ребер 1/(1- σ).

17 Упражнение 6.1 Показать, что для сети из предыдущего примера алгоритм Форда-Фалкерсона может работать бесконечно долго.

18 Целочисленный пример c экспоненциальным числом итераций S t R R R R 1 2R итераций. Длина входа O(log R).

19 Характеризация максимального потока Теорема 6.4 s-t-Поток f является максимальным тогда и только тогда, когда в G f не существует f-увеличивающего пути.

20 Доказательство Пусть в G f не существует f-увеличивающего пути. t не достижимо в G f из s. Пусть R множество вершин, достижимых из s в G f. По определению G f имеем f(e) = u(e) для всех e + (R), и f(e) = 0 для всех e – (R). Лемма 6.2 a) Лемма 6.2 b) f максимальный поток.

21 Замечание В частности, из доказательства следует, что каждому максимальному потоку соответствует s-t-разрез, пропускная способность которого равна величине потока. Вместе с леммой 6.2 b) это влечет центральный результат теории потоков в сети.

22 Максимальный поток и минимальный разрез Теорема 6.5 (Форд, Фалкерсон [1956], Элиас, Файнштайн, Шэннон [1956] ) Величина максимального s-t-потока равна пропускной способности минимального s-t-разреза.

23 Теорема о целочисленном потоке Следствие 6.6 Если пропускные способности дуг в сети целые числа, то существует целочисленный максимальный поток.

24 Упражнение 6.2 Поcтроить пример сети, в которой вместимости дуг целые числа, и существует нецелочисленный максимальный поток.

25 Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) сеть и f s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P U C R + таких, что f(e) = Σ P P U C: e E(P) w(P) для всех e E(G), Σ P P w(P) = value( f ), и | P | + | C | | E(G)|. Более того, если f целочисленный поток, то w может быть выбрано целочисленным.

26 Доказательство Построим P, C и w индукцией по числу дуг с ненулевым потоком. Пусть e=(v 0,w 0 ) дуга с f(e) > 0. Если w 0 t, то должна быть дуга (w 0,w 1 ) c ненулевым потоком. Положим i = 1. Если w 0 {t,v 0,w 0,…, w i–1 }, то STOP. Иначе i = i +1 и продолжаем. Если процесс завершится в t, то проделаем тоже самое в обратном направлении, стартуя с v 0.

27 Иллюстрация доказательства t s v0v0 w0w0 w1w1 w2w2 w3w3 t s v0v0 w0w0 w1w1 w2w2 w3w3 v1v1 v2v2

28 Доказательство Пусть P будет цикл или путь, найденный в результате описанной процедуры. w(P) = min e E(P) f(e) Положим f '(e) = f(e) – w(P) для e E(P) и f '(e) = f(e) для e E(P). По крайней мере, одна дуга обнулилась и добавился ровно один путь или цикл. Величина потока вдоль дуг из P уменьшилась на величину w(P). Если P цикл, то величина s-t-потока не изменилась. Если P путь, то величина s-t-потока уменьшилась на w(P).

29 Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) сеть и f s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P U C R + таких, что f(e) = Σ P P U C: e E(P) w(P) для всех e E(G), Σ P P w(P) = value( f ), и | P | + | C | | E(G)|. Более того, если f целочисленный поток, то w может быть выбрано целочисленным.

30 Упражнение 6.2 Доказать следующую теорему Теорема (Хоффман 1960) Задан орграф G и нижние и верхние оценки на пропускные способности дуг l, u: E(G) R + c l(e) u(e) для всех e E(G). В орграфе G существует циркуляция f с l(e) f(e) u(e) для всех e E(G) тогда и только тогда, когда