Разделы презентаций


Потоки в сетях презентация, доклад

Содержание

Основные задачи Если приписать каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным или

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

Слайд 1Потоки в сетях

Потоки в сетях

Слайд 2Основные задачи
Если приписать каждой дуге ориентированного графа поток

некоторого вещества, граф становится удобной моделью при исследовании целого ряда

проблем в транспорте, связи и других областях, связанных с действительным или воображаемым движением товаров, информации или людей.
Исследуется две основные задачи:
максимизация суммарного потока между двумя заданными вершинами при условии, что поток через каждую дугу ограничен сверху и снизу;
задача нахождения ограниченных потоков с минимальной стоимостью, когда каждой дуге приписана стоимость единицы потока.
Основные задачи  Если приписать каждой дуге ориентированного графа поток некоторого вещества, граф становится удобной моделью при

Слайд 3Ограничим определение ориентированного графа
наличие петель недопустимо
если существует дуга из vi

в vj, то дуги из vj в vi нет
ориентированный граф

должен быть связанным
Ограничим определение ориентированного графаналичие петель недопустимоесли существует дуга из vi в vj, то дуги из vj в

Слайд 4Разделяющие множества
Пусть G = (V, E) — связный граф и F

 E — подмножество множества его ребер. При этом F

называется разделяющим множеством тогда и только тогда, когда подграф G = (V, E – F) несвязен.
Разделяющие множества всегда существуют (если граф имеет по меньшей мере две вершины), так как всегда можно положить F = E. Очевидно, что граф может быть разбит разделяющим множеством на более чем две компоненты.
Разделяющие множестваПусть G = (V, E) — связный граф и F  E — подмножество множества его ребер.

Слайд 5Разрезы
Если задан связный граф G = (V, E) и множество его

вершин разбито на два непустых подмножества А и A, множество

ребер, соединяющих A с A, называется разрезом.
Для любого множества A это множество ребер будет непусто в силу связности графа G, и следовательно, разрез определен. Для любого заданного графа совокупность разрезов, определенных различными множествами A, образует подкласс класса всех разделяющих множеств и, более того, любое разделяющее множество содержит, по крайней мере, один разрез в качестве своего подмножества.

РазрезыЕсли задан связный граф G = (V, E) и множество его вершин разбито на два непустых подмножества А

Слайд 6Сети
Под сетью мы будем понимать пару S = G, с,

где G = V, E — произвольный ориентированный граф, а с:

E  R — функция, которая каждой дуге u, v ставит в соответствие неотрицательное вещественное число с(и, v), называемое пропускной способностью этой дуги. Множества V и Е называются соответственно множеством вершин и множеством дуг сети S.
СетиПод сетью мы будем понимать пару S = G, с, где G = V, E — произвольный ориентированный

Слайд 7Поток в сети
Потоком в сети S называется функция f, определенная

на E. Число f(u, v) называется потоком по дуге (u,

v). Более точно, говорят, что поток направлен от u к v, если f(u, v) > 0 и поток направлен от v к u, если f(u, v) < 0.
Будем для наглядности далее иметь в виду геометрическую реализацию сети и интерпретировать |f(u,v)| как постоянную скорость потока однородного вещества через дугу (u, v). Направление потока определяется знаком f(u, v)
Поток в сетиПотоком в сети S называется функция f, определенная на E. Число f(u, v) называется потоком

Слайд 8Классификация вершин по воздействию на поток
Для произвольной функции f: E

 R и произвольной вершины v сети S рассмотрим величину



Если f(u, v) мы интерпретируем как поток из и в v, то величина Divf (v) определяет «количество потока» (чистый поток), выходящего из вершины v. Эта величина может быть > 0 (если из вершины v больше выходит, чем входит в нее), < 0 (если в вершину входит больше, чем выходит из нее, т. е. наступает «накопление» потока в вершине v) и, наконец, = 0.
Вершина создает поток, поглощает или сохраняет.

Классификация вершин по воздействию на потокДля произвольной функции f: E  R и произвольной вершины v сети

Слайд 9 Сгруппируем вершины сети в множества V+, V– и

