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