Максимальный поток Лекци и 20 – 21. Максимальный поток Рассмотрим ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество. - презентация

1 Максимальный поток Лекци и 20 – 21

2 Максимальный поток Рассмотрим ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество движется от истока к стоку, или как движение тока по проводам, информации по линиям связи или товаров от производителя к потребителю и т.д. Пометки ребер будем рассматривать, напрмер, как ширину дороги, или пропускную способность трубы. Будем считать, что в вершинах вещество не накапливается сколько приходит, столько и уходит (если вершина не является истоком или стоком). Это свойство называется «законом сохранения потока» (flow conservation). Задача о максимальном потоке для данной сети состоит в следующем: найти максимально возможную скорость производства (и потребления) вещества, при которой его ещё можно доставить от истока к стоку при данных пропускных способностях труб.

3 Определение сети Назовем сетью ориентированный граф G = (V, Е), каждому ребру (и, v) Е которого поставлено в соответствие число с(и, v) 0, называемое пропускной способностью ребра. В случае (и, v) Е полагаем с(и, v) = 0. В графе выделены две вершины: исток s и сток t. s s t t (а) Сеть 1 с указанием пропускных способностей ребер

4 Определение потока Пусть дана сеть G = (V,E), пропускная способность которой задаётся функцией с. Сеть имеет исток s и сток t. Потоком в сети G назовём функцию f : V X V > R, удовлетворяющую трём свойствам: 1) Ограничение, связанное с пропускной способностью: f(u, v) c(u, v) для всех и, v из V. Поток из одной вершины в другую не превышает пропускной способности ребра. 2) Кососимметричность: f(u,v) = f(v,u) для всех и, v из V. Величина f(u,v) может быть как положительной, так и отрицательной, отрицательные значения соответствуют движению в обратную сторону. f(и, и) = 0 для любой вершины и. 3) Сохранение потока: v V f(u,v) = 0 для всех и {V – {s, t}}. Для любой вершины и (кроме стока и истока) сумма потоков во все другие вершины равна нулю.

5 Величина потока Величина потока f определяется как сумма v V f(s,v) и обозначается как |f|. Cкладываем потоки по всем рёбрам, выходящим из истока. Учитывая кососимметричность, свойство 3) можно переписать как u V f(u,v) = 0, т.е. сумма всех потоков из других вершин равна нулю. Задача о максимальном потоке состоит в следующем: для данной сети G с истоком s и стоком t найти поток максимальной величины.

6 Поток в сети 1 величины 19 s s t t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 (б) Поток величины 19 На ребрах указана величина потока f(и, v); если f(и, v) = 0, поток не указывается.

7 Заметим также, что если вершины и и v не соединены ребром, то поток между ними равен нулю. Действительно, если (и, v) Е и (v, и) Е, то с(и, v) = c(v, и) = 0. Тогда из первого свойства следует, что f(u,v) 0 и f(v,u) 0. Вспоминая, что f(u,v) = f(v,u) получим: f(u,v) = f(v,u) = 0. Разделим вещество, поступающее в данную вершину v и вещество, из неё выходящее, то есть положительные и отрицательные значения f(u,v). Сумму u V f(u,v) назовём входящим (в вершину v) потоком. f(u,v)>0 Аналогично определим выходящий поток. Тогда свойство 3): для любой вершины, кроме истока и стока, входящий поток равен исходящему.

8 Пример Компания производит изделия на фабрике в городе A (исток s) и складирует их в городе B (сток t). Она арендует место в грузовиках другой фирмы, и место это ограничено: из города и в город v можно доставить не более с(и, v) ящиков в день. Ограничения с(и,v) показаны на рисунке. Задача состоит в том, чтобы перевозить максимально возможное количество изделий из г. A в г. В ежедневно. При этом путь может занимать несколько дней, и ящики могут ждать отправки в промежуточных пунктах, но необходимо, чтобы для каждого пункта число ежедневно прибывающих ящиков было равно числу увозимых, иначе ящиков нехватит или они будут накапливаться. Тем самым выполнено свойство сохранения потока. Величиной потока будет число изделий, ежедневно отгружаемых из г. А, и нас интересует поток максимальной величины.