V0 следующим образом:
V+ = {v  V| Div (v) >

0},
V– = {v  V| Div (v) < 0},
V0 = {v  V| Div (v) < 0}.
V+, V–. V0 называются источниками, стоками и промежуточными вершинами соответственно
Сгруппируем вершины сети в множества V+, V– и V0 следующим образом:V+ = {v  V|

Слайд 10Преобразование задачи о максимальном потоке с несколькими источниками несколькими стоками

к задаче с одним источником и одним стоком

Преобразование задачи о максимальном потоке с несколькими источниками несколькими стоками к задаче с одним источником и одним

Слайд 11Величина потока
Выделим в нашей сети две вершины — источник, s

и сток t (s  t).
Под потоком из s

в t в сети S мы будем понимать произвольную функцию вида f: E  R, для которой выполняются условия
f(u, v)  с(и, v) для каждой дуги u, v  Е (ограничение пропускной способности),
f(u, v) = — f (v, u) (антисимметричность)
и
Div f (v) = 0 для каждой вершины v  V \{s, t} (сохранение потока).
Величину W(f) = Div f (s) будем называть величиной потока f.
Величина потокаВыделим в нашей сети две вершины — источник, s и сток t (s  t). Под

Слайд 12Под разрезом Р(А) сети S, соответствующим подмножеству А  V

(А  , А  V), мы понимаем множество дуг

u, v  Е, таких что u  А и v  V\A.
Для произвольного потока f в сети S поток через разрез Р(А) определяется естественным образом:
Под разрезом Р(А) сети S, соответствующим подмножеству А  V (А  , А  V), мы

Слайд 13Лемма 1. Если s  А и t  V\A,

то для произвольного потока f из s в t
W(f) =

f(A, V\A) — f(V\A, A).
Доказательство. Суммируем уравнения Divf (v) = 0 для всех v  А. Эта сумма складывается из некоторого числа слагаемых f(u, v), снабженных знаком плюс и минус, причем хотя бы одна из вершин и, v принадлежит множеству А. Если обе вершины принадлежат A, то f(u, v) появляется со знаком плюс в Divf(u) и со знаком минус в Divf(v) (и не появляется в выражении Divf(r) ни для одного r, отличного от и и v), что в сумме дает 0. Каждое из слагаемых f(u, v), и  A, v  V\A появляется в точности один раз со знаком плюс в Divf(u), что в сумме дает f(A, V\A). Аналогичные слагаемые f(u, v), и  V\A, v  A отвечают за слагаемое f(V\A, A). С другой стороны наша сумма равна Divf(s) = W(f), ибо Divf(v) = 0 для каждого v  A\{s}.
Лемма 1. Если s  А и t  V\A, то для произвольного потока f из s

Слайд 14Принимая A = V\{t}, получаем в этом частном случае из

леммы 1
Divf(s) = W(f) = f(V\{t}, {t}) – f({t}, V\{t}) =
=

– (f({t}, V\{t}) – f(V\{t}, {t})) = – Divf(t),
что выражает интуитивно понятный факт: в сток входит в точности такое количество потока, какое выходит из источника. В общем виде лемма 1 говорит, что общее количество потока можно измерить в произвольном разрезе, отделяющем s от t.
Принимая A = V\{t}, получаем в этом частном случае из леммы 1Divf(s) = W(f) = f(V\{t}, {t}) –

Слайд 15Определим пропускную способность разреза Р(А):
Под минимальным разрезом, разделяющим s и

t, мы будем понимать произвольный разрез Р(А), s

 А, t  V\A с минимальной пропускной способностью.

Определим пропускную способность разреза Р(А):Под минимальным разрезом, разделяющим s и t, мы будем понимать произвольный разрез Р(А),

Слайд 16Пример
Примеры разрезов — множества S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z),

(y,b)}, S3={(y,b), (z,b)}.
Определите пропускные способности этих разрезов

ПримерПримеры разрезов — множества S1={(a,y), (a,x), (a,z)}, S2={(a,z), (x,z), (y,z), (y,b)}, S3={(y,b), (z,b)}. Определите пропускные способности этих

Слайд 17Теорема (Форд и Фалкерсон).
Величина каждого потока из s в t

не превосходит пропускной способности минимального разреза, разделяющего s и t,

причем существует поток, достигающий этого значения.
Доказательство. Пусть Р(А) — минимальный разрез. В силу леммы 1 для произвольного потока f имеем
W(f) = f(A, V \A) – f(V \A, A)  f(A, V \A) =

Теорема (Форд и Фалкерсон).Величина каждого потока из s в t не превосходит пропускной способности минимального разреза, разделяющего

Слайд 18Как определить максимальный поток

