Published Thứ Năm, 9:30 SA 9 min read

Goldberg–Tarjan Push-Relabel Max Flow

I. Nhắc lại kiến thức từ thuật toán Ford-Fulkerson

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

Thuật toán Push-Relabel hoạt động trên cùng nền tảng mạng luồng như Ford-Fulkerson. Các ký hiệu cơ bản giữ nguyên:

$G = (V, E)$ : Đồ thị có hướng với $V$ là tập đỉnh và $E$ là tập cạnh.
$s$ (Source - Đỉnh nguồn): Nơi luồng bắt đầu đi ra.
$t$ (Sink - Đỉnh đích): Nơi luồng đổ về.
$c(u, v)$ (Capacity - Sức chứa): Lượng tối đa có thể truyền qua cạnh $(u, v)$ . Nếu không có cạnh, $c(u, v) = 0$ .
$f(u, v)$ (Flow - Luồng hiện tại): Lượng thực tế đang chảy qua cạnh $(u, v)$ .
$c_f(u, v)$ (Residual Capacity - Sức chứa thặng dư):

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

Điểm khác biệt cốt lõi với Ford-Fulkerson:

Ford-Fulkerson duy trì một luồng hợp lệ (bảo toàn luồng tại mọi đỉnh trung gian) và tăng dần theo từng đường $s \to t$ . Push-Relabel thay vào đó duy trì một tiền luồng (preflow) — cho phép các đỉnh trung gian tạm thời có lượng dư — rồi dần dần "cân bằng" lại bằng hai thao tác Push và Relabel.

II. Push-Relabel cho Max Flow Problem

( Để 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 😁😁😁)

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

Tiền luồng (Preflow)

Một hàm $f: V \times V \to \mathbb{R}$ là tiền luồng nếu thỏa mãn:

Giới hạn sức chứa: $0 \le f(u, v) \le c(u, v)$ với mọi $(u, v)$ .
Không bảo toàn âm (Non-negative excess): Tổng luồng vào không nhỏ hơn tổng luồng ra tại mọi đỉnh $v \neq s$ :

$\sum_{u \in V} f(u, v) \ge 0$

Khác với luồng hợp lệ (yêu cầu bằng 0), tiền luồng cho phép đỉnh trung gian "giữ lại" một lượng dư tạm thời.

Lượng dư tại đỉnh (Excess - $e(v)$ )

Lượng luồng "bị kẹt" tại đỉnh $v$ , chưa được đẩy tiếp:

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

Nếu $e(v) > 0$ : đỉnh $v$ đang "thừa" luồng, gọi là đỉnh active.
Điều kiện kết thúc: không còn đỉnh active nào (ngoài $s$ và $t$ ).

Hàm nhãn độ cao (Height function - $h$ )

Một hàm nguyên $h: V \to \mathbb{Z}_{\ge 0}$ là hàm nhãn hợp lệ nếu:

$h(s) = |V|, \quad h(t) = 0$

Và với mọi cạnh có $c_f(u, v) > 0$ trong mạng thặng dư:

$h(u) \le h(v) + 1$

Hàm nhãn $h$ đóng vai trò như "độ dốc": luồng chỉ được đẩy từ nơi cao xuống nơi thấp hơn đúng 1 bậc.

Cạnh chấp nhận được (Admissible Edge) (cạnh khả thi)

Cạnh $(u, v)$ trong mạng thặng dư được gọi là admissible (cạnh khả thi) nếu:

$c_f(u, v) > 0 \quad \text{và} \quad h(u) = h(v) + 1$

Chỉ có thể thực hiện thao tác Push trên cạnh admissible.

Đỉnh active

Đỉnh $v \neq s, t$ được gọi là active nếu $e(v) > 0$ . Thuật toán tiếp tục chừng nào còn tồn tại đỉnh active.

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

( Để 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 😁😁😁)

