Максимальний потік — метод Форда–Фалкерсона та алгоритм Едмондса–Карпа

Алгоритм Едмондса–Карпа — це реалізація методу Форда–Фалкерсона для обчислення максимального потоку в потоковій мережі.

Коли підходить цей алгоритм?

• Задачу можна звести до максимального потоку / мінімального розрізу в мережі з пропускними здатностями?
• Граф невеликий, щоб витримати $O(VE^2)$? (для більших графів — швидший алгоритм Дініца за $O(V^2E)$)
• Достатньо простої у реалізації версії через BFS, яку легко написати на контесті як перше наближення?

Потокова мережа

Спочатку означимо, що таке потокова мережа, потік і максимальний потік.

Мережа — це орієнтований граф $G$ з вершинами $V$ та ребрами $E$, доповнений функцією $c$, яка кожному ребру $e \in E$ ставить у відповідність невід'ємне ціле значення — пропускну здатність ребра $e$. Така мережа називається потоковою мережею, якщо ми додатково позначаємо дві вершини: одну як джерело, а іншу як стік.

Потік у потоковій мережі — це функція $f$, яка знову ж таки кожному ребру $e$ ставить у відповідність невід'ємне ціле значення, а саме потік. Ця функція має задовольняти дві умови.

Потік ребра не може перевищувати його пропускну здатність.

$$f(e) \le c(e)$$

А сума вхідного потоку у вершину $u$ має дорівнювати сумі вихідного потоку з $u$, окрім вершин джерела та стоку.

$$\sum_{(v, u) \in E} f((v, u)) = \sum_{(u, v) \in E} f((u, v))$$

Вершина-джерело $s$ має лише вихідний потік, а вершина-стік $t$ має лише вхідний потік.

Легко бачити, що виконується таке співвідношення:

$$\sum_{(s, u) \in E} f((s, u)) = \sum_{(u, t) \in E} f((u, t))$$

Гарною аналогією для потокової мережі є така візуалізація. Ми зображуємо ребра як труби з водою, пропускна здатність ребра — це максимальна кількість води, що може протікати трубою за секунду, а потік ребра — це кількість води, яка наразі тече трубою за секунду. Це й мотивує першу умову потоку. Трубою не може протікати більше води, ніж її пропускна здатність. Вершини діють як з'єднання труб, куди вода виходить з одних труб, а потім ці вершини якимось чином розподіляють воду по інших трубах. Це також мотивує другу умову потоку. Уся вхідна вода має бути розподілена між іншими трубами в кожному з'єднанні. Вона не може магічно зникнути чи з'явитися. Джерело $s$ — це початок усієї води, а вода може витікати лише у стоку $t$.

На зображенні нижче показано потокову мережу. Перше значення кожного ребра — це потік, який спочатку дорівнює 0, а друге значення — це пропускна здатність.

Величина потоку мережі — це сума всіх потоків, що породжуються у джерелі $s$, або, що еквівалентно, сума всіх потоків, які споживаються стоком $t$. Максимальний потік — це потік з найбільшою можливою величиною. Знаходження цього максимального потоку потокової мережі і є тією задачею, яку ми хочемо розв'язати.

У візуалізації з трубами для води задачу можна сформулювати так: скільки води ми можемо проштовхнути трубами від джерела до стоку?

На зображенні нижче показано максимальний потік у потоковій мережі.

Метод Форда–Фалкерсона

Означимо ще одне поняття. Залишкова пропускна здатність орієнтованого ребра — це пропускна здатність мінус потік. Слід зауважити, що якщо вздовж деякого орієнтованого ребра $(u, v)$ є потік, то обернене ребро має пропускну здатність 0, і ми можемо означити потік для нього як $f((v, u)) = -f((u, v))$. Це також означує залишкову пропускну здатність для всіх обернених ребер. З усіх цих ребер ми можемо утворити залишкову мережу — це просто мережа з тими самими вершинами та ребрами, але як пропускні здатності ми використовуємо залишкові пропускні здатності.

Метод Форда–Фалкерсона працює так. Спочатку ми встановлюємо потік кожного ребра рівним нулю. Потім ми шукаємо збільшувальний шлях від $s$ до $t$. Збільшувальний шлях — це простий шлях у залишковому графі, де залишкова пропускна здатність додатна для всіх ребер уздовж цього шляху. Якщо такий шлях знайдено, то ми можемо збільшити потік уздовж цих ребер. Ми продовжуємо шукати збільшувальні шляхи й збільшувати потік. Щойно збільшувального шляху більше не існує, потік є максимальним.

Уточнимо детальніше, що означає збільшення потоку вздовж збільшувального шляху. Нехай $C$ — це найменша залишкова пропускна здатність серед ребер шляху. Тоді ми збільшуємо потік так: для кожного ребра $(u, v)$ шляху оновлюємо $f((u, v)) ~\text{+=}~ C$ та $f((v, u)) ~\text{-=}~ C$.

Ось приклад, що демонструє цей метод. Ми використовуємо ту саму потокову мережу, що й вище. Спочатку ми починаємо з потоку 0.

