Презентация Сети и потоки онлайн

Содержание слайда: Сети и потоки

Содержание слайда: Сеть: - подсистема, транспортирующая некий продукт из одной точки в другую. Пример – нефтепровод, электропровод. - ориентированный граф, ребра которого - трубы между точками системы (вершинами графа). Каждому ребру e = (vi, vj ) соответствует положительное целое число с(e), называемое пропускной способностью e. Если между двумя вершинами не существует ребра, то пропускную способность полагаем равной нулю. У нефтяных сетей пропускная способность – количество нефти, проходящей через трубу (ребро).

Содержание слайда: Сеть. Наличие петель у графа недопустимо. Если существует ребро из vi и vj , то нет ребра из vj и vi . (поток продукта только в одну сторону). Ориентированный граф должен быть связным. Тогда граф называется простым связным ориентированным графом. Особая вершина а, называемая источником. Особая вершина z, называемая стоком. Степень выхода вершины а = 0, так что в источнике ничто не втекает. Степень выхода вершины z = 0, так что из стока ничто не вытекает. Продукт перевозится из а и имеет место назначения z.

Содержание слайда: Определение. Сеть – это ориентированный граф (G, V, E) вместе с весовой функцией C: E  N и выделенными вершинами a, z , такими, что indeg(a) = 0; outdeg(z) = 0 . Например, граф является примером сети, где числа на каждом ребре означают пропускную способность.

Содержание слайда: Поток. Для каждого ребра e имеется значение f(e) , которое является потоком через конкретное ребро (трубу). Величина потока не может превысить пропускную способность трубы. Поток, входящий в вершину, был равен потоку, выходящему из вершины, за исключением вершин a и z - сохранение потока. Пусть in(v) – множество ребер, для которых v – конечная вершина. out(v) – множество ребер, начальная вершина. out(v) – множество ребер, выходящих из вершины v , in(v) – множество ребер, входящих в вершину v .

Содержание слайда: Определение. Поток в сети – это функция f : E  N  {0} такая, что (1) (2)

Содержание слайда: Принцип сохранения потока. Поток из а равен потоку в z , т.е. поток (а) = поток (z)

Содержание слайда: Пример.

Содержание слайда: Пример (продолжение).

Содержание слайда: Пример (продолжение) .

Содержание слайда: Теорема. Для любого фиксированного потока f Следствие. Пусть S - подмножество множества V, содержащее а , но не содержащее z , и T = V – S . Тогда

Содержание слайда: Определения. Величина потока f , обозначаемая val(f) , равна поток(а) = поток(z) . Пусть S - подмножество множества V и T = V – S. Тогда {e : e (S, T)} называется сечением. Если а  S и z  T , то сечение называется a – z сечением. Величина C(S, T) = e(S, T) называется пропускной способностью сечения.

Содержание слайда: Определения. Поток f * в сети называется максимальным потоком, если val(f *)  val(f) для любого потока f в сети. a – z сечение (S, T) называется минимальным сечением, если C(S, T) не больше пропускной способности любого другого a – z сечения. Теорема. Пусть S – подмножество множества V , содержащее а , но не содержащее z , и T = V – S . Тогда val(f)  C(S, T) . Доказательство:

Содержание слайда: Следствия. Если val(f) = C(S, T) для некоторого потока f , а a – z сечения (S, T) , то f – максимальный поток, а С – минимальное сечение. Для некоторого потока f и a – z сечения (S, T) равенство val(f) = С(S, T) имеет место тогда и только тогда, когда f(e) = c(e) для всех e  (S, T) и f(e) = 0 для всех e  (S, T) .

Содержание слайда: Способ определения максимального потока сети. Рассмотрим сеть Максимальный поток (не обязательно единственный) легко найти способом

Содержание слайда: Пример. Сеть Кажется, что у этой сети максимальный поток, т.к. не существует ориентированного пути, по которому можно увеличить поток. Однако сеть имеет больший поток (максимальный):

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

Содержание слайда: Как находить максимальные в смысле потока сети? Сформируем пути из a в z , не обращая внимания на направление ребер. Такие пути называют цепями. Сеть Одним и таких путей будет

Содержание слайда: Как находить максимальные в смысле потока сети? Нет возможности увеличить поток по этому пути, т.к. ребро из b в с наполнено до его пропускной способности. То же для цепи Цепь Если увеличить поток на 2 для стрелок, ииеющих то же направление, что и цепь, и уменьшить поток на 2 для стрелок, имеющих противоположное направление, получится поток увеличивается в 2 раза.

Содержание слайда: Возникли вопросы. 1) Почему выбираем 2? Очевидно – поток желательно увеличить как можно больше. Но не превысить пропускную способность ни одного из заданных ребер. Если ребро имеет направление, противоположное цепи, нельзя увеличить поток через это ребро более, чем на текущую величину потока через него, иначе получится отрицательный поток. Поэтому, если бы не было других ограничений ограничило бы изменение потока до 4.

Содержание слайда: Возникли вопросы. 2) Как это влияет на сохранение потока? Рассмотрим изменение на Поток, выходящий из вершины b, увеличен на ту же самую величину, что и поток, входящий в вершину b. Поэтому чистый поток через b остается прежним. При изменении на поток из вершины b в вершину e увеличен на ту же величину, на которую уменьшен поток из вершины d в вершину e , поэтому чистый поток в вершине e остался тем же.

Содержание слайда: Продолжене. Рассмотрим изменение на Поток из d в e уменьшен на ту же величину, на которую увеличен поток из d в с. Поэтому чистый поток вершины d остался неизменным. Процесс увеличения потока в сети. Формируем цепь из а в z . Если возможно, то увеличиваем поток, определяя наибольшую величину, которую можно добавить к каждому из ребер, имеющих то же самое направление, что и цепь, чтобы поток не превысил пропускную способность, и которую можно вычесть из каждого ребра, имеющего противоположное направление, не создавая отрицательный поток. Поскольку последнее ребро, входящее в z , имеет то же направление, что и цепь, то поток в z возрастает.

Содержание слайда: C какого потока начать?

Содержание слайда: Нахождение максимального потока.

Содержание слайда: Пример. Найти максимальный поток для сети Шаг 1

Содержание слайда: Пример (продолжение). Шаг 2 – проверяем, не пусто ли множество S и выбираем вершину а. Шаг 3 – полагаем резерв вершины b равным min(7, ) = 7. Устанавливаем вершину а в качестве предшественника вершинв=ы b. Шаг 4 не применяем, возвращаемся в шагу 2.

Содержание слайда: Пример (продолжение).

Содержание слайда: Пример (продолжение).

Содержание слайда: Пример (продолжение).

Содержание слайда: Теорема. Алгоритм максимального потока строит максимальный поток для сети. Теорема. Поток f на заданной сети N является максимальным тогда и только тогда, когда существует сечение (S, T) такое, что val(f) = C(S, T).

Содержание слайда: !!.