ребру (u,v)E которого поставлено в соответствие число c(u,v) 0,
называемое пропускной способностью ребра. В случае (u,v)E, полагаем c(u,v)=0.В графе выделены 2 вершины: источник s и сток t.
Граф связен, т.е. .
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Потоки в сетях
Содержание
- 1. Потоки в сетях
- 2. Пусть дана сеть G=(V,E), пропускная способность которой
- 3. Величина потока определяется как сумма потоков по
- 4. Задача о максимальном потоке:Найти максимально возможную скорость
- 5. Вершину сети v , для которой deg-(v)>0
- 6. Поток через даннуюсетьСеть
- 7. Назовём разрезом сети G=(V, E) разбиение множества
- 8. Минимальным разрезом называется разрез наименьшей пропускной способности
- 9. Теорема Форда-Фалкерсона:Во всякой сети величина максимального потока
- 10. Идея алгоритма состоит в нахождении сквозных путей
- 11. В результате каждое ребро будет иметь остаточную
- 12. Для всех рёбер (i,j) положить остаточную пропускную
- 13. Определить множество Si, как множество узлов j,
- 14. Если последней меткой помечен узел стока (k=n),
- 15. (Определение остаточной сети). Обозначим через множество узлов,
- 16. Остаточные пропускные способности рёбер, составляющих сквозной путь,
- 17. (Решение).При m найденных сквозных путях максимальный поток
- 18. Положим Если >0, то поток, проходящий через
- 19. Скачать презентанцию
Пусть дана сеть G=(V,E), пропускная способность которой задаётся функцией с. Потоком в сети G назовём функцию обладающую следующими свойствами:Ограничение, связанное с пропускной способностью:
Слайды и текст этой презентации
Слайд 1 Потоки в сетях
Сетью называется ориентированный граф G=(V,E), каждому
В графе выделены 2 вершины: источник s и сток t.
Граф связен, т.е. .
Слайд 2Пусть дана сеть G=(V,E), пропускная способность которой задаётся функцией с.
Потоком в сети G назовём функцию
обладающую следующими свойствами:
Ограничение, связанное с
пропускной способностью: для всех u,v изV; Косо симметричность: для всех u,v из V;
Сохранение потока: для всех u из V - {s,t}.
Слайд 3Величина потока определяется как сумма потоков по всем рёбрам выходящим
из истока.
Дан ориентированный граф.
Будем рассматривать его как сеть
труб, по которым некоторое вещество движется от источника к стоку. Веса на рёбрах - пропускная способность трубы. 
Слайд 4Задача о максимальном потоке:
Найти максимально возможную скорость производства (и потребления)
вещества, при которой его ещё можно доставить от истока к
стоку при данных пропускных способностях труб.Или
для данной сети G с истоком s и стоком t найти поток максимальной величины.
Слайд 5Вершину сети v , для которой deg-(v)>0 (полустепень исхода) и
deg+(v)=0 (полустепень захода) будем называть источником, а вершину w, для
которой deg+(w)>0 и deg–(w)=0 – стоком.Поток называется максимальным, если он имеет наибольшую величину (среди всех потоков через данную сеть).
Слайд 7Назовём разрезом сети G=(V, E) разбиение множества V на две
части S и T=V \ S, для которых sS и
tT.Пропускной способностью разреза (S,T) называют сумму пропускных способностей, пересекающих разрез рёбер.
Для заданного потока f величина потока через разрез (S,T) определяется как сумма f(S,T) по пересекающим разрез рёбрам.
Слайд 8Минимальным разрезом называется разрез наименьшей пропускной способности (среди всех разрезов
сети).
S={s, v1, v2} T={v3, v4, t}
При
этом f(S,T) = 12+(-4)+11=19 – поток через разрез
c(S, T) = 12+14=26 – пропускная способность разреза
поток через разрез в отличие от пропускной способности может включать и отрицательные слагаемые
Слайд 9Теорема Форда-Фалкерсона:
Во всякой сети величина максимального потока равна пропускной способности
любого минимального разреза.
(Доказательство к экзамену найти самостоятельно).
Слайд 10Идея алгоритма состоит в нахождении сквозных путей с положительными потоками
от источника к стоку.
Рассмотрим ребро
, с начальнойпропускной способностью .
В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро.
Слайд 11В результате каждое ребро будет иметь остаточную пропускную способность.
(cij, cji)
– остаточная пропускная способность .
Сеть, где все рёбра имеют остаточную
пропускную способность называется остаточной.Для произвольного узла j, получающего поток от узла i, определим метку [aj, i], где aj – величина потока между узлами.
Слайд 12Для всех рёбер (i,j) положить остаточную пропускную способность равной первоначальной:
Назначим
a1= и пометим узел 1 меткой [ ,-].
Полагаем i=1.
Алгоритм Форда-Фалкерсона
нахождения максимального потока
Слайд 13Определить множество Si, как множество узлов j, в которые можно
перейти из i по ребру с положительной остаточной пропускной способностью.
Если Si, выполняем шаг 3, иначе шаг 4.
В множестве Si находим узел k, такой, что
Положим ak=cik и пометим узел k меткой [ak,i].
Слайд 14Если последней меткой помечен узел стока (k=n), сквозной путь найден,
переходим к шагу 5.
Иначе полагаем i=k и возвращаемся к шагу
2.(Откат назад). Если i=1, сквозной путь невозможен, переходим к шагу 6.
Если i1, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем узел i из множества узлов, смежных с узлом r.
Полагаем i=r и возвращаемся к шагу 2.
Слайд 15(Определение остаточной сети).
Обозначим через
множество узлов, через которые проходит
p-й найденный сквозной путь от источника к стоку.
Тогда максимальный поток,
проходящий по этому пути равен:
Слайд 16Остаточные пропускные способности рёбер, составляющих сквозной путь, уменьшаются на fp
в направлении движения потока и увеличиваются на fp в противоположном
направлении.Для ребра (i,j), входящего в сквозной путь, текущие остаточные стоимости будут равны:
, если поток ij;
, если поток j i.
Восстанавливаем все узлы, удалённые на шаге 4. Полагаем i=1. Возвращаемся к шагу 2.
Слайд 17(Решение).
При m найденных сквозных путях максимальный поток вычисляется по формуле:
Имея
значения начальных
и конечных пропускных способностей ребра (i,j) вычисляем оптимальный поток через это ребро.
Слайд 18Положим
Если >0, то поток, проходящий через ребро (i,j), равен
.
Если >0, то поток равен .
Случай, когда одновременно >0 и
>0 невозможен
