Изменения
Нет описания правки
# Доказать, что в графе с целочисленными пропускными способностями рёбер число итераций 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>