Ý tưởng chính: Bão hòa tất cả cạnh xuất phát từ $s$ ngay từ đầu, tạo ra các đỉnh active, rồi lần lượt "đẩy" lượng dư này xuống $t$ (hoặc trả ngược về $s$ ) thông qua hai thao tác Push và Relabel.

Thao tác PUSH(u, v)

Điều kiện áp dụng: $e(u) > 0$ và $(u, v)$ là cạnh admissible ( $c_f(u,v) > 0$ và $h(u) = h(v) + 1$ ).

Thực hiện: Đẩy một lượng $\delta$ từ $u$ sang $v$ :

$\delta = \min(e(u),\ c_f(u, v))$

Cập nhật:

$f(u, v) = f(u, v) + \delta \quad \Rightarrow \quad c_f(u,v) = c_f(u,v) - \delta, \quad c_f(v,u) = c_f(v,u) + \delta$

$e(u) = e(u) - \delta, \quad e(v) = e(v) + \delta$

Nếu $\delta = c_f(u,v)$ : gọi là saturating push (cạnh bị bão hòa).
Nếu $\delta < c_f(u,v)$ : gọi là non-saturating push (đỉnh $u$ hết dư).

Thao tác RELABEL(u)

Điều kiện áp dụng: $e(u) > 0$ và không tồn tại cạnh admissible nào xuất phát từ $u$ (tức là với mọi $v$ có $c_f(u,v) > 0$ đều có $h(u) \le h(v)$ ).

Thực hiện: Nâng nhãn $u$ lên đủ cao để tạo ra ít nhất một cạnh admissible:

$h(u) = 1 + \min\{\ h(v) \mid c_f(u, v) > 0\ \}$

Relabel không thay đổi luồng, chỉ thay đổi nhãn để "mở đường" cho Push tiếp theo.

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

Bước 1: Khởi tạo
- Đặt $h(s) = |V|, e(S) = -\infty$ .
- Đặt $h(v) = 0,e(v) = 0, \quad \forall v \in V \setminus \{s\}$
- Với mọi cạnh $(s, v) \in E$ $(s, v) \in E$ : bão hòa hoàn toàn (saturate):
  - $f(s, v) = c(s, v)$
  - $c_f(s, v) = 0$ , $c_f(v, s) = c(s, v)$
  - $e(v) = c(s, v)$ , $e(s) = e(s) - c(s, v)$
- Với mọi cạnh còn lại: $f(u, v) = 0$ .
Bước 2: Chọn đỉnh active
- Tìm một đỉnh $u \neq s, t$ có $e(u) > 0$ .
- Nếu không còn đỉnh active nào $\rightarrow$ Dừng. Chuyển sang Bước 4.
- Nếu tìm thấy $u$ $\rightarrow$ Chuyển sang Bước 3.
Bước 3: Kiểm tra cạnh admissible từ $u$
- Kiểm tra xem có tồn tại cạnh $(u, v)$ với $c_f(u,v) > 0$ và $h(u) = h(v) + 1$ không.
- Nếu có $\rightarrow$ Thực hiện PUSH$(u, v)$, quay lại Bước 2.
- Nếu không có $\rightarrow$ Thực hiện RELABEL$(u)$, quay lại Bước 3 (kiểm tra lại sau khi nâng nhãn).
Bước 4: Kết thúc
- Khi không còn đỉnh active (ngoài $s$ và $t$ ), tiền luồng hiện tại là luồng hợp lệ cực đại.
- Giá trị luồng cực đại chính là lượng dư tại đỉnh đích:
$\text{Max Flow} = e(t)$

4. Ví dụ

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

