Luồng cực đại — Max Flow & Edmonds-Karp

Một nhà mạng cần truyền dữ liệu từ data center A đến data center B qua mạng lưới router. Mỗi liên kết có bandwidth giới hạn. Câu hỏi: tổng bandwidth tối đa có thể truyền từ A đến B là bao nhiêu? Đây không phải shortest path — không cần đường đi nhanh nhất, mà cần tổng thông lượng lớn nhất qua mọi đường có thể, đồng thời.

Bài toán Max Flow là nền tảng của lý thuyết flow network. Nó giải quyết trực tiếp bài toán capacity planning, và gián tiếp giải quyết bipartite matching, project selection, image segmentation qua phép quy dẫn. Min-cut max-flow theorem — một trong những kết quả đẹp nhất của tổ hợp — khẳng định: luồng cực đại bằng lát cắt tối thiểu.

Bức tranh tư duy

Hình dung hệ thống ống nước từ bể chứa (source) đến nhà máy (sink). Mỗi ống có tiết diện giới hạn (capacity). Nước chảy qua nhiều ống đồng thời. Bạn muốn tổng lượng nước đến nhà máy nhiều nhất có thể.

text

        ┌─── B ───┐
       10    │     8
      ╱      5      ╲
   S         ↓        T
      ╲      │      ╱
       8     C    10
        └────┘────┘

Capacity: S→B=10, S→C=8, B→C=5, B→T=8, C→T=10

Ford-Fulkerson method: Lặp lại — tìm đường đi từ S đến T còn capacity (augmenting path), đẩy luồng qua đường đó, cập nhật residual graph. Dừng khi không còn augmenting path.

Residual graph: Sau khi đẩy f đơn vị qua cạnh u→v (capacity c), capacity còn lại là c-f theo chiều thuận, và f theo chiều ngược (cho phép "hủy" luồng đã đẩy). Cạnh ngược chính là chìa khóa — nó cho phép thuật toán sửa sai.

📌 Tại sao cần cạnh ngược?

Không có cạnh ngược, greedy chọn augmenting path đầu tiên có thể block luồng tối ưu. Cạnh ngược cho phép "rút" luồng đã đẩy sai và chuyển hướng — đảm bảo tìm được max flow.

Cốt lõi kỹ thuật

Edmonds-Karp — BFS augmenting paths

Edmonds-Karp là Ford-Fulkerson sử dụng BFS để tìm augmenting path ngắn nhất (ít cạnh nhất). Đảm bảo O(VE²) — hữu hạn và polynomial, không phụ thuộc vào giá trị capacity.

C++PythonJavaGo

cpp

#include <vector>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;

struct MaxFlow {
    int n;
    vector<vector<int>> cap, flow;

    MaxFlow(int n) : n(n), cap(n, vector<int>(n, 0)),
                     flow(n, vector<int>(n, 0)) {}

    void addEdge(int u, int v, int c) {
        cap[u][v] += c;
    }

    int bfs(int s, int t, vector<int>& parent) {
        fill(parent.begin(), parent.end(), -1);
        parent[s] = s;
        queue<pair<int,int>> q;
        q.push({s, INT_MAX});
        while (!q.empty()) {
            auto [u, pushed] = q.front(); q.pop();
            for (int v = 0; v < n; v++) {
                int residual = cap[u][v] - flow[u][v];
                if (parent[v] == -1 && residual > 0) {
                    parent[v] = u;
                    int new_flow = min(pushed, residual);
                    if (v == t) return new_flow;
                    q.push({v, new_flow});
                }
            }
        }
        return 0;
    }

    int maxflow(int s, int t) {
        int total = 0;
        vector<int> parent(n);
        int pushed;
        while ((pushed = bfs(s, t, parent)) > 0) {
            total += pushed;
            int cur = t;
            while (cur != s) {
                int prev = parent[cur];
                flow[prev][cur] += pushed;
                flow[cur][prev] -= pushed;
                cur = prev;
            }
        }
        return total;
    }
};

python