Как определить максимальный поток

Слайд 20Следует обратить внимание, что если поток из источника равен сумме

пропускных способностей ребер, выходящих из источника, или поток, втекающий в

сток, равен сумме пропускных способностей ребер, входящих в сток, то поток максимальный. Однако, поток может быть максимальным и без удовлетворения какого-либо из этих признаков.
Следует обратить внимание, что если поток из источника равен сумме пропускных способностей ребер, выходящих из источника, или

Слайд 21Метод Форда-Фалкерсона
концепция остаточных сетей
концепция увеличивающих цепей
концепция разрезов
Метод является итеративным
Ford_Fulkerson_Method (G,

s, t)
Задаем начальное значение потока f равным 0
while существует увеличивающая

цепь p
do увеличиваем поток f вдоль цепи p
return f
Метод Форда-Фалкерсонаконцепция остаточных сетейконцепция увеличивающих цепейконцепция разрезовМетод является итеративнымFord_Fulkerson_Method (G, s, t)Задаем начальное значение потока f равным

Слайд 22Остаточные сети
Если задана некоторая сеть и поток, то остаточная сеть

— это сеть, состоящая из ребер, допускающих увеличение потока.
Пусть G

= V, E — сеть с источником s и стоком t. Величина дополнительного потока, который мы можем отправить из u в v, не превысив пропускную способность c(u,v), является остаточной пропускной способностью:
cf(u,v) = c(u, v) – f (u,v)

Остаточные сетиЕсли задана некоторая сеть и поток, то остаточная сеть — это сеть, состоящая из ребер, допускающих

Слайд 23Для заданной сети G = V, E и потока f, остаточной

сетью, порожденной потоком f, является сеть Gf = V, Ef 

, где
Ef = {(u,v)  V V: cf(u,v) >0}.
Ребрами Ef являются или ребра E, или обратные им. Если f(u,v) 0 и (u,v)  Ef . Если f (u,v) > 0 для некоторого ребра (u,v)  E, то f (v, u) < 0. В таком случае cf(v, u) = c(v, u) – f (v, u) >0, и, следовательно, (v, u)  Ef .


Для заданной сети G = V, E и потока f, остаточной сетью, порожденной потоком f, является сеть Gf

Слайд 25Метод увеличивающих цепей
Будем говорить, что дуга е сети S

является допустимой дугой из и в v относительно потока f,

если
е = и f(e) < c(e)
или
е = < v, u > и f(e) > 0.
В зависимости от того, какое из приведенных условий имеет место, первое или второе, будем говорить соответственно о согласованной или несогласованной допустимой дуге из и в v.
Метод увеличивающих цепей Будем говорить, что дуга е сети S является допустимой дугой из и в v

Слайд 26Увеличивающей цепью (длины l) для данного потока f из s

в t называется произвольная последовательность (попарно различных) вершин и дуг
v0,

e1, v1, e2,v2, …, vl–1, el, vl,
такая что v0 = s, vl = t, и для каждого i  l дуга ei допустима из vi–1 в vi относительно потока f.
Знание увеличивающей цепи позволяет легко увеличить величину потока f на  = min{(ei): 1  i  l}, где
Увеличивающей цепью (длины l) для данного потока f из s в t называется произвольная последовательность (попарно различных)

Слайд 27Для этого достаточно увеличить на  поток по каждой согласованной

дуге ei:
а также уменьшить на  поток по каждой несогласованной

дуге ei:

Для дуг е, не принадлежащих цепи полагаем f'(e)=f(e). Величина же потока увеличивается на :
W (f') = Divf’(s) = Divf(s) + = W (f') + .

Для этого достаточно увеличить на  поток по каждой согласованной дуге ei:а также уменьшить на  поток

Слайд 28 Увеличивающая цепь имеет вид
v1, v1, v3,

v3, v2, v3, v2, v5, v2, v5, v5, v6, v6,

v7, v6, v7, v7, v8, v8,
что дает увеличение потока на  = 1 с 10 до 11.
Увеличивающая цепь имеет вид  v1, v1, v3, v3, v2, v3, v2, v5, v2, v5,

Слайд 29Теорема 3. Следующие три условия эквивалентны:
(а) Поток из s в

t максимален.
(б) Не существует увеличивающей цепи для f.
(в) W(f) =

c(A, V\A) для некоторого А  V, такого что s  A, t  A.
Теорема 3. Следующие три условия эквивалентны:(а) Поток из s в t максимален.(б) Не существует увеличивающей цепи для

