Алгоритмы поиска блокирующего потока

Определение:
Блокирующий поток —это поток $f$ в сети $G$, что в данной сети $G$ не существует увеличивающего пути (при этом в сети $G_f$ такой путь может существовать, то есть блокирующий поток не обязательно максимален)

Довольно часто (алгоритм Диница) необходимо находить блокирующий поток в ациклической сети, ниже будут приведены несколько алгоритмов, которые это делают.

Жадный алгоритм

Название говорит само за себя, будем жадно пускать поток вдоль произвольного увеличивающего пути в сети $G$. Данный алгоритм чем то похож на Алгоритм Форда-Фалкерсона, но в отличие от него мы не строим остаточную сеть, а всегда ищем увеличивающие пути в исходной сети $G$.

При пускании потока вдоль любого пути из нашей сети $G$ пропадет хотя бы одно ребро (насыщенное потоком) и при этом новых рёбер появится не может (они появляются в остаточной сети $G_f$, а не в $G$), а значит после не более $E$ итераций $t$ станет не достижимым из $s$, а значит наш поток $f$ - блокирующий. Один путь мы ищем с помощью $dfs$, за $O(E)$, следовательно время работы данного алгоритма - $O(E^2)$.

Удаляющий обход

В жадном алгоритме мы совершали много лишних действий. Будем делать то же самое, но теперь если не получилось найти увеличивающий путь пройди по ребру, то это ребро можно удалить, т.к. на любом пути содержащем это ребро точно будет насыщенное потоком.

Оценим время работы. Когда мы просматриваем ребро мы либо удалим его в дальнейшем, либо будет найден увеличивающий путь содержащий это ребро. Каждое ребро удаляется не более одного раза, следовательно удалений $O(E)$. Как было сказано в жадном алгоритме понадобиться найти O(E) путей, а так как мы ищем простые пути их длинна $O(V)$, следовательно мы просматриваем $O(VE + E) = O(VE)$. Число совершенных действий равно числу просмотренных рёбер, следовательно время работы алгоритма $O(VE)$.

Реализация удаляющего обхода

 1 // ptr[v] - номер первого не удалённого ребра
 2 // dist[v] - расстояние от истока
 3 
 4 int dfs(int v, int min_capacity) { 
 5     if (v == T) {
 6         return min_c;
 7     }
 8     for (int i = ptr[v]; i < (int)g[v].size(); ++i) { 
 9         int u = g[v][i];
10         if (edges[u].get_capacity() == 0) {
11             ++ptr[v]; // ребро отсутствует в остаточной сети, так что удалим его
12             continue;
13         }
14         if (dist[edges[u].v] != dist[v] + 1) {
15             ++ptr[v]; // ребро отсутствует в слоистой сети, так что удалим его
16             continue;
17         }
18         int x = dfs(edges[u].v, min(min_c, edges[u].get_capacity()));
19         if (x) { // нашли увеличивающий путь, по которому можно пустить x потока
20             edges[u].flow += x;
21             edges[u ^ 1].flow -= x;
22             return x;
23         }
24         ++ptr[v]; // перейдя по ребру увеличивающий путь не был найден, так что удалим его
25     }
26     return 0;
27 }
28 
29 void find_blocked_flow() {
30     fill(ptr, ptr + N, 0);
31     while (dfs(S, INF)) {}
32 }

Алгоритм Малхотры — Кумара — Махешвари

Данный алгоритм скорее всего никто не будет писать, он просто красивый и с ним Алгоритм Диница просто летает.

Для каждой вершины $v$ введем:

• потенциал на вход: $p_{in}(v) = \sum\limits_{u \in V}{c(u, v)}$,
• потенциал на выход: $p_{out}(v) = \sum\limits_{u \in V}{c(v, u)}$,
• потенциал: $p(v) = min(p_{in}(v), p_{out}(v))$,

при этом $p_{in}(s) = \infty$ и $p_{out}(t) = \infty$.

Потенциал вершины $-$ это количество потока, которое может протекать через вершину и равно минимуму из количества, которое может втекать($p_{in}$), и которое может вытекать($p_{out}$).

Схема алгоритма:

1. Если есть вершина $v$, что $p(v) = 0$, удалим её из сети, т.к. очевидно, что поток через неё течь не может. При удалении вершины пропадают все инцидентные ей ребра и для некоторых вершин нужно пересчитать $p_{in}$ или $p_{out}$ и, возможно, рекурсивно их удалить.
2. Теперь, если сток недостижим из истока, то очевидно, что блокирующий поток найден.
3. Возьмем вершину $v$ с минимальным $p(v)$. $p(v) > 0$, т.к. иначе мы бы удалили её на предыдущем шаге.
4. Пустим из этой вершины $p(v)$ единиц потока в сток и в исток.
5. Перейдем к первому шагу алгоритма.

Рассмотрим подробнее процесс пускания потока в сток на 4 шаге:

1. Введем избыток потока вершины, скажем, что у нашей вершины $v$ избыток потока равен $p(v)$, а у всех остальных избыток равен 0.
2. Из всех вершин с ненулевым избытком потока выберем вершину $v$, идущую в топологической сортировке раньше.
3. Из данной вершины пустим избыточный поток по ребрам, исходящим из неё, сделать это всегда можно, т.к. стартовая вершина обладала минимальным потенциалом, а значит $p_{out}$ любой другой не меньше. Когда пускаем поток по ребру $(v, u)$, уменьшаем избыток $v$ и увеличиваем избыток $u$, суммарный избыток всех вершин сохраняется.
4. Повторяем с первого пункта, пока в нем не будет выбран сток. Так как каждый раз положение выбираемой вершины в топологической сортировке строго увеличивается, а последняя в ней - сток, алгоритм работает корректно.

Аналогично пускается поток и в исток, просто на этот раз будем пропихивать назад недостаток потока и брать максимальную вершину в топологической сортировке.

В качестве упражнения докажите, что сток не достижим из истока тогда и только тогда, когда $p_{out}(s) = 0$, что облегчает проверку этого на втором шаге алгоритма.

Оценим время работы алгоритма. Каждую итерацию пропадает хотя бы одна вершина, выбранная на третьем шаге. Значит, всего совершается $O(V)$ итераций. Несложно убедится, что время работы данного алгоритма равно количеству просмотренных рёбер. На каждой итерации мы проталкиваем избыток(недостаток) потока из $O(V)$ вершин, при этом, либо ребро полностью насыщается потоком, и больше мы не будем его использовать, либо избыток(недостаток) потока заканчивается. Понятно, что ребер, которые не удаляются, на каждой итерации $-$ $O(V)$, а тех, которые удалятся, суммарно $O(E)$, следовательно, время работы алгоритма: $O(V^2 + E)$.

---

Автор конспекта: Станислав Донской

По всем вопросам пишите в telegram @stasana