Изменения
Нет описания правки
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
# Альтернативная реализация масштабирования потока $-$ на каждом шаге рассматриваем рёбра с пропускной способностью $c \ge 2^{k-i}$. Доказать, что для такой реализации время работы $O(EEk)$.
# $f_{max}$ - макс. поток, $f_{blocking}$ - блокирующий поток. Доказать, что $\frac {|f_{blocking}|} { |f_{max}|} $ может быть сколь угодно мало.