Семинар 12. Потоки минимальной стоимости
Алгоритмы и структуры данных, часть 2


Что: Семинар
Когда: Суббота, 05 мая 2018, 16:20–17:40
Где: НГУ, ауд. 2128

Описание

Сеть с стоимостями (кососимм.). Постановки задачи о потоке мин. стоимости.

Остаточная сеть. Лемма о разности потоков и ост. сети. Лемма о разложении потока на пути и циклы. Критерий оптимальности потока (через цикл отр. веса). Теорема Форда-Фалкерсона (проталкивание вдоль пути мин. стоимости).

Оптимальный поток нулевой величины (отсутствие циклов отр. веса). Решение задачи методом Форда-Фалкерсона.

Алгоритм решения за O(F x VE). Использование алгоритма Дейкстры с потенциалами. Нулевой текущий вес появляющихся в ост. сети рёбер. Алгоритм за O(F x ElogV).

Задачи о паросочетаниях: макс. и мин. стоимости. Сведение к поиску потока.

Видео