9 s s t t (а) На каждом ребре написано максимальное число ящиков, которые можно отправить в день. s s t t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 (б) Пример потока f величины 19. Показаны только положительные значения f(u, v) > 0, после косой черты стоит пропускная способность c(u,v). П ример

10 Модель не учитывает встречные перевозки. Если из вершины v 1 в v 2 ежедневно везут восемь ящиков, а из v 2 в v 1 ежедневно везут три ящика, чему должны быть равны f(v 1,v 2 ) и f(v 2,v 1 )? Эти величины должны быть противоположны. Мы полагаем f(v 1,v 2 ) = 8 3 = 5, a f(v 2,v 1 )= 5. Те же значения функции f соответствуют ежедневным перевозкам пяти ящиков из v 1 в v 2, так что в модели встречные перевозки автоматически сокращаются. Это разумно, экономика должна быть экономной.

11 Пример сокращения потоков между вершинами 10 4 (а) 8/10 4 (б) 8/10 3/4 (в) 5/10 4 (г) 10 2/4 (д) c(v 1, v 2,) = 10; c(v 2, v 1 ) = 4. Сначала из v1 в v2 возили ежедневно 8 ящиков. Затем стали возить 3 ящика в обратном направлении. Потом уменьшили число перевозимых в обратную сторону ящиков на 3. Эти две различные (в жизни) ситуации соответствуют одной и той же функции f, в обоих случаях f(v 1,v 2 ) = 5, a f(v 2, v 1 ) = –5. Если требуется начать перевозки дополнительных 7 ящиков в день из v 2 в v 1, то нужно прежде всего отменить перевозки 5 ящиков в обратную сторону, после чего назначить перевозку дополнительных 2 ящиков.

12 Несколько истоков Задача о максимальном потоке для нескольких истоков и стоков сводится к обычной построением эквивалентной сети с одним истоком и одним стоком. А именно: в сеть добавляется общий исток s, из которого ведут рёбра бесконечной пропускной способности во все прежние истоки. Аналогичным образом из всех прежних стоков проведены рёбра в общий сток t. Добавленные рёбра имеют бесконечную пропускную способность. В примере (след. слад) легко видеть, что каждый поток в сети (а) соответствует потоку в сети (Ь) и наоборот.

13 (а) (б)

14 Обозначения Будем использовать следующее соглашение: если в выражении на месте вершины стоит множество вершин, то имеется в виду сумма по всем элементам этого множества (неявное суммирование). Это относится и к случаю нескольких переменных. Например, если X и Y множества вершин, то f(X,Y) = x X y Y f(x,y) В этих обозначениях закон сохранения потока запишется как f(u,V) = 0 для всех и V – {s,t}. Кроме того, в неявных суммах мы опускаем фигурные скобки.

15 Лемма 1 Пусть f поток в сети G = (V,E). Тогда для любого X V выполнено f(X,X) = 0. Для любых X, Y V выполнено f(X,Y) = – f(Y,X). Для любых X, Y, Z V из X Y = ø следует f(XUY, Z) = f(X, Z) + f(У, Z) и f(Z, XUY) = f(Z, X) + f(Z,Y).

16 Остаточные сети Пусть дана сеть G = (V, Е) с истоком s и стоком t. Пусть f поток в этой сети. Для любой пары вершин и и v определяется остаточная пропускная способность из и в v: c f (u,v) = c(u,v) – f (u,v). Она определяет, сколько ещё потока можно направить из и в v. Например, если c(u,v) = 16, a f(u,v) = 11 то мы можем переслать ещё c f (и, v) = 5 единиц по ребру (и, v). Остаточная пропускная способность c f (и, v) может превосходить с(и, v), если в данный момент поток f(и, v) отрицателен. Например, если с(и, v) = 16, а f(и, v) = 4, то c f (u,v) = 20. Мы можем увеличить поток на 4, отменив встречный поток, и ещё отправить 16 единиц, не превышая пропускной cпособности ребра (и, v). Неформально говоря, остаточная сеть состоит из тех рёбер, поток по которым можно увеличить. –4/16

