Đồ 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 G_f = (V, E_f) với tập cung E_f 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) ∈ E_f 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) ∈ E_f 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) ∈ E_f với trọng số c(u, v) – f(u, v) và (v, u) ∈ E_f với trọng số f(u, v).

• Các cung của G_f đồ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ị G_f được gọi là đồ thị tăng luồng. khung|giữa|Hình 1: Ví dụ về đồ thị tăng luồng

Tăng luồng

• Giả sử P = (s = v₀, v₁, v₂… v_k = t) là một đường đi từ s đến t trên đồ thị tăng luồng G_f. 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 G_f.
• 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 đó: khung|giữa|Hình 2:
• với u ∈ X^* và v ∈ X, do (u, v) ∉ G_f nên f(u, v) = c(u, v). Vậy: khung|giữa|Hình 3: