В этом посте я расскажу о четырех основных и простых алгоритмах поиска максимального потока, к каждому алгоритму прилагается описание работы, псевдокод, нестрогое объяснение корректности, реализация на C++11, и ссылки на задачи.
I. Задача
Пусть дан граф $$$G=<V,E>$$$ и две вершины $$$s,t \in V$$$, которые в дальнейшем будем называть исток и сток, и каждому ребру из вершины $$$a$$$ в вершину $$$b$$$ сопоставлена пропускная способность $$$c_{a,b}$$$. Определим сопоставление каждому ребру $$$<a,b>$$$ числа $$$g_{a,b}$$$. Назовем это сопоставление потоком, если для каждого ребра $$$<a,b>$$$ верны два утверждения:
1) $$$0 \le g_{a,b} \le c_{a,b}$$$
2) $$$ \sum_{i \in V} g_{i,a} = \sum_{i \in V} g_{a,i} \forall a \in V \setminus \{ s,t \} $$$
Величина потока равна $$$ \sum_{i \in V} g_{s,i} = \sum_{i \in V} g_{i,t} = |F|$$$. Задача — вычислить $$$|F|$$$ и все $$$g_{a,b}$$$.
II. Метод проталкивания потока
a) Алгоритм Форда-Фалкерсона
Пусть дан граф с пропускными способностями. Будем хранить его пропускные способности в матрице смежности $$$c[][]$$$, если ребра $$$<a,b>$$$ нет в графе, $$$c[a][b]=0$$$. Определим операцию проталкивания потока: пусть мы выбрали путь $$$p_{1},p_{2}, \dots ,p_{k}$$$ из истока $$$s$$$ в сток $$$t$$$ такой, что пропускные способности между соседними вершинами положительны: $$$c_{p_{i-1},p_{i}} > 0 \forall i \in [2,k]$$$. Пусть $$$AugFlow$$$ — минимальная пропускная способность на ребре на пути: $$$AugFlow = min_{i \in [2,k]} c_{p_{i-1},p_{i}}$$$. Пройдем по этому пути и вычтем из пропускных способностей $$$AugFlow$$$ по направлению к стоку и добавим против стока. Итак, если у нас есть путь ненулевой пропускной способности, мы можем увеличить поток. Можно ли, вычисляя такие пути, всегда найти максимальный поток? Работает следующая теорема:
Теорема 1.1 Для того, чтобы поток был максимальным, необходимо и достаточно, чтобы отсутствовал путь из истока в сток ненулевой пропускной способности.
Асимптотика Если пропускные способности целочисленные, то дополняющий поток всегда не меньше единицы. Тогда, так как асимптотика обхода графа $$$O(E)$$$, асимптотика алгоритма составляет $$$O(E|F|)$$$. К сожалению, это не так для графов с вещественными пропускными способностями. Но если использовать обход графа в ширину, действует следующая теорема:
Теорема 1.2 В течении алгоритма с обходом в ширину расстояние от истока до любой вершины по ребрам ненулевой пропускной способности не уменьшается.
Это дает еще одну асимптотику: $$$O(VE^{2})$$$. Данный алгоритм называется алгоритмом Эдмондса-Карпа. Его реализация здесь дана.
b) Алгоритм Диница
Алгоритм Форда-Фалкерсона можно ускорить, использую следующую идею. Выполним поиск в ширину из истока и, игнорируя ребра с нулевой пропускной способностью, вычислим расстояния $$$d[]$$$ до каждой вершины. Будем говорить, что мы построили слоистую сеть. Затем будем искать такие дополняющие пути $$$p[]$$$, что $$$d[p[1]]-d[p[0]]=d[p[2]]-d[p[1]]= \dots =1$$$. Все эти пути можно найти довольно быстро — за $$$O(VE)$$$: очевидно, что в силу ограничения, наложенного на путь, если по ребру $$$<a,b>$$$ не удалось протолкнуть путь, в течении фазы по нему нельзя будет протолкнуть путь. Поэтому будем поддерживать у каждой вершины первую нерассмотренную вершину для каждой фазы, и искать следующие пути в этой фазе, начиная с первой нерассмотренной вершины и увеличивать это значение, если путь с этой вершины не нашелся. После того, как мы нашли все пути, мы приступаем к следующей фазе. При этом работает следующая теорема:
Теорема 2.1 Расстояние до стока после каждой фазы строго возрастает.
Тогда, так как путь из истока в сток не больше $$$V$$$, количество фаз $$$O(V)$$$.
Асимптотика $$$O(V)$$$ фаз и $$$O(VE)$$$ на каждую фазу — итого $$$O(V^{2}E)$$$.
Частный случай использования этого алгоритма для поиска максимального паросочетания в двудольном графе называется алгоритмом Хопкрофта-Карпа. Он имеет более сильную асимптотику $$$O(\sqrt{V}E)$$$.
III. Метод проталкивания предпотока
a) Разрядить, пока есть что разрядить
Назовем предпотоком сопоставление каждому ребру в графе числа, при котором выполняется:
1) $$$0 \le g_{a,b} \le c_{a,b}$$$
2) $$$ \sum_{i \in V} g_{i,a} \ge \sum_{i \in V} g_{a,i} \forall a \in V \setminus \{ s,t \} $$$
Определим переполнение $$$e_{i}$$$ вершины как значение $$$ \sum_{i \in V} g_{i,a} - \sum_{i \in V} g_{a,i} $$$, и высоту $$$h_{i}$$$ вершины. Будем выполнять две операции:
1) Проталкивание из вершины $$$a$$$ в вершину $$$b$$$. Допустимо тогда, когда $$$h_{a}=h_{b}+1$$$. Проталкиваем столько потока, на сколько переполнена $$$a$$$, но не более, чем может вместить ребро $$$<a,b>$$$: $$$pushed=min(e_{a},c_{a,b})$$$.
2) Поднятие вершины $$$a$$$: допустимо, если $$$a$$$ переполнена, но нет такой вершины $$$b$$$, что $$$h_{a}=h_{b}+1$$$.
Алгоритм заключается в использовании этих операций в любом порядке, пока хотя бы одна из них допустима. Можно для удобства определить операцию разрядить вершину, которая выполняет проталкивания из нее и поднятия, пока она переполнена (это не повлияет на асимптотику).
Перед основным циклом необходимо выполнить следующую инициализацию: проталкиваем тривиально из истока во все соседние вершины.
Теорема 3.1 Подъем вершины строго увеличивает ее высоту.
Теорема 3.2 Если ни одно действие недопустимо — предпоток есть максимальный поток.
Асимптотика Высота каждой вершины во время работы алгоритма не превышает $$$2V$$$, откуда количество вызовов операции поднять есть $$$O(V^{2})$$$, а количество вызовов операции протолкнуть есть $$$O(V^{2}E)$$$. Итоговая асимптотика — $$$O(V^{2}E)$$$.
Задачи 4 5
Те же, что и для Диница
б) Разрядить в очереди
Краткая идея: будем хранить все переполненные вершины в очереди, и разряжать первую вершину.
Асимптотика $$$O(V^{3})$$$.
Задачи 6
К сожалению, к данной задаче принимается Диниц, а не должен.
Comments (0)