17 Определение Сеть G f = (V, E f ), где E f = { (u,v) V x V: c f (u, v) > 0 } назовём остаточной сетью сети G, порождённой потоком f. Её рёбра, называемые остаточными рёбрами, допускают положительный поток. Заметим, что остаточное ребро (и,v) не обязано быть ребром сети G, может оказаться, что E f Е. Такое ребро из и в v появляется, когда f(и, v) < 0, то есть когда имеется имеется поток вещества в обратном направлении (по ребру (v, и)) ведь этот поток можно уменьшить. Если ребро (и, v) принадлежит остаточной сети, то хотя бы одно из рёбер (и, v) и (v, и) было в исходной сети. Получаем оценку E f 2 E.

18 Пример остаточной сети На рис. а) изображен поток f в сети G, на рис. б) – остаточная сеть G f и выделен путь p, по которому можно еще пропустить 4 единицы. Рёбер (v 1, s) и (v 2,v 3 ) не было в исходной сети. c(v 1, v 2 ) = 10; c(v 2, v 1 ) = 4; f(v 2, v 1 ) = 1; c f (v 2, v 1 )= 4 – 1= 3; c f (v 1, v 2 ) = 10 – (-1) = 11; c(v 3, v 2 ) = 9; c(v 2, v 3 ) = 0; f(v 3, v 2 ) = 4; c f (v 3, v 2 ) = 9 – 4 = 5; c f (v 2, v 3 ) = 0 – (-4) = 4; s s t t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 (а) s s t t (б)

19 Соотношение потоков сети и остаточной сети Остаточная сеть G f является сетью с пропускными способностями C f. Пусть имеется сеть G = (V, Е) и два потока f 1 и f 2 на ней. Рассмотрим их сумму (функцию из V X V в R): (f 1 + f 2 )(u, v) = f 1 (u, v) + f 2 (u, v) (1) Лемма 2 Пусть G = (V, Е) сеть с истоком s и стоком t, а f поток в ней. Пусть G f остаточная сеть сети G, порождённая потоком f. Пусть f' поток в G f. Тогда сумма f + f ', определенная как в (1), является потоком в сети G величины | f + f '| = | f | + | f '|.

20 Доказательство леммы 2 Сначала докажем, что f + f ' будет потоком. 1) Проверим условие, связанное с ограниченной пропускной способностью. Заметим, что f '(u,v) с f (u,v) для всех и, v V, Поэтому (f + f ')(и, v) = f(u, v) + f '(u, v) f(u, v) + (c(u, v)-f(u, v)) = c(u, v). 2) Кососимметричность. Для всех и, v V выполнено (f + f)(u, v) = f(u,v) + f'(u,v) = -f(v,u) - f'(v,u) = - (f(v,u) + f(v,u)) = - (f + f)(u, v) 3) Закон сохранения потока. Для всех и V \ {s, t} выполнено: (f + f ')(u,V) = f(u,V) + f '(u,V) = f(u,V) + f '(u, V) = = 0. Наконец, найдём величину суммарного потока: | f + f '| = (f + f')(s,V) = f (s,V) + f '(s,V) = |f | + |f '|.

21 Дополняющие пути Пусть f поток в сети G = (V,E). Назовём дополняющим путём простой путь из истока s в сток t в остаточной сети G f. Из определения остаточной сети вытекает, что по всем ребрам (и, v) дополняющего пути можно переслать ещё сколько-то вещества, не превысив пропускную способность ребра. Величину наибольшего потока, который можно переслать по дополняющему пути р, назовём остаточной пропускной способностью пути р: c f = min { c f (u,v): (u,v) p }.

22 Лемма 3 Пусть f поток в сети G = (V, Е) и р дополняющий путь в G f. Определим функцию f p : V X V > R: C f (p), если (и, v) р f p (u,v) = –C f (p), если (v,u) p (1) 0, в остальных случаях. Тогда f p поток в сети G f и |f p | = c f (p) > 0. Если добавить поток f p к потоку f, то получится поток в сети G с большим значением.

23 Следствие 4 Пусть f поток в сети G = (V, Е), а р дополняющий путь в сети G f, заданный равенством (1). Тогда функция f' = f + f p является потоком в сети G величины | f'| = | f | + |f p | > |f|. Доказательство вытекает из лемм 2 и 3.

24 Пример. Добавление потока величины 4 и остаточная сеть s s t t 11/16 12/12 19/20 12/13 11/14 4/4 7/7 10 1/4 9 (в) На рис. в) показана сеть – результат добавления потока величины 4, проходящего вдоль пути p. На рис. г) показана остаточная сеть, порожденная потоком с рис. в). t t s s (б) s s t t (г)

