I. Bài toán Luồng Cực Đại (Max Flow Problem)

Hãy tưởng tượng bạn đang quản lý hệ thống ống nước của một thành phố. Nước xuất phát từ nhà máy, chảy qua hàng loạt đường ống lớn nhỏ, rồi đến tay người dùng. Mỗi đường ống chỉ chịu được một lượng nước nhất định — vượt quá là vỡ ống.

Câu hỏi đặt ra: Làm thế nào để bơm được nhiều nước nhất có thể từ nhà máy đến thành phố, mà không làm vỡ bất kỳ đường ống nào?

Đó chính xác là bài toán Max Flow — và nó xuất hiện ở khắp nơi trong thực tế:

• 🌐 Mạng máy tính: Tối đa băng thông truyền dữ liệu giữa hai máy chủ
• 🚗 Giao thông: Điều phối xe qua các tuyến đường không bị tắc nghẽn
• 🏭 Logistics: Tối ưu luồng hàng hóa qua chuỗi cung ứng

Trong bài viết này, chúng ta sẽ cùng tìm hiểu cách máy tính giải quyết bài toán này thông qua thuật toán Ford-Fulkerson — một trong những thuật toán kinh điển và trực quan nhất trong lĩnh vực này.

II. Quick Recap Graph Theory

1. Graph là gì?

Một đồ thị (graph) $G$ được định nghĩa là một cặp $G = (V, E)$, trong đó:

• $V$ là tập hợp các đỉnh (vertices/nodes)
• $E$ là tập hợp các cạnh (edges), mỗi cạnh kết nối hai đỉnh Ví dụ trực quan: Mạng lưới đường phố — mỗi ngã tư là một đỉnh, mỗi con đường là một cạnh.

2. Phân loại đồ thị

2.1 Đồ thị vô hướng vs. có hướng

Loại	Mô tả	Ký hiệu cạnh
Undirected Graph	Cạnh không có chiều, đi được cả hai phía	$(u, v)$
Directed Graph (Digraph)	Cạnh có chiều (mũi tên), chỉ đi được một chiều	$(u \to v)$

VD:

Ta có: Graph a)

$G = (V, E)$

$V = \{1,2,3,4,5,6,7\}$

$E = \{ (1,2), (2,3), (2,4), (3,4), (4,5), (5,6), (6,7),(3,7)\}$

Graph b)

$G = (V, E)$

$V = \{1,2,3,4,5,6,7\}$

$E = \{(1→2), (2→3), (2→4), (3→4), (4→5), (6→5), (7→6), (3→7)\}$

2.2 Đồ thị có trọng số (Weighted Graph)

Mỗi cạnh được gán một trọng số (weight) — trong bài toán Max Flow, trọng số này chính là capacity (sức chứa) của cạnh đó. VD:

Ta có: Capacity của: $(S→A) = 1, (S→C) = 2, ... ,(B→E)=2$

III. Max Flow with Ford-Fulkerson

( Để hiểu nhanh thuật toán skip đến Part 3 và 4 để hiểu cách thuật toán hoạt động rồi quay lại Part 1,2 😁😁😁)

1. Các ký hiệu và Khái niệm cơ bản

Để hiểu thuật toán, trước hết chúng ta cần nắm rõ các thành phần cấu tạo nên một "Mạng luồng":

• $G = (V, E)$: Đồ thị có hướng với $V$ là tập các đỉnh (vertices) và $E$ là tập các cạnh (edges).

• $s$ (Source - Đỉnh nguồn): Nơi luồng nước/dòng điện bắt đầu đi ra (không có cạnh đi vào).

• $t$ (Sink - Đỉnh đích): Nơi luồng nước/dòng điện đổ về (không có cạnh đi ra).

• $c(u, v)$ (Capacity - Sức chứa): Trọng số của cạnh hướng từ $u$ đến $v$. Đây là lượng tối đa mà cạnh đó có thể tải (ví dụ: đường kính ống nước). Nếu không có cạnh giữa $u$ và $v$, $c(u, v) = 0$.

• $f(u, v)$ (Flow - Luồng hiện tại): Lượng dữ liệu/nước thực tế đang chảy qua cạnh từ $u$ đến $v$.

Ba điều kiện bắt buộc của một Luồng hợp lệ:

1. Giới hạn sức chứa (Capacity Constraint): Luồng trên một cạnh không được vượt quá sức chứa của nó:

   $$0 \le f(u, v) \le c(u, v)$$

2. Tính phản đối xứng (Skew Symmetry): Luồng đi theo chiều ngược lại ký hiệu là số âm:

   $$f(u, v) = -f(v, u)$$

