ПОТОКИ В СЕТЯХ презентация

и мультидуг, с 1 источником s∈V и 1 стоком t∈V.
(Запретим одновременное ∃ дуг (i, j) и (j, i))

∀ дуге графа (i, j) ∈ A, приписана пропускная способность bij ≥ 0, целое число, которое задает max доп. величину потока по дуге.

Потоком из источника s в сток t (или s−t потоком) в сети G назовем мн. неотрицательных чисел xij, (i, j)∈A, для которых выполнены условия сохранения потока

и ограничения на
дуговые потоки
0 ≤ xij ≤ bij, (i, j) ∈ A

ЛП ⇒ для ее решения применим аппарат ЛП.
Более того, mat ограничений удовлетворяет свойству
абсолютной унимодулярности…

Известно неск. полиномиальных алг., трудоемкость кот. O(|V|3).

путем любой путь P из s в t в неориентированном графе, полученном из графа G игнорированием направлений дуг, кот. обладает след. свойствами:
1) ∀ дуги (i, j) ∈ E, проходимой путем P в прямом направлении (и называемой прямой дугой), xij < bij, т. е. прямые дуги пути не ненасыщенны;
2) ∀ дуги (j, i) ∈ E, проходимой путем P в обратном направлении
i → j (и называемой обратной дугой), xji > 0.

s−t разрезом

наз. разбиение мн. вершин V на подмн. X и

Пропускная способность s−t разреза

равна

s−t разрез является узким местом сети:

среди всех s−t разрезов.

Теорема (Форда−Фалкерсона). В ∀ сети величина max s−t потока = пропускной способности min s−t разреза.
Доказательство. Рассмотрим доп. поток {xij}. Если v = проп. спос. некоторого разреза, то теорема доказана. В прот. сл. величину потока можно ↑ по приводимому ниже правилу до тех пор, пока v не станет = проп. спос. нек. разреза.
Имея поток {xij}, находим подмн. в. Х по след. правилам:

0. Поместим источник s в мн. X.
1. Если i ∈ X и xij < bij (дуга (i, j) не насыщена), то в. j → X.
2. Если i ∈ X и xji > 0 (∃ > 0 поток по (j, i)), то в. j → X.

2 для построения Х, получим 1 из 2-х результатов:

I. Сток

Тогда ∀ дуги (i, j) ∈ E, i ∈ X,

согласно пр. 1 вып. условие xij = bij и, согласно пр. 2, имеет место равенство xji = 0 ⇒

⇒

и

⇒ получен поток, величина кот. =

II. Сток

Тогда из опр. мн. Х ⇒ ∃ увеличивающий s-t путь

s,…,i,i+1,…,t, в кот. все прямые дуги (i, i+1) не насыщены, и ∃
>0 поток по всем обратным дугам пути xi+1,i > 0.

дугам (i, i+1) пути,
ε2 = minxi+1,i по всем обратным дугам (i+1, i),
ε = min{ε1, ε2} > 0.
Проп. спос. bij − целые числа.
Начнем с целочисленного потока (например, 0).
⇒ ε − целое > 0
Можно увеличить на ε потоки по всем прямым дугам пути и уменьшить на ε потоки по всем обратным дугам пути.
⇒ величина s−t потока увеличится на ε, и новые значения дуговых потоков останутся допустимыми.
Используя новый поток, можно построить новое мн. Х. Если t попадет в Х, то можно снова увеличить поток и т. д.
Т.к. проп. спос. min разреза ограничена, и на каж. шаге величина потока ↑ ≥ на 1, то после конечного числа шагов получим ситуацию I и ⇒ max поток.

разл. max потоков и min разрезов.

Теорема. Пусть

– min s−t разрезы. Тогда

и

и

также min s−t разрезы.

Теорема. Пусть

– min s−t разрезы, а

полученный в доказательстве теоремы Форда−Фалкерсона. Тогда

– разрез,

В алгоритме ∀ вершина может находиться в 1 из 3 состояний:
не помечена,
помечена,
помечена и просмотрена.
В начале все в. не помечены.

из 2 частей:
1) либо индекса i+, если можно ↑ поток из i в j, либо индекса i−, если можно ↓ поток из j в i;
2) числа ε(j), указывающего max величину, на кот. можно ↑ s-j поток, не нарушая ограничений на проп. спос.
Ист. s приписывается метка [s+, ε(s)=+∞]. Теперь в. s помечена, а все остальные в. не помечены.
Выберем ∀ помеч. но не просм. в. j. Она имеет метку [i+, ε(j)], или [i−, ε(j)].
Каж. непом. в. k : xjk < bjk, припишем метку [j+, ε(k)], где
ε(k)=min{ε(j), bjk−xjk}. Такие в. k теперь помечены.
Всем непом. в. k : xkj > 0, припишем метки [j−, ε(k)], где
ε(k)=min{ε(j), xkj}. Такие в. k теперь также помечены.
Когда все смежные с j в. помеч., в. j – помеч. и просмотренная.
Рассмотрим др. помеч., но не просм. в., пока t не окажется помеч. либо нельзя > пометить ни 1 в. и t остался непомечен.