25 Разрезы в сетях Назовём разрезом сети G = (V, Е) разбиение множества V на две части S и T = V\S, для которых s S и t Т. Пропускной способностью разреза (S, T) называют сумму c(S, T) пропускных способностей пересекающих разрез ребер (по всем ребрам из S T). Для заданного потока f величина потока через разрез (S, Т) определяется как сумма f(S, T) по пересекающим разрез ребрам. Минимальным разрезом называют разрез наименьшей пропускной способности среди всех разрезов данной сети.

26 Пример На рис. изображён разрез ({s, v 1, v 2 }, {v 3, v 4, t}). Поток через него равен f(v 1, v 3 ) + f(v 2, v 3 ) + f(v 2, v 4 ) = 12 + (-4) + 11 = 19, Пропускная способность разреза равна с(v 1, v 3 ) + с(v 2, v 4 ) = = 26. Поток через разрез, в отличие от пропускной способности разреза, может включать и отрицательные слагаемые. s s t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 ST

27 Другой разрез На рис. изображён разрез ({s, v 1, v 2, v 4 }, {v 3, t}). Поток через него равен f(v 1, v 3 ) + f(v 2, v 3 ) + f(v 4, v 3 ) + f(v 4, t) = 12 + (-4) = 19, Пропускная способность разреза равна с(v 1, v 3 ) + с(v 4, v 3 ) + с(v 4, t) = = 23. S s s t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 T

28 Лемма 5 Пусть f – поток в сети G, а (S, T) разрез сети G. Поток f (S, T) через разрез равен |f |. Следствие 6 Величина любого потока f в сети G не превосходит пропускной способности любого разреза сети G. Доказательство |f| = f( S, T) = u S y T f(u,v) u S y T c(u,v) = c(S, T)

29 Теорема 7 о максимальном потоке и минимальном разрезе Пусть f поток в сети G = (V, Е). Тогда следующие утверждения равносильны: 1. Поток f максимален (является потоком максимальной величины) в сети G. 2. Остаточная сеть G f не содержит дополняющих путей. 3.Для некоторого разреза (S,T) сети G выполнено равенство | f | = c(S, T). В этом случае разрез является минимальным, то есть имеет минимально возможную пропускную способность.

30 Доказательство (1)=> (2) От противного. Пусть что поток f максимален, но G f содержит дополняющий путь р. Рассмотрим сумму f + f p, где f p задается равенством 1). По следствию 4 эта сумма является потоком в G, величина которого больше |f|, что противоречит максимальности. (2) => (3) Пусть в сети G f нет пути из истока s в сток t. Рассмотрим множество S = { v V: в G f существует путь из s в v}. Положим Т = V\S. Очевидно, что s S, a t Т, так как в G f нет пути из s в t. Поэтому пара (S,T) разрез. Ни для каких и S и v Т ребро (и, v) не принадлежит E f (в противном случае вершина v попала бы в S). Поэтому f(u, v) = с(и, v). По лемме 5 |f | = f(S,T) = c(S,T). (3) => (1) Для любого разреза (S,T) верно |f| c(S,T) (следствие 6). Поэтому из равенства |f| = c(S,T) следует, что поток f максимален.

