Алгоритм Форда-Фалкерсона

Материал из Algocode wiki
Версия от 15:49, 4 марта 2020; Stasana (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Немного теории

Утверждение: (Лемма о потоке через разрез)
Для любого $s-t$ разреза $f(S, T) = |f|$

Доказательство:
$f(S, T) \overset{1}{=} f(S, T) + f(S, S) \overset{2}{=} f(S, V) \overset{3}{=} f(s, V) + f(S \setminus \{s\}, V) \overset{4}{=} f(s, V) \overset{5}{=} |f|$

  1. из-за антисимметричности потока $f(S, S) = 0$
  2. $f(S, T) + f(S, S) = \sum\limits_{v \in S} \sum\limits_{u \in T} f(v, u) + \sum\limits_{v \in S} \sum\limits_{u \in S} f(v, u) = \sum\limits_{v \in S} \sum\limits_{u \in V} f(v, u) = f(S, V)$
  3. так же как и 2
  4. $\forall v \in S\setminus \{s\}, f(v, V) = 0$ - сохранение потока
  5. определение

Утверждение: (Теорема Форда-Фалкерсона)
Три следующие утверждения эквивалентны:

  1. Поток $f$ - максимален
  2. В остаточной сети нет увеличивающего пути
  3. Существует $s-t$ разрез, что $f(S, T) = c(S, T)$



Доказательство:

  • 1 $\Rightarrow$ 2: Если увеличивающий путь есть, то мы можем увеличить поток вдоль него, значит поток $f$ - не максимален, противоречие
  • 2 $\Rightarrow$ 3: Разделим вершины на множество достижимых из $s$ и не достижимых (по рёбрам с $c(v, u) > 0$), т.к. увеличивающего пути нет, то $s$ и $t$ лежат в разных множествах, а значит это s-t разрез. При этом для всех его рёбер $f(v, u) = c(v, u)$, а значит $f(S, T) = c(S, T)$
  • 3 $\Rightarrow$ 1: для любого $s-t$ разреза $f(S, T) \leq c(S, T)$, а по лемме о потоке через разрез $|f| = f(S, T) \leq c(S, T)$, значит поток f - максимален

В качестве упражнения предложите сведение поиска минимального разреза к поиску максимального потока.

Алгоритм Форда-Фалкерсона

Идея алгоритма в том, что изначально $\forall{v, u}: f(v, u) = 0$ и мы будем итеративно увеличивать его вдоль увеличивающего пути:

  1. $f(v, u) = 0$, для всех ребер
  2. Если сток недостижим из истока в остаточной сети(по ребрам с $c_f(v, u) > 0$) алгоритм завершается
  3. Найти увеличивающий путь в $G_f$ и пустить вдоль него $\underset{(v, u) \in P}{min} c_f(v, u)$ потока
  4. Перейти к шагу 2

Если алгоритм завершился, то в остаточной сети нет увеличивающего пути, а значит он нашел максимальный поток. В большинстве задач пропускные способности целые, а значит после каждой итерации алгоритма поток увеличивается хотя бы на 1, увеличивающий путь можно искать с помощью $dfs$, следовательно время работы $O(|F|*(V + E))$.

Пример реализации на C++

 1 struct Edge {
 2     int v; // вершина, куда ведёт ребро
 3     int flow; // поток, текущий по ребру
 4     int capacity; // пропускная способность ребра
 5 
 6     Edge(int v, int capacity)
 7         : v(v), flow(0), capacity(capacity) {}
 8 
 9     int get_capacity() { // пропускная способность ребра в остаточной сети
10         return capacity - flow;
11     }
12 };
13 
14 const int INF = (int)(1e9) + 666;
15 const int N = 666;
16 int S, T; // сток и исток
17 
18 vector<Edge> edges;
19 vector<int> graph[N]; // в списке смежности храним не рёбра, и индексы в списке рёбер
20 int used[N];
21 int timer = 1; // для быстрого зануления used-а
22 
23 // Будем поддерживать список рёбер в таком состоянии, что для i ребра, (i ^ 1) будет обратным
24 void add_edge(int v, int u, int capacity) {
25     graph[v].emplace_back(edges.size()); // номер ребра в списке
26     edges.emplace_back(u, capacity); // прямое ребро
27     graph[u].emplace_back(edges.size()); // номер ребра
28     edges.emplace_back(v, 0); // обратное ребро
29 }
30 int dfs(int v, int min_capacity) {
31     if (v == T) {
32         // нашли увеличивающий путь, вдоль которого можно пустить min_capacity потока
33         return min_capacity;
34     }
35     used[v] = timer;
36     for (int index : graph[v]) {
37         if (edges[index].get_capacity() == 0) {
38             continue; // ребро отсутсвует в остаточной сети
39         }
40         if (used[edges[index].v] == timer) {
41             continue;
42         }
43         int x = dfs(edges[index].v, min(min_capacity, edges[index].get_capacity()));
44         if (x) { // нашли путь по которому можно пустить x потока
45             edges[index].flow += x;
46             edges[index ^ 1].flow -= x;
47             return x;
48         }
49     }
50     // не существует пути из v в T
51     return 0;
52 }
53 
54 int main() {
55     int n, m;
56     cin >> n >> m >> S >> T;
57     for (int i = 0; i < m; ++i) {
58         int v, u, capacity;
59         cin >> v >> u >> capacity;
60         add_edge(v, u, capacity);
61     }
62     while (dfs(S, INF)) {  // ищем увеличивающий путь
63         ++timer
64     }
65     // увеличивающего пути нет, следовательно максимальный потока найден
66     int result = 0;
67     for (int index : graph[S]) {
68         result += edges[index].flow;
69     }
70     cout << result << endl;
71     return 0;
72 }




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

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