Ми можемо знайти шлях $s - A - B - t$ із залишковими пропускними здатностями 7, 5 та 8. Їхній мінімум дорівнює 5, тому ми можемо збільшити потік уздовж цього шляху на 5. Це дає потік 5 для мережі.

Знову шукаємо збільшувальний шлях, цього разу знаходимо $s - D - A - C - t$ із залишковими пропускними здатностями 4, 3, 3 та 5. Тому ми можемо збільшити потік на 3 і отримуємо потік 8 для мережі.

Цього разу ми знаходимо шлях $s - D - C - B - t$ із залишковими пропускними здатностями 1, 2, 3 та 3, і отже, збільшуємо потік на 1.

Цього разу ми знаходимо збільшувальний шлях $s - A - D - C - t$ із залишковими пропускними здатностями 2, 3, 1 та 2. Ми можемо збільшити потік на 1. Але цей шлях дуже цікавий. Він містить обернене ребро $(A, D)$. У вихідній потоковій мережі нам не дозволено надсилати жодного потоку від $A$ до $D$. Але оскільки ми вже маємо потік 3 від $D$ до $A$, це стає можливим. Інтуїція тут така: замість того щоб надсилати потік 3 від $D$ до $A$, ми надсилаємо лише 2 і компенсуємо це, надсилаючи додатковий потік 1 від $s$ до $A$, що дозволяє нам надіслати додатковий потік 1 уздовж шляху $D - C - t$.

Тепер знайти збільшувальний шлях між $s$ і $t$ неможливо, тому цей потік $10$ є найбільшим можливим. Ми знайшли максимальний потік.

Слід зауважити, що метод Форда–Фалкерсона не визначає способу знаходження збільшувального шляху. Можливими підходами є використання DFS або BFS, які обидва працюють за $O(E)$. Якщо всі пропускні здатності мережі є цілими числами, то для кожного збільшувального шляху потік мережі зростає щонайменше на 1 (детальніше див. Теорема про цілочисловий потік). Тому складність методу Форда–Фалкерсона становить $O(E F)$, де $F$ — це максимальний потік мережі. У випадку раціональних пропускних здатностей алгоритм також завершиться, але його складність не обмежена. У випадку ірраціональних пропускних здатностей алгоритм може ніколи не завершитися і може навіть не збігатися до максимального потоку.

Алгоритм Едмондса–Карпа

Алгоритм Едмондса–Карпа — це просто реалізація методу Форда–Фалкерсона, яка використовує BFS для знаходження збільшувальних шляхів. Алгоритм уперше опублікував Юхим Диниць у 1970 році, а пізніше незалежно опублікували Джек Едмондс і Річард Карп у 1972 році.

Складність можна задати незалежно від величини максимального потоку. Алгоритм працює за час $O(V E^2)$, навіть для ірраціональних пропускних здатностей. Інтуїція полягає в тому, що щоразу, коли ми знаходимо збільшувальний шлях, одне з ребер стає насиченим, і відстань від цього ребра до $s$ буде довшою, якщо воно знову з'явиться у збільшувальному шляху пізніше. Довжина простих шляхів обмежена $V$.

Реалізація

Матриця capacity зберігає пропускну здатність для кожної пари вершин. adj — це список суміжності неорієнтованого графа, оскільки під час пошуку збільшувальних шляхів ми також маємо використовувати обернені до орієнтованих ребер.

Функція maxflow повертатиме величину максимального потоку. Під час роботи алгоритму матриця capacity фактично зберігатиме залишкову пропускну здатність мережі. Величина потоку в кожному ребрі насправді не зберігається, але реалізацію легко розширити — за допомогою додаткової матриці, — щоб також зберігати потік і повертати його.

C++

int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;

int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({s, INF});

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({next, new_flow});
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(n);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}

Python

from collections import deque

INF = float("inf")

n: int
capacity: list[list[int]]  # матриця залишкових пропускних здатностей
adj: list[list[int]]       # список суміжності неорієнтованого графа


def bfs(s: int, t: int, parent: list[int]) -> int:
    for i in range(n):
        parent[i] = -1
    parent[s] = -2
    # У черзі зберігаємо вершину та мінімальну пропускну здатність шляху до неї
    q = deque([(s, INF)])

    while q:
        cur, flow = q.popleft()
        for nxt in adj[cur]:
            # Йдемо лише ребрами з додатною залишковою пропускною здатністю
            if parent[nxt] == -1 and capacity[cur][nxt]:
                parent[nxt] = cur
                new_flow = min(flow, capacity[cur][nxt])
                if nxt == t:
                    return new_flow
                q.append((nxt, new_flow))

    return 0


def maxflow(s: int, t: int) -> int:
    flow = 0
    parent = [-1] * n

    while True:
        new_flow = bfs(s, t, parent)
        if new_flow == 0:
            break
        flow += new_flow
        # Йдемо назад шляхом і оновлюємо залишкові пропускні здатності
        cur = t
        while cur != s:
            prev = parent[cur]
            capacity[prev][cur] -= new_flow
            capacity[cur][prev] += new_flow
            cur = prev

    return flow

TypeScript

