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

Презентация на тему Презентация на тему ПОТОКИ В СЕТЯХ, предмет презентации: Разное. Этот материал содержит 27 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

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


Слайд 2
Текст слайда:

Определения

Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 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


Слайд 3
Текст слайда:

Максимальный поток

0 ≤ xij ≤ bij, (i, j) ∈ A


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

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


Слайд 4
Текст слайда:

Определения

Пусть задан доп. поток из s в t. Назовем увеличивающим путем любой путь 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 разрез является узким местом сети:


Слайд 5
Текст слайда:

Определения

s

t

i

j

k

Увеличивающий путь:

s

t



i

j

k

l

Разрез и его пропускная способность:


Слайд 6
Текст слайда:

Теорема Форда−Фалкерсона

Наз. s−t разрез минимальным, если он имеет min проп. спос. среди всех 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.


Слайд 7
Текст слайда:

Доказательство теоремы Форда−Фалкерсона

Вершины ∉ Х поместим в мн.

Исп-я пр. 0 – 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.


Слайд 8
Текст слайда:

Доказательство теоремы Форда−Фалкерсона

Пусть ε1 = min(bi,i+1 – xi,i+1) по всем прямым дугам (i, i+1) пути,
ε2 = minxi+1,i по всем обратным дугам (i+1, i),
ε = min{ε1, ε2} > 0.
Проп. спос. bij − целые числа.
Начнем с целочисленного потока (например, 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 : 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 остался непомечен.


Слайд 11
Текст слайда:

Алгоритм расстановки пометок Форда-Фалкерсона

Если 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


Слайд 12
Текст слайда:

Замечания

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

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


Слайд 13
Текст слайда:

s

t

1

2

1,1

3,0

2,1

2,2

1,1

проп. спос.

поток

Пример

[s+,∞]

[s+,1]

[2─,1]

[1+,1]


Слайд 14
Текст слайда:

s

t

1

2

1,1

3,1

2,1

2,1

1,0

проп. спос.

поток

Пример

[s+,∞]

[s+,1]

[2+,1]


Слайд 15
Текст слайда:

s

t

1

2

1,1

3,1

2,2

2,2

1,1

проп. спос.

поток

Пример

[s+,∞]


Слайд 16
Текст слайда:

Потоки минимальной стоимости

0 ≤ xij ≤ bij, (i, j) ∈ A


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

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


Слайд 17
Текст слайда:

Алгоритм Басакера−Гоуэна

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

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


Слайд 18
Текст слайда:

s

t

1

2

3

4

Пример

v = 2

1,1

1,2

1,1

1,2

2,2

2,2

1,1

стоимость

проп. спос.

Шаг 0. Полагаем xij = 0.
Шаг 1. Определяем модиф. стоимости

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


Слайд 19
Текст слайда:

s

t

1

2

3

4

Пример

v = 2

1,0

1,0

1,1

1,1

2,0

1,1

Шаг 1.

2,0

поток

проп. спос.

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


Слайд 20
Текст слайда:

s

t

1

2

3

4

Пример

v = 2

1,1

1,1

1,1

1,0

2,1

1,1

2,1

поток

проп. спос.


Слайд 21
Текст слайда:

Алгоритм Клейна

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

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


Слайд 22
Текст слайда:

Корректность алгоритма Клейна

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


Слайд 23
Текст слайда:

Доказательство теоремы

Случай a. Рассмотрим цикл из s в t по 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


Слайд 24
Текст слайда:

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

Для нахождения <0 циклов можно воспользоваться след. проц. Флойда−Уоршелла.
Пусть 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


Слайд 25
Текст слайда:

Пример

проп. спос.

стоимость


Слайд 26
Текст слайда:

Пример

v = 85


Слайд 27
Текст слайда:

Пример


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика