ПОТОКИ В СЕТЯХ. Определения Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 1 источником s V и 1 стоком t V. (Запретим одновременное. - презентация

1 ПОТОКИ В СЕТЯХ

2 Определения Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 1 источником s V и 1 стоком t V. (Запретим одновременное дуг (i, j) и (j, i)) дуге графа (i, j) A, приписана пропускная способность b ij 0, целое число, которое задает max доп. величину потока по дуге. Потоком из источника s в сток t (или s t потоком) в сети G назовем мн. неотрицательных чисел x ij, (i, j) A, для которых выполнены условия сохранения потока и ограничения на дуговые потоки 0 x ij b ij, (i, j) A

3 Максимальный поток 0 x ij b ij, (i, j) A З. ЛП для ее решения применим аппарат ЛП. Более того, mat ограничений удовлетворяет свойству абсолютной унимодулярности… Известно неск. полиномиальных алг., трудоемкость кот. O(|V| 3 ).

4 Определения Пусть задан доп. поток из s в t. Назовем увеличивающим путем любой путь P из s в t в неориентированном графе, полученном из графа G игнорированием направлений дуг, кот. обладает след. свойствами: 1) дуги (i, j) E, проходимой путем P в прямом направлении (и называемой прямой дугой), x ij < b ij, т. е. прямые дуги пути не ненасыщенны; 2) дуги (j, i) E, проходимой путем P в обратном направлении i j (и называемой обратной дугой), x ji > 0. s t разрезом наз. разбиение мн. вершин V на подмн. X и Пропускная способность s t разреза равна s t разрез является узким местом сети:

5 Определения stijk Увеличивающий путь: s t ij kl Разрез и его пропускная способность:

6 Теорема Форда Фалкерсона Наз. s t разрез минимальным, если он имеет min проп. спос. среди всех s t разрезов. Теорема (Форда Фалкерсона). В сети величина max s t потока = пропускной способности min s t разреза. Доказательство. Рассмотрим доп. поток {x ij }. Если v = проп. спос. некоторого разреза, то теорема доказана. В прот. сл. величину потока можно по приводимому ниже правилу до тех пор, пока v не станет = проп. спос. нек. разреза. Имея поток {x ij }, находим подмн. в. Х по след. правилам: 0. Поместим источник s в мн. X. 1. Если i X и x ij < b ij (дуга (i, j) не насыщена), то в. j X. 2. Если i X и x ji > 0 ( > 0 поток по (j, i)), то в. j X.

7 Доказательство теоремы Форда Фалкерсона Вершины Х поместим в мн. Исп-я пр. 0 – 2 для построения Х, получим 1 из 2-х результатов: I. Сток Тогда дуги (i, j) E, i X, согласно пр. 1 вып. условие x ij = b ij и, согласно пр. 2, имеет место равенство x ji = 0 и получен поток, величина кот. = II. Сток Тогда из опр. мн. Х увеличивающий s-t путь s,…,i,i+1,…,t, в кот. все прямые дуги (i, i+1) не насыщены, и >0 поток по всем обратным дугам пути x i+1,i > 0.

8 Доказательство теоремы Форда Фалкерсона Пусть 1 = min(b i,i+1 – x i,i+1 ) по всем прямым дугам (i, i+1) пути, 2 = minx i+1,i по всем обратным дугам (i+1, i), = min{ 1, 2 } > 0. Проп. спос. b ij целые числа. Начнем с целочисленного потока (например, 0). целое > 0 Можно увеличить на потоки по всем прямым дугам пути и уменьшить на потоки по всем обратным дугам пути. величина s t потока увеличится на, и новые значения дуговых потоков останутся допустимыми. Используя новый поток, можно построить новое мн. Х. Если t попадет в Х, то можно снова увеличить поток и т. д. Т.к. проп. спос. min разреза ограничена, и на каж. шаге величина потока на 1, то после конечного числа шагов получим ситуацию I и max поток.

9 Разрезы Следствие. Поток max не увеличивающего пути. В сети может несколько разл. max потоков и min разрезов. Теорема. Пусть – min s t разрезы. Тогда и и также min s t разрезы. Теорема. Пусть – min s t разрезы, а полученный в доказательстве теоремы Форда Фалкерсона. Тогда – разрез, В алгоритме вершина может находиться в 1 из 3 состояний: не помечена, помечена, помечена и просмотрена. В начале все в. не помечены.

10 Алгоритм расстановки пометок Форда-Фалкерсона Шаг 1. (Расстановка пометок). Метка в. j состоит из 2 частей: 1) либо индекса i +, если можно поток из i в j, либо индекса i, если можно поток из j в i; 2) числа (j), указывающего max величину, на кот. можно s-j поток, не нарушая ограничений на проп. спос. Ист. s приписывается метка [s +, (s)=+ ]. Теперь в. s помечена, а все остальные в. не помечены. Выберем помеч. но не просм. в. j. Она имеет метку [i +, (j)], или [i, (j)]. Каж. непом. в. k : x jk < b jk, припишем метку [j +, (k)], где (k)=min{ (j), b jk x jk }. Такие в. k теперь помечены. Всем непом. в. k : x kj > 0, припишем метки [j, (k)], где (k)=min{ (j), x kj }. Такие в. k теперь также помечены. Когда все смежные с j в. помеч., в. j – помеч. и просмотренная. Рассмотрим др. помеч., но не просм. в., пока t не окажется помеч. либо нельзя > пометить ни 1 в. и t остался непомечен.