3. Bảo toàn luồng (Flow Conservation): Tổng luồng đi vào một đỉnh (trừ $s$ và $t$) phải bằng tổng luồng đi ra khỏi đỉnh đó:

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

2. Các khái niệm cốt lõi của Ford-Fulkerson

Thuật toán Ford-Fulkerson không chạy "mù quáng" mà dựa trên hai khái niệm cực kỳ quan trọng sau:

Mạng thặng dư (Residual Network - $G_f$)

Là một đồ thị mô phỏng "khả năng còn lại" của mạng lưới tại thời điểm hiện tại. Nó cho biết ta có thể thêm bao nhiêu luồng vào một cạnh, hoặc có thể "rút bớt" bao nhiêu luồng từ cạnh đó.

• Mỗi cạnh trong mạng thặng dư sẽ có sức chứa thặng dư (Residual Capacity), ký hiệu là $c_f(u, v)$:

  $$c_f(u, v) = c(u, v) - f(u, v)$$

• Cạnh xuôi (Forward edge): Nếu $f(u, v) < c(u, v)$, ta có thể tăng luồng thêm tối đa $c_f(u, v)$.

• Cạnh ngược (Backward edge): Nếu $f(u, v) > 0$, ta có một cạnh ngược trong mạng thặng dư với $c_f(v, u) = f(u, v)$ (nghĩa là ta có quyền "hủy bỏ" hay giảm bớt luồng đã gửi trước đó).

Đường tăng luồng (Augmenting Path)

Là một đường đi đơn từ đỉnh nguồn $s$ đến đỉnh đích $t$ trên mạng thặng dư $G_f$, sao cho tất cả các cạnh trên đường đi này đều có sức chứa thặng dư lớn hơn 0 ($c_f(u, v) > 0$).

3. Các bước thực hiện thuật toán

Ý tưởng chính của Ford-Fulkerson rất đơn giản: Chừng nào còn tìm được đường tăng luồng từ $s$ đến $t$, thì ta còn tăng luồng của hệ thống lên.

Quy trình các bước chi tiết:

• Bước 1: Khởi tạo

  • Đặt luồng trên tất cả các cạnh bằng 0: $f(u,v)=0$ với mọi $(u,v) \in E$.
  • Khởi tạo mạng thặng dư $G_f$ với $c_f(u,v)=c(u,v)$ với mọi cạnh gốc, và $c_f(v,u)=0$ với mọi cạnh ngược tương ứng.
  • Khởi tạo Max_Flow = 0.

• Bước 2: Tìm đường tăng luồng

  • Sử dụng một thuật toán tìm kiếm (như DFS hoặc BFS) để tìm một đường đi $P$ từ $s$ đến $t$ trên $G_f$. (chỉ đi qua các cạnh có $c_f(u,v)>0$.
  • Nếu không tìm thấy đường đi nào nữa $\rightarrow$ Dừng thuật toán. Chuyển sang Bước 5.
  • Nếu tìm thấy → Chuyển sang Bước 3.

• Bước 3: Xác định chai cổ chai (Bottleneck)

  • Tìm cạnh có sức chứa thặng dư nhỏ nhất trên đường đi $P$ vừa tìm được. Gọi giá trị này là $\Delta$ (delta):

    $$\Delta = \min \{ c_f(u, v) \mid (u, v) \in P \}$$

• Bước 4: Cập nhật luồng trên toàn mạng

  • Với mỗi cạnh $(u, v)$ thuộc đường đi $P$:
  • 4a. Cập nhật luồng trên đồ thị gốc:
    • Nếu $(u,v)$ là cạnh xuôi (tồn tại trong đồ thị gốc $G$):
      • $f(u,v)=f(u,v)+Δ$
    • Nếu $(u,v)$ là cạnh ngược trong $G_f$ (cạnh gốc là $(v,u)$ trong $G$):
      • $f(v,u)=f(v,u)−Δ$
  • 4b. Cập nhật mạng thặng dư $G_f$:
    • Với mỗi cạnh $(u, v)$ thuộc $P$:
      • $c_f(u,v)=c_f(u,v)−Δ$
      • $c_f(v,u)=c_f(v,u)+Δ$
  • 4c. Cập nhật tổng luồng: $MaxFlow=MaxFlow+Δ$ → Quay lại Bước 2.

• Bước 5: Kết thúc

  • Không còn đường tăng luồng nào từ $s$ đến $t$ trong $G_f$.
  • Giá trị Max_Flow hiện tại chính là luồng cực đại của mạng.

4. Ví dụ thực tế:

Lấy graph: Bước 1: Khởi tạo

Bước 2: Tìm đường tăng luồng

• Sử dụng một thuật toán tìm kiếm (như DFS hoặc BFS) để tìm một đường đi $P$ từ $s$ đến $t$ trên $G_f$. (chỉ đi qua các cạnh có $c_f(u,v)>0$.
  • Ta ví dụ giả định thu được đoạn đường có path sau: S→A→B→E

Bước 3: Xác định chai cổ chai (Bottleneck)

• Tìm cạnh có sức chứa thặng dư nhỏ nhất trên đường đi $P$ vừa tìm được. Gọi giá trị này là $\Delta$ (delta):

$$\Delta = \min \{c_f(S,A), c_f(A,B), c_f(B,E) \} =\min \{3,3,2 \} = 2$$

Bước 4: Cập nhật luồng trên toàn mạng!

Với mỗi cạnh $(u, v)$ thuộc đường đi $P$: Dựa theo graph ở trên: 4a)
$f(S, A) = f(S, A) + 2 = 0 + 2$
$f(A, S) = f(A, S) - Δ = 0 + 2$

$f(A, B) = f(A, B) + Δ$
...

4b)
$c_f(S, A)=c_f(S, A)−Δ = 3 - 2 =1$
$c_f(A, S)=c_f(A, S)+Δ = 0 + 2 = 2$

