Теорема Менгера: как найти максимальное число рёберно-непересекающихся путей между двумя вершинами?
Задача: между $s$ и $t$ найти максимум путей, которые не используют одно и то же ребро дважды (рёберно-непересекающиеся). Слышал, что это связано с теоремой Менгера и потоком. Как именно свести и какая будет асимптотика?
2 ответа
Теорема Менгера (рёберная форма): максимальное число рёберно-непересекающихся путей между $s$ и $t$ равно минимальному числу рёбер, удаление которых разъединяет $s$ и $t$ (минимальному рёберному разрезу).
Сведение к потоку. Присваиваем каждому ребру пропускную способность 1 и считаем максимальный поток из $s$ в $t$. Поскольку все пропускные единичные, каждый «единичный поток» = один путь, и они автоматически не делят рёбер. Значение потока = число путей.
for(auto&[u,v]:edges) add_edge(u, v, 1); // ориентированный случай
int paths = maxflow(s, t);
Для неориентированного графа ребро ${u,v}$ моделируется двумя ориентированными $u\to v$ и $v\to u$, каждое пропускной 1 (или одним ребром cap=1 в обе стороны — зависит от реализации остаточной сети).
Асимптотика: на единичных пропускных Диниц даёт $O(E\sqrt{E})$ (а для разреженных — фактически очень быстро). min-cut величины $k$ ⟺ ровно $k$ путей.
Восстановление самих путей: после maxflow ищем пути жадным DFS по рёбрам с пущенным потоком (где течёт 1), удаляя использованные рёбра. Получите ровно paths путей.
Важно различать рёберную и вершинную версии Менгера:
- Рёберно-непересекающиеся пути → пропускная 1 на рёбрах (как выше).
- Вершинно-непересекающиеся пути (не делят промежуточных вершин) → нужно расщепление вершин: каждую внутреннюю вершину дублируем с внутренним ребром пропускной 1, и считаем поток. Тогда max число вершинно-непересекающихся путей = минимальное число вершин, разъединяющих $s$ и $t$.
Это частая ловушка: задача просит вершинно-непересекающиеся, а человек ставит cap=1 только на рёбра и получает завышенный ответ.