Слайд 30Доказательство
(а)  (б). Если поток максимален, то очевидно, что для

него не существует увеличивающей цепи, ибо существование такой цепи делало

бы возможным увеличение потока.
(б)  (в). Предположим, что для некоторого потока f не существует увеличивающей цепи. Определим множество А  V как множество вершин v, для которых существует цепь
v0, e1, v1, e2,v2, …, vk–1, ek, vk
такая что k  0, v0 = s, vk = v и еi — дуга, допустимая из vi-1 в vi, 1 i  k. Очевидно, что s  A, а t  А, поскольку это означало бы существование увеличивающей цепи для f. Рассмотрим разрез Р(А). Для каждой дуги е  Р(А) должно выполняться равенство f(e) = c(e) согласно определению множества А, таким образом, f(A, V\A) = c(A, V\A). Пользуясь определением множества А, аналогичным образом получаем f(V\A, A) = 0. В силу леммы 1 отсюда вытекает, что
W(f) = f(A, V \A) – f(V \A, A) = c(A, V\A).
(в)  (а) следует из уже доказанного факта, что величина произвольного потока не превосходит с (A, V\A)
Доказательство(а)  (б). Если поток максимален, то очевидно, что для него не существует увеличивающей цепи, ибо существование

Слайд 31Алгоритм построения максимального потока
Идея метода: начиная с произвольного потока

(например, f(e) = 0 для каждой дуги е  Е), мы ищем

