Изменения
Нет описания правки
# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
# Сформулируйте и докажите аналогичную лемме о сумме лемму о разности потоков.
# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.
# Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.
# Если выбирать путь с максимальным $C_{min}$, то время работы ФФ будет $O(polynom(V, E) \log(C_{max}))$. Докажите это.
# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.
# Доказать, что величину потока можно представить в виде $\sum{c_{i} f_{p_{i}}}$ + $\sum{d_{j} f_{k_{j}}}$ , где $p_i$ - путь из $s$ в $t$, $k_j$ - цикл, $c_i$ и $d_j$ - константы.
# Доказать теорему о декомпозиционном барьере. (см. вики-конспекты)
# Поток назовём циркуляцией, если его величина равна $0$. Рассмотрим граф $G$ такой, что $ \forall uv \in E : L_{uv} \le f_{uv} \le R_{uv} $. Свести поиск допустимой циркуляции к задаче о макс. потоке.
# Пусть есть $k$ истоков и $m$ стоков. Свести задачу к задаче о максимальном потоке.
# Пусть у вершин тоже будет пропускная способность. Свести задачу к задаче о максимальном потоке.
# Альтернативная реализация масштабирования потока $-$ на каждом шаге рассматриваем рёбра с пропускной способностью $c \ge 2^{k-i}$. Доказать, что для такой реализации время работы $O(EEk)$.
# $f_{max}$ - макс. поток, $f_{blocking}$ - блокирующий поток. Доказать, что $\frac {|f_{blocking}|} { |f_{max}|} $ может быть сколь угодно мало.
# Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $O(E V k)$.
# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций while в алгоритме Диница равно $O(V^{\frac{2}{3}} {c_{max}}^{\frac{1}{3}})$.
# Доказать, что на графе с целочисленными пропускными способностями рёбер число итераций алгоритма Диница равно $O(V^{\frac{1}{2}} * c(G)^{\frac{1}{2}})$.
