Изменения

# Докажите вершнинную теорему Менгера: минимальное число вершин, которые необходимо удалить в графе, чтобы из $s$ в $t$ не было пути, равно максимальному числу вершинно непересекающихся путей из $s$ в $t$ ($s$ и $t$ удалять нельзя).

# Глобальным разрезом называется разбиение множества вершин графа на два непустых непересекающихся множества. Сведите задачу о глобальном разрезе к поиску $O(V)$ максимальных потоков.

# Постройте граф, в котором алгоритм Форда-Фалкерсона (ФФ) находит $\Omega(C_{max})$ путей. Веса всех рёбер целочисленные.

# Постройте граф, в котором не будет найден максимальный поток. Веса рёбер вещественные.

# Если выбирать путь с максимальным $C_{min}$, то время работы ФФ будет $O(polynom(V, E) \log(C_{max}))$. Докажите это.

# Постройте граф, в котором алгоритм Эдмондса-Карпа совершить $\Omega(V E)$ дополнений до пути.

# Пусть есть $k$ истоков и $m$ стоков. Свести задачу к задаче о максимальном потоке.

# Пусть у вершин тоже будет пропускная способность. Свести задачу к задаче о максимальном потоке.