

Đồ thị tăng luồng 

 Giả sử f là một luồng trên mạng G = (V, E). Từ mạng G = (V, E) ta xây dựng đồ thị có trọng số trên cung Gf = (V, Ef) với tập cung Ef và trọng số trên các cung được xác định theo quy tắc sau:
 Nếu e = (u, v) ∈ E với f(u, v) = 0 thì (u, v) ∈ Ef với trọng số c(u, v).
 Nếu e = (u, v) ∈ E với f(u, v) = c(u, v) thì (v, u) ∈ Ef với trọng số f(u, v).
 Nếu e = (u, v) ∈ E với 0 < f(u, v) < c(u, v) thì (u, v) ∈ Ef với trọng số c(u, v) – f(u, v) và (v, u) ∈ Ef với trọng số f(u, v).
 Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại được gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.

Tăng luồng 
 Giả sử P = (s = v0, v1, v2… vk = t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi k là trọng số cung nhỏ nhất trên đường đi P. Xây dựng luồng f’ theo quy tắc sau:
 f’(u, v) = f(u, v) + k, nếu (u, v) ∈ P là cung thuận.
 f’(u, v) = f(u, v) – k, nếu (u, v) ∈ P là cung nghịch.
 f’(u, v) = f(u, v) nếu (u, v) ∉ P.
 Dễ dàng kiểm tra được rằng f’ xây dựng như trên là luồng trong mạng và val(f’) = val(f) + k.
 Thủ tục tăng luồng này gọi là tăng luồng dọc theo đường P.

Đường tăng luồng 
 Đường tăng luồng f là mọi đường đi từ s đến t trên đồ thị tăng luồng Gf.
 Các mệnh đề dưới đây là tương đương:
 f là luồng cực đại trong mạng.
 Không tìm được đường tăng luồng f.
 val(f) = c(X, X*) với một lát cắt (X, X*) nào đó.

Chứng minh
 CM 2 → 3: Ký hiệu X là tập các đỉnh đến được từ s, Đặt X* = V\X. Lúc đó (X, X*) là lát cắt và f(u, v) = 0 với mọi u ∈ X* và v ∈ X. Do đó:

 với u ∈ X* và v ∈ X, do (u, v) ∉ Gf nên f(u, v) = c(u, v). Vậy:

Đọc thêm 
 Lát cắt (lý thuyết đồ thị)
 Thuật toán Ford-Fulkerson
 Định lý luồng cực đại lát cắt cực tiểu
 Luồng trên mạng
 Luồng cực đại