Изменения
Нет описания правки
# Сведите задачу о максимальном потоке с несколькими истоками и несколькими стоками к обычной задаче о максимальном потоке.
# Можно ввести понятие пропускной способности вершины $c(u)$ как максимальной разрешенной суммы $\sum_{uv}f(uv)$. Решите задачу о максимальном потоке для графа с пропускными способностями вершин.
# Пусть $f_{max}$ - максимальный поток в сети, а $f_{blocking}$ - блокирующий поток. Доказать, что $|f_{blocking}| / |f_{max}|$ может быть сколь угодно мало.
# Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $O(EVk)$.
# Доказать, что в графе с целочисленными пропускными способностями рёбер число итераций while в алгоритме Диница равно $O(V^{2/3} C_{max}^{1/3})$.
# Доказать, что в графе с целочисленными пропускными способностями рёбер число итераций алгоритма Диница равно $O(V^{1/2} c(G)^{1/2})$, где $c(G)$ есть сумма пропускных способностей всех вершин.
# Пусть $w(uv)$ - стоимость ребра, $c(uv)$ - пропускная способность ребра. Разработать алгоритм построения разреза минимальной средней стоимости. (Отношение суммы стоимостей рёбер дерева к сумме пропускных способностей рёбер разреза должно быть минимальным)
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
# Докажите реберную теорему Менгера: минимальное число ребер, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу реберно непересекающихся путей из $s$ в $t$.
# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).
</wikitex>