Đặt $h(S) = |V| = 6$ , $e(S) = -\infty$ .
- Đặt $h(v) = 0,e(v) = 0, \quad \forall v \in V \setminus \{s\}$ $h (v) = 0, e (v) = 0, \forall v \in V ∖ {s}$
  - Với mọi cạnh $(s, v) \in E$ : bão hòa hoàn toàn (saturate) ở đây ta có cạnh $(S,A), (S,C)$ :
  - Ta có
    - $f(S, A) = c(S, A) = 3$
    - $f(S, C) = c(S, C) = 7$
    - $c_f(S, A) = 0$ , $c_f(A, S) = c(S, A) = 3$
    - $c_f(S, C) = 0$ , $c_f(C, S) = c(S, C) = 7$
    - $e(A) = c(S, A) = 3$ , $e(S) = e(S) - c(S, A) = -\infty - 3 = -\infty$
    - $e(C) = c(S, C) = 7$ , $e(S) = e(S) - c(S, C) = -\infty - 7 = -\infty$
  - Với mọi cạnh còn lại: $f(u, v) = 0$ như $f(A, D) = f(A, B)= ... = 0$

Bước 2: Chọn đỉnh active

Tìm một đỉnh $u \neq s, t$ có $e(u) > 0$ .
- Ta giả định tìm thấy $A$ $\rightarrow$ Chuyển sang Bước 3.
Bước 3: Kiểm tra cạnh admissible từ $u$
- Ta kiểm tra có tồn tại cạnh $(A, v)$ với $c_f(A,v) > 0$ và $h(A) = h(v) + 1$ không . (Ta có thể thấy nhiều cạnh từ A -> v có $c_f(A,v) > 0$ nhưng lại ko thỏa mãn đk $h(A) = h(v) + 1$ )
- Ta thực hiện RELABEL(A), quay lại Bước 3 (kiểm tra lại sau khi nâng nhãn).
- RELABEL(A)
  - Vì $e(A) >0$ và không tồn tại cạnh admissible (hãy dễ hiểu hơn ko có đỉnh nào có $h(v)< h(A)$ và đồng thời thoat mãn điều kiện có $c_f(A,v) > 0$ )
$h(A) = 1 + \min\{c_f(A, S), c_f(A, C), c_f(A, B), c_f(A, D) \} = 1 +\min\{-\infty,0,0,0\} = 1$
- quay lại Bước 3:
- Ta thấy có tồn tại cạnh $(A, B)$ với $c_f(A,B) = 3 > 0$ và $h(A) = h(B) + 1$
- PUSH(A, B)
  - Lúc này cạnh (A,B) đã admissible
  - $\delta = \min(e(A),\ c_f(A, B)) = \min\{3,3\} = 3$
  - Cập nhật:
    - $f(A, B) = f(A, B) + \delta \quad = 0 + 3 =3$
    - $\Rightarrow \quad c_f(A,B) = c_f(A,B) - \delta = 3 - 3 = 0, \quad c_f(B,A) = c_f(B,A) + \delta = 0 + 3 = 3$
    - $e(A) = e(A) - \delta = 3-3 = 0, \quad e(B) = e(B) + \delta = 0 + 3 =3$

(Ta tiếp tục vòn lặp khi $e(u) >0, \forall u \in V$ ) LẶP LẦN 1:

Bước 2: Chọn đỉnh active

Tìm một đỉnh $u \neq s, t$ $u \neq = s, t$ có $e(u) > 0$ $e (u) > 0$ .
- Ta giả định tìm thấy $B$ $\rightarrow$ Chuyển sang Bước 3. Bước 3: Ta kiểm tra có tồn tại cạnh $(B, v)$ với $c_f(B,v) > 0$ và $h(B) = h(v) + 1$ không .
Vì ko có ta thực hiện bước RELABEL(B) và PUSH(B, E) Tuy nhiên ở đây ta có:
$\delta = \min(e(B),\ c_f(B, E)) = \min\{3,2\} = 2$
Cập nhật:
- $f(B, E) = f(B, E) + \delta \quad = 0 + 2 =2$
- $\Rightarrow \quad c_f(B,E) = c_f(B,E) - \delta = 2 - 2 = 0, \quad c_f(E,B) = c_f(E,B) + \delta = 0 + 2 = 2$
- $e(B) = e(B) - \delta = 3-2 = 1, \quad e(E) = e(E) + \delta = 0 + 2 =2$ (Bạn có thể thấy hiện tại $e(B)$ = 1 do trước đó khi chảy vào E capacity (B,E) = 2)