31 Метод Форда-Фалкерсона Поиск максимального потока проводится последовательно. Вначале поток нулевой. На каждом шаге мы увеличиваем значение потока. Для этого мы находим дополняющий путь, по которому можно пропустить ещё немного вещества, и используем его для увеличения потока. Этот шаг повторяется, пока есть дополняющие пути. Полученный поток будет максимальным. Ford-Fulkerson-Method(G, s, t) { положить поток f равным 0; while ( существует дополняющий путь ) дополнить f вдоль p; return f; }

32 Алгоритм На каждом шаге вибираем произвольный дополняющий путь р и увеличиваем поток f, добавляя поток величины c f (p) по пути р. В массиве f [и, v] хранятся текущие значения потока. Ford-Fulkerson(G,s,t) for(для каждого ребра (u,v) ) { f[u,v] = 0; f[v,u]= 0; } while( в G f существует путь р из s в t){ c f (p) min{c f (u,v):(u,v)входит в p} for(для каждого ребра(u,v)пути р){ f[u,v]=f[u,v]+c f (p); f[v,u]= -f[u,v]; } } }

33 Анализ Время работы процедуры Ford-Fulkerson зависит от того, как ищется путь р. Если выбирать дополняющий путь при помощи поиска в ширину, то алгоритм работает полиномиальное время. Рассмотрий случай, когда пропускные способности – целые числа. Инициализация требует O(E). Цикл while выполняется не более |f*| раз, где f* - максимальный поток. Поиск дополняющего пути в остаточной сети займет время О(Е). Поэтому время работы процедуры будет O(E |f*|). Если использовать поиск в ширину, то путь р будет кратчайшим из дополняющих путей (длину каждого ребра считаем равной 1) Эта реализация метода Форда-Фалкерсона называется алгоритмом Эдмондса-Карпа. Время работы алгоритма Эдмондса-Карпа равно O(VE 2 ).

34 s s t t s s t t 4/16 4/ /14 4/ /9 (а) Пример Остаточная сеть и дополняющий путь Увеличенный поток f p = 4 s s t t s s t t 11/16 4/1 2 7/ /14 4/4 7/7 7/10 4 4/9 (б) f p = 4 + 7= 11

35 (б) s s t t 11/16 4/12 7/ /14 4/4 7/7 7/10 4 4/9 s s t t Остаточная сеть и дополняющий путь Увеличенный поток s s t t 11/16 12/12 15/20 8/13 11/14 4/4 7/7 10 1/4 4/9 (в) f p = = 19 s s t t

36 Остаточная сеть и дополняющий путь s s t t 11/16 4/12 7/ /14 4/4 7/7 7/10 4 4/9 Увеличенный поток (в) s s t t s s t t 11/16 12/12 19/20 12/13 11/14 4/4 7/7 10 1/4 9 (г) f p = = 23 s s t t

37 s s t t 11/16 12/12 19/20 12/13 11/14 4/4 7/7 10 1/4 9 Увеличенный поток (г) (д) Остаточная сеть s s t t Минимальный разрез: отсекается та часть вершин, до которых есть путь из s.

38 Задача о максимальном паросочетании в двудольном графе Пусть G = (V, Е) неориентированный граф. Паросочетанием назовем множество рёбер М Е, не имеющих общих концов (каждая вершина v V является концом максимум одного ребра из М). Будем говорить, что вершина v V входит в паросочетание М, если в М есть ребро с концом v; в противном случае v свободна. Максимальное паросочетание это паросочетание М, содержащее максимально возможное число рёбер (|М| |М'| для любого паросочетания М').

39 Двудольный граф Рассмотрим паросочетания в двудольных графах. Множество V разбито на два непересекающихся подмножества L и R, и любое ребро из Е соединяет некоторую вершину из L с некоторой вершиной из R. Например, L женихи, R невесты, наличие ребра (и, v) означает, что и и v согласны стать супругами. Максимальное паросочетание доставляет ЗАГСу больше всего работы.

40 Пример LR L R (a)(b) Множество вершин разбито на две части L и R. (а) Паросочетание из двух рёбер. (b) Максимальное паросочетание состоит из трёх ребер.