s-t пути, и текущий поток max.
Если t помеч., то на шаге 2 поток по найденному увеличивающему пути увеличивается.
Шаг 2. (Увеличение потока). Пусть t имеет метку [k+, ε(t)]. Тогда положим xkt=xkt+ε(t) и перейдем к в. k.
Если k имеет метку [j+, ε(k)], то положим xjk=xjk+ε(t).
Если k имеет метку [j−, ε(k)], то положим xkj=xkj−ε(t).
Переходим к в. j.
Продолжим движение по увеличивающему пути от стока к источнику, пока не придем в s. В результате величина потока увеличится на ε(t).
Положим все вершины непомеченными и перейдем на шаг 1.

Если нельзя пометить более ни 1 в. и сток остался непомеч., то

– min разрез, и полученный поток max

сходиться не к max потоку.
∃ простые модификации алг. :
Шаг 1. Удалить из сети все насыщенные дуги и перейти на шаг 2.
Шаг 2. Найти увеличивающий путь и послать по нему max возможный поток. Перейти на шаг 1.
Если такого пути нет, то перейти на шаг 3.
Шаг 3. Восстановить все дуги сети. Найти увеличивающий путь и послать по нему max возможный поток. Перейти на шаг 1. Если увеличивающего пути нет, то алг. завершает работу.

Трудоемкость алг. Форда−Фалкерсона зависит от v и ⇒ является псевдополиномиальной.
∃ методы, в которых среди увеличивающих путей находится путь min длины (по количеству входящих в него дуг), имеющие полиномиальную трудоемкость O(|V|3).

A

Если бы не было ограничений на проп. спос. дуг, то для решения задачи достаточно найти кратчайший (по cij) путь из s в t и пропустить по нему поток величины v.

Приведем 2 алгоритма для случая целочисленных bij

= 0.
Шаг 1. Определить модифицированные дуговые стоимости

Шаг 2. Найти путь из s в t min длины и увеличить на 1 поток по этому пути. Если величина нового потока равна v, то алг. останавливается. В противном сл. перейти на шаг 1.

Определяем модиф. стоимости

Шаг 2. Находим путь из s в t min длины, например, {s, 1, 2, t}.
Полагаем xs1 = x12 = x2t =1. Перейдем на Шаг 1.

3, 2, 1, 4, t} min длины 5. Пропустим 1 потока по этому пути:

Шаг 1. Определить модифицированные дуговые стоимости

Шаг 2. Найти цикл <0 стоимости (назовем его отрицательным), где стоимость цикла равна сумме модиф. стоимостей входящих в него дуг. Увеличить поток по <0 циклу на δ =min{bij – xij, xji}, где min берется по всем прямым (i, j) и обрат. (j, i) дугам цикла, и перейти на шаг 2.
Если <0 цикла нет, то найденный поток opt!
(Если в сети ∃ несколько <0 циклов, то увеличить поток по каж. из них.)

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

oi, затем из t в s по пути pi. Это отрицательный цикл (для модифицированных стоимостей). Получили противоречие.

Случай b. Обозн. через f 1-ю в., после кот. пути oi и pi начинают различаться, а через l – 1-ю в., после кот. они совпадают. Стоимость потока по участку пути oi от f в l меньше стоимости по участку пути pi от f в l. ⇒ найден <0 цикл: из f в l по пути oi, а из l в f по пути pi. Это противоречие доказывает теорему.

s

t

oi

pi

f

l

pi

oi

s

t

Флойда−Уоршелла.
Пусть dij – веса дуг (i, j)∈E. Рассмотрим след. тернарную
(3-местную) операцию, определенную для нек. фикс. в. j:
dik=min{dik, dij+djk}, i,k ≠ j (*)
Если выполнить операцию (*) ∀ в. j, то в случае ≥ 0 весов получ. в результате зн. dik = длинам кратчайших путей из i в k ∀ пар вер.

Положим dii=+∞ и применим (*) ∀ j, i и k.
Если ∃ в. i : dii < 0 ⇒ она ∈ <0 циклу. Сам <0 цикл восстанавливается переходя из в. i в смежную в. j, у кот. djj < 0. Из в. j переходим в новую в. k с dkk < 0… пока не вернемся в в. i.
T=O(n3).

i

k

j