увеличивающие цепи и увеличиваем вдоль них фактический поток.
1) Закончится ли работа такого алгоритма через конечное число шагов?
2) Будет ли полученный поток максимальным?
Алгоритм построения максимального потока Идея метода: начиная с произвольного потока (например, f(e) = 0 для каждой дуги

Слайд 32Ответ на второй вопрос будет утвердительным, что непосредственно следует из

теоремы 3.
Форд и Фалкерсон дали в некотором смысле отрицательный

ответ на первый вопрос. А именно, они привели пример сети, в которой можно так «злоумышленно» подбирать очередные рассматриваемые увеличивающие цепи, что процесс никогда не кончится; более того, величина потока в течение всего времени будет меньше одной четверти величины максимального потока.
Ответ на второй вопрос будет утвердительным, что непосредственно следует из теоремы 3. Форд и Фалкерсон дали в

Слайд 35Алгоритм Эдмондса и Карпа
Эдмондс и Карп показали, что если

мы увеличиваем фактический поток всегда вдоль кратчайшей увеличивающей цепи, то

максимальный поток строится с использованием не более mn/2 цепей.
Отыскание кратчайшей цепи легко реализовать при помощи алгоритма, аналогичного поиску в ширину. Точнее говоря, начиная от источника s, мы ведем поиск в ширину в графе Gf, состоящем из дуг u, v, таких что в нашей сети существует дуга, допустимая от и до v относительного фактического потока f, вплоть до момента достижения стока t. Очевидно, что найденный в результате этого процесса кратчайший путь из s в t соответствует кратчайшей увеличивающей цепи из s в t в исходной сети. Принимая во внимание, что процесс поиска в ширину мы можем выполнить за время О(m + п), мы можем оценить сложность всего алгоритма построения максимального потока как О(тn(m + п)).
Алгоритм Эдмондса и Карпа Эдмондс и Карп показали, что если мы увеличиваем фактический поток всегда вдоль кратчайшей

Слайд 36Алгоритм для построения максимального потока Диница
Этот метод основан на

построении некоторой вспомогательной бесконтурной сети, структура которой точно отображает все

кратчайшие увеличивающие цепи из s в t относительно фактического потока f. Обозначим такую сеть через Sf. Мы строим ее при помощи поиска в ширину в уже упомянутом графе Gf с дугами, определяемыми допустимыми относительно фактического потока f дугами в исходной сети. Сеть Sf содержит источник s, сток t и дуги графа Gf вида , где и находится на расстоянии d, a v на расстоянии d + 1 от s, 0  d  l, где l есть длина сети Sf, т. е. расстояние от s до t в графе Gf. Пропускную способность cf(u, v) мы определяем как c(u,v) – f(u,v) или как f(v, u) в зависимости от того, представляет ли дуга согласованную дугу или нет (или сумму этих значений), если одновременно существуют согласованная и несогласованная дуги, допустимые от и к v.
Алгоритм для построения максимального потока Диница Этот метод основан на построении некоторой вспомогательной бесконтурной сети, структура которой

Слайд 371 procedure PSA; (* построение вспомогательной бесконтурной сети Sf; переменные

V, XV, ПРЕДШ, ЗАПИСЬ, ХПРЕДШ, ХЗАПИСЬ, ДЛИНА, С, F, ХС,

XF, s, t — глобальные *)
2 begin
3 for u  V do (* инициализация *)
4 begin ДЛИНА [и] := ; ХПРЕДШ [и] := ;
ХЗАПИСЬ[и]:= ;
5 for v  V do ХС [и, v] := 0;
6 for v  V do XF [u, v] := 0 (*инициализация нулевого потока*)
7 end;
8 ОЧЕРЕДЬ := ; XV := ; ДЛИНА [s] := 0;
(*поиск в ширину, начиная от источника s*)
9 ОЧЕРЕДЬ  s;
10 while ОЧЕРЕДЬ   do
11 begin u  ОЧЕРЕДЬ; XV := XV  {u};
12 for v  ЗАПИСЬ [и] do (*поиск согласованных дуг*)
13 if (ДЛИНА [и] < ДЛИНА [v]  ДЛИНА [t]) and (F [и, v] < С [и, v]) then
14 begin if ДЛИНА[и] =  then ОЧЕРЕДЬ  v; (*v — новая*)
15 ДЛИНА[v] := ДЛИНА[и] + 1;(*добавить к сети Sf*)
16 ХЗАПИСЬ[и] := ХЗАПИСЬ[и]  {v};
17 ХПРЕДШ [v] := ХПРЕДШ[v]  {u};
18 ХС[и, v] := С[и, v] – F[и, v]
19 end;
20 for v  ПРЕДШ[и] do (*поиск несогласованных дуг*)
21 if (ДЛИНА[и] < ДЛИНА[v]  ДЛИНА [t]) and (F[v, и] > 0) then
22 begin if ДЛИНА[v] =  then ОЧЕРЕДЬ  v; (* новый *)
23 ДЛИНА [v] := ДЛИНА[и] + 1;
24 if XC[и, v] = 0 then (* добавить к сети Sf *)
25 begin ХЗАПИСЬ[и] : = ХЗАПИСЬ[и]  {v};
26 ХПРЕДШ[v] := ХПРЕДШ[v]  {u};
27 end;
28 ХС[и, v] := XС[и, v] + F[и, v]
29 end
30 end
31 end
1 procedure PSA; (* построение вспомогательной бесконтурной сети Sf; переменные V, XV, ПРЕДШ, ЗАПИСЬ, ХПРЕДШ, ХЗАПИСЬ, ДЛИНА,

Слайд 38Эффективный алгоритм построения псевдомаксимального потока во вспомогательной бесконтурной сети (Малхотри,

Кумара и Махешвари)

Эффективный алгоритм построения псевдомаксимального потока во вспомогательной бесконтурной сети (Малхотри, Кумара и Махешвари)

Слайд 39Данные: Сеть, представленная списками инцидентности
ПРЕДШ [v], ЗАПИСЬ[v], v  V,

пропускные способности c[u, v], и, v  V, источник s

 V и сток t  V. Результаты: Максимальный поток F[u, v], и, v  V.
1 begin
2 for u  V do
3 for v  V do F[и, v] := 0; (* нулевой начальный поток *)
4 repeat PSA; (*построение вспомогательной бесконтурной сети*)
5 if ДЛИНА[t]   then (* поток F не является максимальным *)
begin MAXPSA; (*построение максимального потока
во вспомогательной сети*)
(*перенести поток из вспомогательной сети в главную*)
for u  XV do (*XV = множество вершин вспомогательной
сети*)
8 for v  XV do
9 begin F[u, v] := F[u, v] – XF[u, v];
10 if F[u, v] > C[u, v] then
11 begin
F[v, u] := F[v, u] – (F[u, v] – C[u, v]);
12 F[u, v] := C[u, v]
13 end
14 end
15 end (* конец фазы*)
16 until ДЛИНА[t] =  (* поток F – максимальный *)
17 end
Данные: Сеть, представленная списками инцидентностиПРЕДШ [v], ЗАПИСЬ[v], v  V, пропускные способности c[u, v], и, v 

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

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

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

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

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


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

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