Алгоритмы и структуры данных 12. Потоки (1). Форд-Фалкерсон и Эдмондс-Карп

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 21 апреля 2022 года
Лектор: Степанов Илья Даниилович
Оператор: Жулябина Ирина
Монтаж: Жильцов Игорь

0:00 - Потоки. Мотивация, пример. Пример сечения
2:46 - Сеть, поток, остаточная сеть - определения
11:37 - Пример. Мотивация рассмотрения остаточной сети
14:40 - Как обрабатывать противонаправленные рёбра (warning: наличие противонаправленных рёбер создает некоторые трудности, например на 29-20)
15:29 - Упрощённая формулировка теоремы Форда-Фалкерсона
19:09 - Ещё определения: разрез, его величина, величина потока через него
21:24 - Лемма 1. |f| = f(S, T)
31:47 - Лемма 2. |f| ≤ c(S, T)
33:49 - Теорема Форда-Фалкерсона, полная формулировка
35:28 - 1) ⇒ 2)
36:37 - 2) ⇒ 3)
39:56 - 3) ⇒ 1)
41:57 - Алгоритм Форда-Фалкерсона
44:38 - Примеры. Граф, на которых время работы слишком велико
48:20 - Асимптотика
49:36 - Алгоритм Эдмондса-Карпа. O(FE) → O(VE^2)
51:35 - Пример
52:26 - Корректность (очев.)
52:56 - Док-во асимптотики. Лемма 1. Проталкивание потока не сокращает расстояние от S до произвольной V
1:05:02 - Лемма 2. Произвольное ребро насыщается O(V) раз
1:13:22 - Непосредственное док-во асимптотики
1:15:45 - Типично, что на практике Эдмондс-Карп работает ещё быстрее
1:16:44 - Кайфовая задача
1:19:44 - Как максимальные потоки помогают искать какие-то минимумы?
1:20:39 - Кайфовое решение