$c_f(A, B)=c_f(A, B)-Δ$
...

4c)
$MaxFlow=MaxFlow+2 = 0 + 2 = 2$
Lưu ý: trong code ta không cần chú ý bước 4a chỉ cần 4b và 4c để ta đủ tìm max flow→ Quay lại Bước 2.

LẶP LẦN 1:

Bước 2: Tìm đường tăng luồng và Bước 3: Xác định chai cổ chai (Bottleneck) path: S→A→B→D→E

$$\Delta = \min \{c_f(S,A), c_f(A,B), c_f(B,D), c_f(D,E) \} =\min \{1,1,3,6 \} = 1$$

Bước 4: Cập nhật luồng trên toàn mạng

4b)

$c_f(S, A)=c_f(S, A)−Δ = 1 - 1 = 0$

$c_f(A, S)=c_f(A, S)+Δ = 2 + 1 = 3$

$c_f(A, B)=c_f(A, B)-Δ$

...

4c)

$MaxFlow=MaxFlow+1 = 2 + 1 = 3$

LẶP LẦN 2:

Bước 2: Tìm đường tăng luồng và Bước 3: Xác định chai cổ chai (Bottleneck)

$$\Delta = \min \{path: S→C→A→D→E\} = \min \{7,5,4,5 \} = 4$$

Bước 4: Cập nhật luồng trên toàn mạng

$MaxFlow=7$ LẶP LẦN 3:

Bước 2: Tìm đường tăng luồng và Bước 3: Xác định chai cổ chai (Bottleneck)

$$\Delta = \min \{path: S→C→D→E\} = 1$$

Bước 4: Cập nhật luồng trên toàn mạng

$MaxFlow=8$

LẶP LẦN 4:

• không tìm thấy đường đi nào nữa $\rightarrow$ Dừng thuật toán. Chuyển sang Bước 5.
• Bước 5: Kết thúc
• Không còn đường tăng luồng nào từ $s$ đến $t$ trong $G_f$ -> Giá trị Max_Flow = 8

5. Lưu ý quan trọng về Độ phức tạp (Định lý Edmonds-Karp)

• Thuật toán Ford-Fulkerson nguyên bản không quy định cụ thể cách bạn tìm đường tăng luồng (DFS hay BFS). Nếu dùng DFS, trong trường hợp xấu nhất với các số nguyên, độ phức tạp có thể lên tới $O(|E| \cdot f^*)$ (với $f^*$ là giá trị luồng cực đại).

• Nếu ta bắt buộc dùng BFS để luôn tìm đường đi ngắn nhất (ít cạnh nhất), thuật toán này được gọi là Thuật toán Edmonds-Karp. Độ phức tạp lúc này sẽ được cố định và tối ưu hơn rất nhiều: $O(|V| \cdot |E|^2)$, không còn phụ thuộc vào giá trị của luồng nữa.

6. Reference

https://pub.aimind.so/introduction-to-graph-theory-336ab875c8ca https://36-750.github.io/ox-hugo/network1.png https://www.w3schools.com/dsa/dsa_theory_graphs_maxflow.php https://www.w3schools.com/dsa/dsa_algo_graphs_fordfulkerson.php