from collections import deque

class MaxFlow:
    def __init__(self, n: int):
        self.n = n
        self.cap = [[0] * n for _ in range(n)]
        self.flow = [[0] * n for _ in range(n)]

    def add_edge(self, u: int, v: int, c: int):
        self.cap[u][v] += c

    def bfs(self, s: int, t: int, parent: list[int]) -> int:
        parent[:] = [-1] * self.n
        parent[s] = s
        q = deque([(s, float('inf'))])
        while q:
            u, pushed = q.popleft()
            for v in range(self.n):
                residual = self.cap[u][v] - self.flow[u][v]
                if parent[v] == -1 and residual > 0:
                    parent[v] = u
                    new_flow = min(pushed, residual)
                    if v == t:
                        return new_flow
                    q.append((v, new_flow))
        return 0

    def maxflow(self, s: int, t: int) -> int:
        total = 0
        parent = [0] * self.n
        while True:
            pushed = self.bfs(s, t, parent)
            if pushed == 0:
                break
            total += pushed
            cur = t
            while cur != s:
                prev = parent[cur]
                self.flow[prev][cur] += pushed
                self.flow[cur][prev] -= pushed
                cur = prev
        return total

java

import java.util.*;

class MaxFlow {
    int n;
    int[][] cap, flow;

    MaxFlow(int n) {
        this.n = n;
        cap = new int[n][n];
        flow = new int[n][n];
    }

    void addEdge(int u, int v, int c) { cap[u][v] += c; }

    int bfs(int s, int t, int[] parent) {
        Arrays.fill(parent, -1);
        parent[s] = s;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{s, Integer.MAX_VALUE});
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int u = cur[0], pushed = cur[1];
            for (int v = 0; v < n; v++) {
                int res = cap[u][v] - flow[u][v];
                if (parent[v] == -1 && res > 0) {
                    parent[v] = u;
                    int nf = Math.min(pushed, res);
                    if (v == t) return nf;
                    q.add(new int[]{v, nf});
                }
            }
        }
        return 0;
    }

    int maxflow(int s, int t) {
        int total = 0;
        int[] parent = new int[n];
        int pushed;
        while ((pushed = bfs(s, t, parent)) > 0) {
            total += pushed;
            int cur = t;
            while (cur != s) {
                int prev = parent[cur];
                flow[prev][cur] += pushed;
                flow[cur][prev] -= pushed;
                cur = prev;
            }
        }
        return total;
    }
}

type MaxFlow struct {
    n    int
    cap  [][]int
    flow [][]int
}

func NewMaxFlow(n int) *MaxFlow {
    cap := make([][]int, n)
    fl := make([][]int, n)
    for i := range cap {
        cap[i] = make([]int, n)
        fl[i] = make([]int, n)
    }
    return &MaxFlow{n: n, cap: cap, flow: fl}
}

func (mf *MaxFlow) AddEdge(u, v, c int) { mf.cap[u][v] += c }

func (mf *MaxFlow) bfs(s, t int, parent []int) int {
    for i := range parent { parent[i] = -1 }
    parent[s] = s
    type pair struct{ node, flow int }
    q := []pair{{s, 1<<31 - 1}}
    for len(q) > 0 {
        cur := q[0]; q = q[1:]
        for v := 0; v < mf.n; v++ {
            res := mf.cap[cur.node][v] - mf.flow[cur.node][v]
            if parent[v] == -1 && res > 0 {
                parent[v] = cur.node
                nf := min(cur.flow, res)
                if v == t { return nf }
                q = append(q, pair{v, nf})
            }
        }
    }
    return 0
}

func (mf *MaxFlow) Maxflow(s, t int) int {
    total := 0
    parent := make([]int, mf.n)
    for {
        pushed := mf.bfs(s, t, parent)
        if pushed == 0 { break }
        total += pushed
        cur := t
        for cur != s {
            prev := parent[cur]
            mf.flow[prev][cur] += pushed
            mf.flow[cur][prev] -= pushed
            cur = prev
        }
    }
    return total
}

