Потоки в сетях
Определение потока
Пример сети и потока
Теорема о декомпозиции
Дополнительные определения
Свойства
Теорема Форда-Фалкерсона
Алгоритм Форда-Фалкерсона
Реализация
Сложность
Проблемы
Проблемы
Медленное насыщение
Как улучшить?
Проталкивание предпотока
Высота вершины
Неформальная идея
Операции
Операции
Алгоритм (Гольдберг, Тарьян)
Демо:
Формальный алгоритм
Корректность алгоритма
Корректность алгоритма
Корректность алгоритма
Применения
1.92M

Потоки в сетях

1. Потоки в сетях

2.

3.

4. Определение потока

• Сеть G=(V,E) - ориентированный граф,
• Для каждого ребра
English     Русский Rules