Презентация на тему: Потоки в сетях

Потоки в сетях
Потоки в сетях
Потоки в сетях
Задача о максимальном потоке :
Потоки в сетях
Потоки в сетях
Потоки в сетях
Потоки в сетях
Теорема Форда-Фалкерсона:
Потоки в сетях
Потоки в сетях
Алгоритм Форда-Фалкерсона нахождения максимального потока
Потоки в сетях
Потоки в сетях
Потоки в сетях
Потоки в сетях
Потоки в сетях
Потоки в сетях
1/18
Средняя оценка: 4.3/5 (всего оценок: 60)
Код скопирован в буфер обмена
Скачать (129 Кб)
1

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

Сетью называется ориентированный граф G =( V, E ), каждому ребру ( u, v )  E которого поставлено в соответствие число c ( u, v )  0, называемое пропускной способностью ребра. В случае ( u, v )  E, полагаем c ( u, v )=0. В графе выделены 2 вершины: источник s и сток t. Граф связен, т.е..

Изображение слайда
2

Слайд 2

Пусть дана сеть G =( V, E ), пропускная способность которой задаётся функцией с. Потоком в сети G назовём функцию обладающую следующими свойствами: Ограничение, связанное с пропускной способностью: для всех u, v из V ; Косо симметричность: для всех u, v из V ; Сохранение потока: для всех u из V - { s, t }.

Изображение слайда
3

Слайд 3

Величина потока определяется как сумма потоков по всем рёбрам выходящим из истока. Дан ориентированный граф. Будем рассматривать его как сеть труб, по которым некоторое вещество движется от источника к стоку. Веса на рёбрах - пропускная способность трубы.

Изображение слайда
4

Слайд 4: Задача о максимальном потоке :

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

Изображение слайда
5

Слайд 5

В ершину сети v, для которой deg - (v) > 0 ( полустепень исхода) и deg + (v)=0 (полустепень захода) будем называть источником, а вершину w, для которой deg + (w) > 0 и deg – (w)=0 – стоком. Поток называется максимальным, если он имеет наибольшую величину (среди всех потоков через данную сеть).

Изображение слайда
6

Слайд 6

Поток через даннуюсеть Сеть

Изображение слайда
7

Слайд 7

Назовём разрезом сети G =( V, E ) разбиение множества V на две части S и T = V \ S, для которых s  S и t  T. Пропускной способностью разреза ( S, T ) называют сумму пропускных способностей, пересекающих разрез рёбер. Д ля заданного потока f величина потока через разрез ( S, T ) определяется как сумма f ( S, T ) по пересекающим разрез рёбрам.

Изображение слайда
8

Слайд 8

Минимальным разрезом называется разрез наименьшей пропускной способности (среди всех разрезов сети). S={s, v 1, v 2 } T={v 3, v 4, t} При этом f(S,T) = 12+(-4)+11=19 – поток через разрез c(S, T) = 12+14=26 – пропускная способность разреза поток через разрез в отличие от пропускной способности может включать и отрицательные слагаемые

Изображение слайда
9

Слайд 9: Теорема Форда-Фалкерсона:

Во всякой сети величина максимального потока равна пропускной способности любого минимального разреза. (Доказательство к экзамену найти самостоятельно).

Изображение слайда
10

Слайд 10

Идея алгоритма состоит в нахождении сквозных путей с положительными потоками от источника к стоку. Рассмотрим ребро, с начальной пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро.

Изображение слайда
11

Слайд 11

В результате каждое ребро будет иметь остаточную пропускную способность. ( c ij, c ji ) – остаточная пропускная способность. Сеть, где все рёбра имеют остаточную пропускную способность называется остаточной. Для произвольного узла j, получающего поток от узла i, определим метку [a j, i], где a j – величина потока между узлами.

Изображение слайда
12

Слайд 12: Алгоритм Форда-Фалкерсона нахождения максимального потока

Для всех рёбер ( i,j ) положить остаточную пропускную способность равной первоначальной: Назначим a1=  и пометим узел 1 меткой [,-]. Полагаем i =1. Алгоритм Форда-Фалкерсона нахождения максимального потока

Изображение слайда
13

Слайд 13

Определить множество S i, как множество узлов j, в которые можно перейти из i по ребру с положительной остаточной пропускной способностью. Если S i , выполняем шаг 3, иначе шаг 4. В множестве S i находим узел k, такой, что Положим a k =c ik и пометим узел k меткой [a k,i].

Изображение слайда
14

Слайд 14

Если последней меткой помечен узел стока ( k=n ), сквозной путь найден, переходим к шагу 5. Иначе полагаем i=k и возвращаемся к шагу 2. (Откат назад). Если i=1, сквозной путь невозможен, переходим к шагу 6. Если i  1, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся к шагу 2.

Изображение слайда
15

Слайд 15

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

Изображение слайда
16

Слайд 16

Остаточные пропускные способности рёбер, составляющих сквозной путь, уменьшаются на f p в направлении движения потока и увеличиваются на f p в противоположном направлении. Для ребра ( i,j ), входящего в сквозной путь, текущие остаточные стоимости будут равны: , если поток i j ; , если поток j i. Восстанавливаем все узлы, удалённые на шаге 4. Полагаем i=1. Возвращаемся к шагу 2.

Изображение слайда
17

Слайд 17

(Решение). При m найденных сквозных путях максимальный поток вычисляется по формуле: Имея значения начальных и конечных пропускных способностей ребра ( i,j ) вычисляем оптимальный поток через это ребро.

Изображение слайда
18

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

Положим Если  >0, то поток, проходящий через ребро (i,j), равен . Если  > 0, то поток равен . Случай, когда одновременно  >0 и  > 0 невозможен

Изображение слайда