Đồ thị tăng luồng

Thêm liên kết
Bách khoa toàn thư mở Wikipedia

Đồ thị tăng luồng[sửa | sửa mã nguồn]

  • 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:
  1. Nếu e = (u, v) ∈ E với f(u, v) = 0 thì (u, v) ∈ Ef với trọng số c(u, v).
  2. 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).
  3. 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.
Hình 1: Ví dụ về đồ thị tăng luồng

Tăng luồng[sửa | sửa mã nguồn]

  • 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:
  1. f’(u, v) = f(u, v) + k, nếu (u, v) ∈ P là cung thuận.
  2. f’(u, v) = f(u, v) – k, nếu (u, v) ∈ P là cung nghịch.
  3. 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[sửa | sửa mã nguồn]

  • Đườ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:
  1. f là luồng cực đại trong mạng.
  2. Không tìm được đường tăng luồng f.
  3. 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 đó:
Hình 2:
  • với u ∈ X* và v ∈ X, do (u, v) ∉ Gf nên f(u, v) = c(u, v). Vậy:
Hình 3:

Đọc thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Đồ_thị_tăng_luồng&oldid=70757530”