41 Поиск максимального паросочетания Будем использовать метод Форда-Фалкерсона для поиска максимального паросочетания в двудольном графе G = (V, Е) за полиномиальное от |V| и |Е| время. Для этого рассмотрим сеть G' = (V', E'), построенную следующим образом: добавяляются две новые вершины: исток (s) и сток (t): V' = V U {s,t}. Е'= {(s,u):u L} U {(и, v): u L, v R, (и, v) E} U {(v,t): v R} (L и R обозначаются доли графа, ребра направленные). Будем считать, что пропускная способность каждого ребра равна единице.

42 Поток f в сети G = (V, Е) называется целочисленным, если все значения f(u,v) целые. Лемма 8 Пусть G = (V, Е) двудольный граф с долями L и R, и G' = (V, Е') соответствующая сеть. Пусть М паросочетание в G. Тогда существует целочисленный поток в G' со значением |f| = |М|. Обратно, если f целочисленный поток в G, то в G' найдется паросочетание из |f| элементов. Теорема 9 о целочисленном потоке Если пропускные способности всех рёбер целые числа, то максимальный поток, найденный алгоритмом Форда- Фалкерсона, будет целочисленным. Следствие 10 Число рёбер в максимальном паросочетания М в двудольном графе G равно значению максимального потока в сети G'.

43 Пример Соответствующая сеть G' и максимальный поток в ней. Пропускная способность любого ребра равна единице; поток по выделенным рёбрам равен единице, по остальным нулю. Выделенные рёбра, соединяющие вершины из L с вершинами из R, соответствуют максимальному паросочетанию в двудольном графе.

44 Анализ Таким образом, чтобы найти максимальное паросочетание в двудольном графе G, нам достаточно применить метод Форда-Фалкерсона и найти максимальный поток в соотвествующей сети G. Оценка времени работы такого алгоритма. Никакое паросочетание в двудольном графе не может содержать более min(L,R) = О (V) рёбер, поэтому значение максимального потока в G' равно O(V). Следовательно, время работы алгоритма Форда- Фалкерсона равно O(VE).

45 Алгоритм проталкивания предпотока Не просматриваем всю всю остаточную сеть на каждом шаге, а действуем локально в окрестности одной вершины. Кроме того, не требуем, выполнения закона сохранения потока в процессе работы алгоритма. Определим предпоток как функцию f : V X V > R, которая кососимметрична, удовлетворяет ограничениям, связанным с пропускными способностями, а также ослабленному закону сохранения: f(V, и) 0 для всех вершин и V\{s}. Таким образом, в каждой вершине и (кроме истока) есть некоторый неотрицательный избыток e(u) = f(V,u). Вершину, отличную от s, с положительным избытком назовём переполненной.

46 Мотивировка В алгоритмах проталкивания предпотока избыток, например, жидкости в каждой вершине сливается. Важную роль играет целочисленный параметр высота вершины. Мы будем воображать, что в процессе работы алгоритма вершина может подниматься вверх. Высота вершины определяет, куда мы стараемся направить избыток жидкости. Высота истока всегда равна |V|, а стока нулю. Все остальные вершины изначально находятся на высоте 0, и со временем поднимаются. Для начала мы отправляем из истока вниз столько жидкости, сколько нам позволяют пропускные способности выходящих из истока труб (это количество равно пропускной способности разреза (s, V\s )). Возникающий в соседних с истоком вершинах избыток жидкости сначала просто выливается, но затем будет направлен дальше.

47 Рассматривая какую-либо вершину и в ходе работы алгоритма, мы можем обнаружить, что в ней есть избыток жидкости, но все трубы, по которым ещё можно отправить жидкость из и куда-то (в ненасыщенные трубы) ведут в вершины той же или большей высоты. В этом случае мы можем выполнить операцию, называемую «подъёмом» вершины и. После этого вершина и становится на единицу выше самого низкого из тех её соседей, в которого ведёт ненасыщенная труба, т.е., мы поднимаем и ровно настолько, чтобы появилась ненасыщенная труба, ведущая вниз. В конце концов мы добьёмся того, что в сток приходит максимально возможное количество жидкости. При этом предпоток может ещё не быть потоком (избыток жидкости сливается). Продолжая подъём вершин, которые могут стать выше истока, мы постепенно отправим избыток обратно в исток, что означает сокращение потока жидкости от истока, и превратим предпоток в поток, который окажется максимальным.