func min(a, b int) int { if a < b { return a }; return b }

Dinic's Algorithm — blocking flow với level graph

Dinic cải tiến bằng cách xây level graph (BFS để gán level cho đỉnh), rồi tìm blocking flow bằng DFS trên level graph. Mỗi phase tăng khoảng cách shortest augmenting path → tối đa V phase. Complexity: O(V²E), nhanh hơn đáng kể trên đồ thị lớn.

python

class Dinic:
    def __init__(self, n: int):
        self.n = n
        self.graph: list[list[list[int]]] = [[] for _ in range(n)]

    def add_edge(self, u: int, v: int, cap: int):
        self.graph[u].append([v, cap, len(self.graph[v])])
        self.graph[v].append([u, 0, len(self.graph[u]) - 1])

    def bfs(self, s: int, t: int) -> bool:
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, cap, _ in self.graph[u]:
                if cap > 0 and self.level[v] == -1:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] != -1

    def dfs(self, u: int, t: int, pushed: int) -> int:
        if u == t:
            return pushed
        while self.iter[u] < len(self.graph[u]):
            v, cap, rev = self.graph[u][self.iter[u]]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(pushed, cap))
                if d > 0:
                    self.graph[u][self.iter[u]][1] -= d
                    self.graph[v][rev][1] += d
                    return d
            self.iter[u] += 1
        return 0

    def max_flow(self, s: int, t: int) -> int:
        flow = 0
        while self.bfs(s, t):
            self.iter = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Min-Cut Max-Flow Theorem

Định lý: Giá trị luồng cực đại từ s đến t = capacity của lát cắt tối thiểu ngăn cách s và t.

Sau khi chạy max flow, thực hiện BFS trên residual graph từ s. Đỉnh reachable thuộc phía S, còn lại thuộc phía T. Các cạnh từ S sang T với residual = 0 chính là min-cut.

Thực chiến

Tình huống 1: Network capacity planning

Bối cảnh: Tính bandwidth tối đa giữa hai data center qua mạng lưới router.

python

def max_bandwidth(routers: int, links: list[tuple[int, int, int]],
                  src: int, dst: int) -> int:
    mf = MaxFlow(routers)
    for u, v, bw in links:
        mf.add_edge(u, v, bw)
        mf.add_edge(v, u, bw)  # undirected
    return mf.maxflow(src, dst)

Tình huống 2: Bipartite matching qua max flow

Bối cảnh: N nhân viên, M task. Mỗi nhân viên có thể làm một số task nhất định. Tìm cách phân công tối đa.

python

def max_matching(n_workers: int, n_tasks: int,
                 can_do: list[tuple[int, int]]) -> int:
    # Source = 0, Workers = 1..n, Tasks = n+1..n+m, Sink = n+m+1
    total = n_workers + n_tasks + 2
    s, t = 0, total - 1
    mf = MaxFlow(total)

    for w in range(1, n_workers + 1):
        mf.add_edge(s, w, 1)

    for w, task in can_do:
        mf.add_edge(w, n_workers + task, 1)

    for task in range(1, n_tasks + 1):
        mf.add_edge(n_workers + task, t, 1)

    return mf.maxflow(s, t)

Phân tích: Xây flow network với source → workers → tasks → sink, capacity 1 mỗi cạnh. Max flow = maximum matching. Edmonds-Karp chạy O(V × E) trên bipartite graph (nhanh hơn bound chung O(VE²)).

Sai lầm điển hình

❌ Sai lầm 1: Quên cạnh ngược (reverse edge)

Vấn đề: Chỉ cập nhật capacity thuận mà không tạo cạnh ngược.

python

# SAI: không có reverse edge
flow[u][v] += pushed
# thiếu: flow[v][u] -= pushed

Tại sao sai: Không có cạnh ngược, thuật toán không thể "rút" luồng đã đẩy sai. Kết quả có thể nhỏ hơn max flow thực tế.

python