const INF = Number.MAX_SAFE_INTEGER;

let n: number;
let capacity: number[][]; // матриця залишкових пропускних здатностей
let adj: number[][]; // список суміжності неорієнтованого графа

function bfs(s: number, t: number, parent: number[]): number {
  parent.fill(-1);
  parent[s] = -2;
  // У черзі зберігаємо вершину та мінімальну пропускну здатність шляху до неї
  const q: Array<[number, number]> = [[s, INF]];
  let head = 0;

  while (head < q.length) {
    const [cur, flow] = q[head++];
    for (const next of adj[cur]) {
      // Йдемо лише ребрами з додатною залишковою пропускною здатністю
      if (parent[next] === -1 && capacity[cur][next]) {
        parent[next] = cur;
        const newFlow = Math.min(flow, capacity[cur][next]);
        if (next === t) return newFlow;
        q.push([next, newFlow]);
      }
    }
  }

  return 0;
}

function maxflow(s: number, t: number): number {
  let flow = 0;
  const parent: number[] = new Array(n).fill(-1);

  for (;;) {
    const newFlow = bfs(s, t, parent);
    if (newFlow === 0) break;
    flow += newFlow;
    // Йдемо назад шляхом і оновлюємо залишкові пропускні здатності
    let cur = t;
    while (cur !== s) {
      const prev = parent[cur];
      capacity[prev][cur] -= newFlow;
      capacity[cur][prev] += newFlow;
      cur = prev;
    }
  }

  return flow;
}

Go

const INF = int(^uint(0) >> 1) // максимальне додатне int

var (
    n        int
    capacity [][]int // матриця залишкових пропускних здатностей
    adj      [][]int // список суміжності неорієнтованого графа
)

func bfs(s, t int, parent []int) int {
    for i := range parent {
        parent[i] = -1
    }
    parent[s] = -2
    // У черзі зберігаємо вершину та мінімальну пропускну здатність шляху до неї
    type node struct{ v, flow int }
    q := []node{{s, INF}}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for _, next := range adj[cur.v] {
            // Йдемо лише ребрами з додатною залишковою пропускною здатністю
            if parent[next] == -1 && capacity[cur.v][next] > 0 {
                parent[next] = cur.v
                newFlow := min(cur.flow, capacity[cur.v][next])
                if next == t {
                    return newFlow
                }
                q = append(q, node{next, newFlow})
            }
        }
    }

    return 0
}

func maxflow(s, t int) int {
    flow := 0
    parent := make([]int, n)

    for {
        newFlow := bfs(s, t, parent)
        if newFlow == 0 {
            break
        }
        flow += newFlow
        // Йдемо назад шляхом і оновлюємо залишкові пропускні здатності
        cur := t
        for cur != s {
            prev := parent[cur]
            capacity[prev][cur] -= newFlow
            capacity[cur][prev] += newFlow
            cur = prev
        }
    }

    return flow
}

Теорема про цілочисловий потік ##

Теорема стверджує, що якщо кожна пропускна здатність у мережі є цілим числом, то величина максимального потоку є цілим числом, і існує максимальний потік, у якому потік у кожному ребрі також є цілим числом. Зокрема, метод Форда–Фалкерсона знаходить саме такий потік.

Теорема про максимальний потік і мінімальний розріз

$s$-$t$-розріз — це розбиття вершин потокової мережі на дві множини, таке що одна множина містить джерело $s$, а інша — стік $t$. Пропускна здатність $s$-$t$-розрізу означується як сума пропускних здатностей ребер, що йдуть зі сторони джерела на сторону стоку.

Очевидно, що ми не можемо надіслати від $s$ до $t$ більше потоку, ніж пропускна здатність будь-якого $s$-$t$-розрізу. Тому максимальний потік обмежений пропускною здатністю мінімального розрізу.

Теорема про максимальний потік і мінімальний розріз іде ще далі. Вона стверджує, що пропускна здатність максимального потоку має дорівнювати пропускній здатності мінімального розрізу.

На зображенні нижче ви можете побачити мінімальний розріз потокової мережі, яку ми використовували раніше. Воно показує, що пропускна здатність розрізу $\{s, A, D\}$ та $\{B, C, t\}$ дорівнює $5 + 3 + 2 = 10$, що дорівнює знайденому нами максимальному потоку. Інші розрізи матимуть більшу пропускну здатність, наприклад, пропускна здатність між $\{s, A\}$ та $\{B, C, D, t\}$ дорівнює $4 + 3 + 5 = 12$.

Мінімальний розріз можна знайти після виконання обчислення максимального потоку методом Форда–Фалкерсона. Один з можливих мінімальних розрізів такий: множина всіх вершин, до яких можна дістатися з $s$ у залишковому графі (використовуючи ребра з додатною залишковою пропускною здатністю), і множина всіх інших вершин. Це розбиття легко знайти за допомогою DFS, починаючи з $s$.

Задачі для практики

• Codeforces - Array and Operations
• Codeforces - Red-Blue Graph
• CSES - Download Speed
• CSES - Police Chase
• CSES - School Dance
• CSES - Distinct Routes

Відеоматеріали