Изменения
Нет описания правки
# Доказать, что если в алгоритме масштабирования использовать алгоритм Диница вместо ФФ, то время работы равно $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)$ - пропускная способность ребра. Будем называть $s$-$t$-разделяющим множество ребер, при удалении которого из графа нет пути из $s$ в $t$. Разработать алгоритм построения $s$-$t$-разделяющего множества ребер минимальной средней стоимости. (Отношение суммы стоимостей рёбер к сумме пропускных способностей рёбер множества должно быть минимальным)
# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.