LẶP LẦN 2: Bước 2: Chọn đỉnh active

Tìm một đỉnh $u \neq s, t$ $u \neq = s, t$ có $e(u) > 0$ $e (u) > 0$ .
- Ta giả định tìm thấy $C$ $\rightarrow$ Chuyển sang Bước 3. Bước 3: Ta kiểm tra có tồn tại cạnh $(C, v)$ với $c_f(C,v) > 0$ và $h(C) = h(v) + 1$ không .
Vì ko có ta thực hiện bước RELABEL(C) và PUSH(C, D) (Bạn có thể thấy hiện tại $e(C)$ = 4 do trước đó khi chảy vào D capacity (C,D) = 3)

LẶP LẦN 3: Bước 2: Chọn đỉnh active

Tìm một đỉnh $u \neq s, t$ $u \neq = s, t$ có $e(u) > 0$ $e (u) > 0$ .
- Ta giả định tìm thấy $D$ $\rightarrow$ Chuyển sang Bước 3. Bước 3: Ta kiểm tra có tồn tại cạnh $(D, v)$ với $c_f(D,v) > 0$ và $h(D) = h(v) + 1$ không .
Vì ko có ta thực hiện bước RELABEL(D) và PUSH(D, E)

LẶP LẦN 4: Bước 2: Chọn đỉnh active

Tìm một đỉnh $u \neq s, t$ $u \neq = s, t$ có $e(u) > 0$ $e (u) > 0$ .
- Ta giả định tìm thấy $C$ $\rightarrow$ Chuyển sang Bước 3. Bước 3: Ta kiểm tra có tồn tại cạnh $(C, v)$ với $c_f(C,v) > 0$ và $h(C) = h(v) + 1$ không .
Vì ko có ta thực hiện bước RELABEL(C) và PUSH(C, A)

LẶP LẦN 5:

LẶP LẦN 6:

LẶP LẦN 7:

Dù trực quan ta thấy không còn đường có thể đi vào E nữa những thuật toán vẫn tiếp tục do vẫn thỏa mãn điều kiện ở Bước 2: Tìm một đỉnh $u \neq s, t$ có $e(u) > 0$ . Do đó các đỉnh còn $e(u)>0$ sẽ chạy về S đến khi các còn lại $e(u) \leq 0$ (Note: $e(S) < 0$ trường hợp duy nhất bé hơn 0 do ta quy định từ đầu $e(S) = -\infty$ )

Cuối cùng ta sẽ thu được $\text{Max Flow} = e(E) = 8$ khi vòng lặp kết thúc.

5. Lưu ý quan trọng về Độ phức tạp

Biến thể	Chiến lược chọn đỉnh active	Độ phức tạp
Generic Push-Relabel	Tùy ý	$O(V^2 E)$
FIFO Push-Relabel	Hàng đợi FIFO	$O(V^3)$
Highest-label Push-Relabel	Đỉnh có $h(u)$ lớn nhất	$O(V^2 \sqrt{E})$

So với Ford-Fulkerson ( $O(E \cdot f^*)$ , phụ thuộc vào giá trị luồng) và Edmonds-Karp ( $O(VE^2)$ ), Push-Relabel với FIFO đạt $O(V^3)$ — không phụ thuộc vào giá trị luồng hay số cạnh theo cách tệ nhất.
Trong thực tế, biến thể Highest-label với $O(V^2\sqrt{E})$ thường là lựa chọn tốt nhất cho đồ thị dày.
Thuật toán này đặc biệt hiệu quả trên các mạng lớn hoặc mạng có giá trị capacity rất lớn, nơi Ford-Fulkerson trở nên không thực tế.

III. References

https://en.wikipedia.org/wiki/Push–relabel_maximum_flow_algorithm https://www.geeksforgeeks.org/dsa/introduction-to-push-relabel-algorithm/ https://www.youtube.com/watch?v=LjNzXyjMu5w (video ví dụ trực quan)