11 Алгоритм расстановки пометок Форда-Фалкерсона Если t не помеч., то не увеличивающего s-t пути, и текущий поток max. Если t помеч., то на шаге 2 поток по найденному увеличивающему пути увеличивается. Шаг 2. (Увеличение потока). Пусть t имеет метку [k +, (t)]. Тогда положим x kt =x kt + (t) и перейдем к в. k. Если k имеет метку [j +, (k)], то положим x jk =x jk + (t). Если k имеет метку [j, (k)], то положим x kj =x kj (t). Переходим к в. j. Продолжим движение по увеличивающему пути от стока к источнику, пока не придем в s. В результате величина потока увеличится на (t). Положим все вершины непомеченными и перейдем на шаг 1. Если нельзя пометить более ни 1 в. и сток остался непомеч., то – min разрез, и полученный поток max

12 Замечания Замечание. Если b ij R, то алг. может не быть конечным или может сходиться не к max потоку. простые модификации алг. : Шаг 1. Удалить из сети все насыщенные дуги и перейти на шаг 2. Шаг 2. Найти увеличивающий путь и послать по нему max возможный поток. Перейти на шаг 1. Если такого пути нет, то перейти на шаг 3. Шаг 3. Восстановить все дуги сети. Найти увеличивающий путь и послать по нему max возможный поток. Перейти на шаг 1. Если увеличивающего пути нет, то алг. завершает работу. Трудоемкость алг. Форда Фалкерсона зависит от v и является псевдополиномиальной. методы, в которых среди увеличивающих путей находится путь min длины (по количеству входящих в него дуг), имеющие полиномиальную трудоемкость O(|V| 3 ).

13 st 1 2 1,13,0 2,1 2,2 1,1 проп. спос. поток Пример [s +, ] [s +,1] [2,1] [1 +,1]

14 st 1 2 1,13,1 2,1 1,0 проп. спос. поток Пример [s +, ] [s +,1] [2 +,1]

15 st 1 2 1,13,1 2,2 1,1 проп. спос. поток Пример [s +, ]

16 Потоки минимальной стоимости 0 x ij b ij, (i, j) A Если бы не было ограничений на проп. спос. дуг, то для решения задачи достаточно найти кратчайший (по c ij ) путь из s в t и пропустить по нему поток величины v. Приведем 2 алгоритма для случая целочисленных b ij

17 Алгоритм Басакера Гоуэна Шаг 0. Положить все дуговые потоки и v = 0. Шаг 1. Определить модифицированные дуговые стоимости Шаг 2. Найти путь из s в t min длины и увеличить на 1 поток по этому пути. Если величина нового потока равна v, то алг. останавливается. В противном сл. перейти на шаг 1.

18 st Пример v = 2 1,11,2 1,1 1,2 2,2 1,1 стоимость проп. спос. Шаг 0. Полагаем x ij = 0. Шаг 1. Определяем модиф. стоимости Шаг 2. Находим путь из s в t min длины, например, {s, 1, 2, t}. Полагаем x s1 = x 12 = x 2t =1. Перейдем на Шаг 1.

19 st Пример v = 2 1,0 1,1 2,0 1,1 Шаг 1. 2,0 поток проп. спос. Шаг 2. Находим путь {s, 3, 2, 1, 4, t} min длины 5. Пропустим 1 потока по этому пути:

20 st Пример v = 2 1,1 1,0 2,1 1,1 2,1 поток проп. спос.

21 Алгоритм Клейна Шаг 0. Найти произвольный доп. s t поток величины v. Шаг 1. Определить модифицированные дуговые стоимости Шаг 2. Найти цикл

22 Корректность алгоритма Клейна Теорема. Поток величины v opt в сети с модиф. дуговыми стоимостями не отрицательных циклов. Доказательство. следует из того, что в случае < 0 цикла можно добавить циркуляцию по этому циклу, сохранив величину потока и уменьшив его стоимость, что противоречит opt потока.. Рассмотрим нек. поток, для кот. в сети не < 0 циклов. Предположим, что opt поток имеет < стоимость. Разложим opt поток на v путей, обозначим их o i, i = 1,…,v, по каж. из кот. пропущен 1-ый поток. Аналогично разложим рассматриваемый поток на v путей p i, i = 1,…,v, по каж. из кот. пропущен 1-ый поток. Ввиду того, что opt поток имеет < стоимость, пути o i и p i : стоимость потока по o i < стоимости потока по p i. Тогда эти пути: a) либо не имеют общих дуг, b) либо частично совпадают.

23 Доказательство теоремы Случай a. Рассмотрим цикл из s в t по o i, затем из t в s по пути p i. Это отрицательный цикл (для модифицированных стоимостей). Получили противоречие. Случай b. Обозн. через f 1-ю в., после кот. пути o i и p i начинают различаться, а через l – 1-ю в., после кот. они совпадают. Стоимость потока по участку пути o i от f в l меньше стоимости по участку пути p i от f в l. найден

24 Нахождение отрицательных циклов Для нахождения

25 Пример проп. спос. стоимость

26 Пример v = 85

27 Пример i\ji\js1246 s i\ji\j35789t t -4 -3