48 Высотная функция Пусть G = (V, Е) сеть с истоком s и стоком t, а f предпоток в G. Функция h : V > N называется высотной функцией для предпотока f, если: h(s) = |V|, h(t) = 0, h(u) h(v) + 1 для любого ребра (и, v) E j. Лемма 11 Пусть f предпоток в сети G = (V, Е) и h высотная функция. Тогда если для вершин и, v V, выполнено h(u) > h(v) + 1, то остаточная сеть не содержит ребра (и, v) («по круто идущим вниз трубам идёт максимально возможный поток».) u v h(v) = kh(u) k+1

49 Операция проталкивания Push (и, v) применима, если: 1)вершина u переполнена: e(u) > 0; 2)ребро (и, v) не насыщено: с f (и, v) > 0; 3)h(u) = h(v) + 1. Push(u,v) { d f (u,v) = min(e(u), c f (u,v); f[u,v] = f[u,v]+ d f (u,v); f[v, u] = - f[u,v] e[u] = e[u] – d f (u,v); e[v] = e[v] + d f (u,v); }

50 Условие h(u) = h(v) + 1 гарантирует, что мы направляем дополнительный поток лишь по рёбрам, идущим вниз с единичной разницей высот. Проталкивание называется насыщающим, если в результате ребро (u,v) становится насыщенным, то есть если c f (u,v) обращается в нуль (ребро исчезает из остаточной сети); в противном случае проталкивание считают ненасыщающим. Если есть сосед, который на единицу ниже, то можно выполнить проталкивание, но нельзя выполнить подъём. Если все соседи не ниже, то проталкивание выполнить нельзя, а подъём можно, после чего возможно проталкивание.

51 Операция поднятия вершины Lift (u) применима, если: 1) вершина u переполнена: e(u) > 0; 2) для любого ребра (u,v) E f выполнено:h(u) h(v). Lift (и) поднимает переполненную вершину и на максимальную высоту, которая допустима по определению высотной функции: высота вершины превосходит высоту соседа в остаточной сети не более чем на 1. Lift(u) { h[u] = 1 + min{ h[v]: (u,v) E f }; } Заметим, если вершина и переполнена, то в E f найдётся по крайней мере одно ребро, выходящее из и: так как f[V, и] = е[и] > 0, поэтому существует по крайней мере одна такая вершина v, для которой f(v, и) > 0. c f (u, v) = c(u, v) - f[u, v] = c(u, v) + f[v, u] > 0, что означает, что (и, v) E f.}

52 Общая схема алгоритма проталкивания предпотока Начальный предпоток: C (u,v), если и=s f p (u,v) = –C (v,u), если и=s 0, в остальных случаях. Initialize(G, s) { for (для каждой вершины u V) { h[u] = 0; e[u] = 0; } for (для каждого ребра (u,v) E) { f[u,v] = 0; f[v,u] = 0; h[s] = |V|; } for (для каждой вершины u Adj [s]) { f[s,u] = c(s,u); f[u,s] = -c(s,u); e[u] = c(s,u); } }

53 Продолжение схемы алгоритма Поток по каждому ребру, выходящему из истока s, становится равным пропускной способности этого ребра. По остальным рёбрам поток равен 0. В каждой смежной с истоком вершине v появляется избыток e[v] = c(s, v ). h – высотная функция, так как рёбра (и, v), для которых h[u] > h[v] + 1, выходят только из истока, но они насыщены и их нет в остаточной сети. Generic-Preflow-Push { Initialize(G,s); while (возможны операции подъема или проталкивания) выполнить одну из этих операций; }

54 t S e=16 e=13-13 e=0 e= e= st v