# ĐÚNG: cập nhật cả chiều thuận và chiều ngược
flow[u][v] += pushed
flow[v][u] -= pushed  # hoặc residual ngược tăng lên

❌ Sai lầm 2: Ford-Fulkerson với DFS trên capacity lớn

Vấn đề: Dùng DFS thay BFS cho augmenting path.

python

# NGUY HIỂM: DFS có thể chọn path kém, loop rất lâu
def find_path_dfs(s, t):  # Ford-Fulkerson gốc
    ...

Tại sao sai: Ford-Fulkerson thuần (DFS) có complexity O(E × max_flow). Nếu capacity lớn (10⁹), có thể chạy 10⁹ iteration. Với số thực (floating point), thậm chí có thể không dừng. Edmonds-Karp (BFS) đảm bảo O(VE²) — polynomial.

python

# ĐÚNG: luôn dùng BFS (Edmonds-Karp) hoặc Dinic
def find_path_bfs(s, t):  # Edmonds-Karp
    ...

❌ Sai lầm 3: Undirected edge xử lý sai

Vấn đề: Với cạnh vô hướng, chỉ thêm một chiều.

python

# SAI: cạnh vô hướng chỉ thêm một chiều
mf.add_edge(u, v, cap)

Tại sao sai: Cạnh vô hướng với capacity c cho phép flow c theo cả hai chiều. Phải thêm cả u→v và v→u, mỗi cái capacity c.

python

# ĐÚNG: thêm cả hai chiều cho undirected edge
mf.add_edge(u, v, cap)
mf.add_edge(v, u, cap)

Under the Hood

Hiệu năng

Thuật toán	Time	Space	Ghi chú
Ford-Fulkerson (DFS)	O(E × max_flow)	O(V²)	Không polynomial, tránh dùng
Edmonds-Karp (BFS)	O(VE²)	O(V²)	An toàn, dễ cài
Dinic	O(V²E)	O(V + E)	Nhanh hơn thực tế, O(E√V) cho bipartite

Bipartite matching: Dinic trên bipartite graph đạt O(E√V) — tối ưu cho bài toán matching.

Min-Cut ↔ Max-Flow duality

Luồng cực đại = lát cắt tối thiểu. Ứng dụng:

Network reliability: min-cut cho biết bottleneck — số cạnh tối thiểu cần cắt để ngắt kết nối s-t
Image segmentation: pixel là node, similarity là capacity, min-cut chia ảnh thành foreground/background
Project selection: profit maximization với dependencies → quy về min-cut

Edmonds-Karp vs Dinic — khi nào dùng gì?

Tiêu chí	Edmonds-Karp	Dinic
Dễ cài đặt	✅ Rất đơn giản	Phức tạp hơn (level graph + DFS)
Tốc độ thực tế	Chậm hơn	✅ Nhanh hơn nhiều
Bipartite matching	O(VE)	✅ O(E√V)
Competitive programming	Đủ cho V ≤ 500	✅ Cần cho V ≤ 10⁴

Quy tắc: Edmonds-Karp cho prototype và bài nhỏ. Dinic cho production và bài lớn.

Checklist ghi nhớ

✅ Checklist triển khai

Nền tảng

[ ] Flow network: source, sink, capacity, flow conservation, capacity constraint
[ ] Residual graph: capacity còn lại + cạnh ngược
[ ] Augmenting path: đường từ s đến t trên residual graph còn capacity > 0

Triển khai

[ ] Edmonds-Karp: BFS tìm augmenting path, cập nhật flow thuận + ngược
[ ] Dinic: BFS level graph + DFS blocking flow, dùng iter[] tránh duyệt lại cạnh đã bão hòa
[ ] Undirected edge: thêm cả hai chiều, mỗi chiều capacity c

Ứng dụng

[ ] Bipartite matching: source → left → right → sink, capacity 1
[ ] Min-cut: BFS trên residual graph sau max flow, cạnh bão hòa = min-cut edges
[ ] Project selection, network capacity planning

Bài tập luyện tập

Bài 1: Maximum Bipartite Matching — Intermediate