55 st t e=16 e=0 e=0+7 e=9-7 e=4 7 2

56 Анализ Лемма 12 Пусть f предпоток в сети G = (V,E). Пусть h высотная функция для f и вершина и переполнена. Тогда в и возможно либо проталкивание, либо подъём. Доказательство Поскольку h высотная функция, то h(u) h(y) +1 для любого остаточного ребра (u,v). Если в и невозможно проталкивание, то для всех остаточных рёбер (и, v) выполнено неравенство h(u) < h(v) + 1, из чего следует, что h(u) h(v), и в вершине и возможен подъём. Корректность метода. 1) Если алгоритм остановится, то предпоток f в этот момент будет максимальным потоком. 2) Алгоритм действительно остановится. Лемма 13 ри исполнении программы Generic-Preflow-Push высота h[u] любой вершины и V может только возрастать. Лемма 14 Во время выполнения программы Generic-Preflow-Push функция h остаётся высотной функцией. Лемма 15 Пусть G = (V, Е) сеть с истоком s и стоком t. Пусть f предпоток в G, a h высотная для f. Тогда в остаточной сети G f не существует пути из истока в сток.

57 Теорема Если программа Generic-Preflow-Push, применённая к сети G = (V, Е) с истоком s и стоком t останавливается, то получающийся предпоток f, будет максимальным потоком для G. Пояснение. В момент остановки переполненных вершин в сети нет. Значит, в этот момент предпоток является потоком. Функция h будет высотной функцией, и потому в остаточной сети G f нет пути из s в t. По теореме о максимальном потоке и минимальном разрезе поток f максимален. Лемма 16 Пусть G = (V, Е) сеть с истоком s и стоком t, а f предпоток в G. Тогда для любой переполненной вершины и найдется простой путь из и в s в остаточной сети G f. Лемма 17 При исполнении программы Generic-Preflow-Push высота любой вершины v V не превосходит 2|V| 1.

58 Следствие При исполнении программы Generic-Preflow-Push общее число операций подъёма не превосходит 2|V| 2. Лемма 18 При исполнении программы Generic-Preflow-Push количество насыщающих проталкиваний не превосходит 2|V||E|. Теорема Общее число операций подъёма и проталкивания при исполнении программы Generic-Preflow-Push на сети G = (V, Е) равно O(V 2 E).

59 Задача о выходе Имеется, граф вершины которого образуют решётку из n строк и n столбцов. Обозначим через (i, j) вершину на пересечении i-го столбца и j-ой строки. Все вершины такой решётки, не считая граничных имеют четырёх соседей. Требуется выяснить, существуют ли т попарно непересекающихся (не имеющих общих вершин) путей от данных т n 2 начальных точек решётки (x 1,y 1 ), (х 2,y 2 ), …, (х т,y т ) к т различным граничным точкам.

60 Подсказка к решению Рассмотрим сеть, в которой каждая внутрення вершина имеет дубль. Все инцидентные ребра каждой внутренней вершины сделайте входящими. Добавьте выходящую дугу из каждой внутренней вершины в вершину-дубль. Все инцидентные ребра каждой внутренней вершины сделайте выходящими из вершины-дубля. Покажите, что задача о максимальном потоке в такой сети сводится к обычной задаче о максимальном потоке для построенной таким образом сети.

61 Минимальное покрытие путями Покрытием путями ориентированного графа G = (V, Е) назовается множество путей Р с таким свойством: каждая вершина из V принадлежит ровно одному пути из Р. Пути могут начинаться и заканчиваться где угодно, и иметь любую длину, в том числе нулевую. Покрытие наименьшим возможным числом путей называется минимальным покрытием путями. Решение Построим граф G' = (V, Е), где V = {х 0, х 1,..., х n } U {у 0, y 1, …, у n }, E' = {(x 0, x i ): x i V} U {(y i, y 0 ): y i V} U {(x i, y j }: (i, j) Е} Решим для этого графа задачу о максимальном потоке.

62 Пример Также нужно достроить исток и сток. Исток соединить с левой долей, сток – с правой