Đề bài: Cho bipartite graph n-left, m-right và danh sách cạnh. Tìm matching lớn nhất.

🧠 Quiz

Min-cut max-flow theorem phát biểu gì?

[ ] A. Min-cut luôn nhỏ hơn max-flow
[ ] B. Min-cut luôn lớn hơn max-flow
[x] C. Giá trị max-flow bằng capacity của min-cut
[ ] D. Min-cut và max-flow không liên quan Giải thích: Đây là duality theorem: max-flow = min-cut. Luồng cực đại bị giới hạn bởi bottleneck nhỏ nhất (min-cut), và bottleneck đó đạt được.

💡 Gợi ý

Xây flow network: S → left nodes (cap 1) → right nodes (cap 1) → T
Max flow = max matching

✅ Lời giải

python

def max_bipartite_matching(n: int, m: int, edges: list[tuple[int,int]]) -> int:
    total = n + m + 2
    s, t = 0, total - 1
    mf = MaxFlow(total)
    for i in range(1, n + 1):
        mf.add_edge(s, i, 1)
    for u, v in edges:
        mf.add_edge(u, n + v, 1)
    for j in range(1, m + 1):
        mf.add_edge(n + j, t, 1)
    return mf.maxflow(s, t)

Phân tích: O(V × E) với Edmonds-Karp, O(E√V) với Dinic.

Bài 2: Network Bottleneck — Advanced

Đề bài: Cho flow network, tìm min-cut (tập cạnh cần cắt để ngắt kết nối s-t với tổng capacity nhỏ nhất). In ra các cạnh thuộc min-cut.

💡 Gợi ý

Chạy max flow
BFS trên residual graph từ s → tập S = reachable
Cạnh (u, v) thuộc min-cut nếu u ∈ S, v ∉ S, và residual = 0

Liên kết học tiếp

Từ khóa glossary: max flow, luồng cực đại, Edmonds-Karp, Dinic, Ford-Fulkerson, min-cut, residual graph, augmenting path

Tìm kiếm liên quan: luồng cực đại, network flow, bipartite matching, min-cut, lát cắt tối thiểu

Luồng cực đại — Max Flow & Edmonds-Karp ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Edmonds-Karp — BFS augmenting paths ​

Dinic's Algorithm — blocking flow với level graph ​

Min-Cut Max-Flow Theorem ​

Thực chiến ​

Tình huống 1: Network capacity planning ​

Tình huống 2: Bipartite matching qua max flow ​

Sai lầm điển hình ​

❌ Sai lầm 1: Quên cạnh ngược (reverse edge) ​

❌ Sai lầm 2: Ford-Fulkerson với DFS trên capacity lớn ​

❌ Sai lầm 3: Undirected edge xử lý sai ​

Under the Hood ​

Hiệu năng ​

Min-Cut ↔ Max-Flow duality ​

Edmonds-Karp vs Dinic — khi nào dùng gì? ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Maximum Bipartite Matching — Intermediate ​

Bài 2: Network Bottleneck — Advanced ​

Liên kết học tiếp ​

Luồng cực đại — Max Flow & Edmonds-Karp

Bức tranh tư duy

Cốt lõi kỹ thuật

Edmonds-Karp — BFS augmenting paths

Dinic's Algorithm — blocking flow với level graph

Min-Cut Max-Flow Theorem

Thực chiến

Tình huống 1: Network capacity planning

Tình huống 2: Bipartite matching qua max flow

Sai lầm điển hình

❌ Sai lầm 1: Quên cạnh ngược (reverse edge)

❌ Sai lầm 2: Ford-Fulkerson với DFS trên capacity lớn

❌ Sai lầm 3: Undirected edge xử lý sai

Under the Hood

Hiệu năng

Min-Cut ↔ Max-Flow duality

Edmonds-Karp vs Dinic — khi nào dùng gì?

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Maximum Bipartite Matching — Intermediate

Bài 2: Network Bottleneck — Advanced

Liên kết học tiếp