Đồ thị tăng luồng

Đồ 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:

1. 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).
2. 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).
3. 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.

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:

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

• Đườ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:

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) ∉ G_f nên f(u, v) = c(u, v). Vậy:

Hình 3:

Đọ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

Liên kết ngoài

• Sách trực tuyến về Lý thuyết đồ thị
• Hướng dẫn về lý thuyết đồ thị Lưu trữ 2012-01-16 tại Wayback Machine
• Bài giảng của một môn học về các thuật toán đồ thị Lưu trữ 2005-08-31 tại Wayback Machine
• Minh họa hoạt hình về các thuật toán đồ thị
  • Lần bước thuật toán để tìm hiểu.
• Tóm tắt các trang minh họa thuật toán Lưu trữ 2008-06-01 tại Wayback Machine
• Dữ liệu test chuẩn cho các bài toán đồ thị con đầy đủ lớn nhất (Maximum Clique), tập con độc lập lớn nhất (Maximum Independent Set), phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring) Lưu trữ 2013-05-29 tại Wayback Machine
• Sưu tập ảnh số 1: một số mạng lưới thực
• Sưu tập ảnh số 1: một số mạng lưới thực Lưu trữ 2012-02-23 tại Wayback Machine
• Sưu tập các liên kết về đồ thị
• Các tạp chí lý thuyết đồ thị Lưu trữ 2013-07-04 tại Wayback Machine
• Sách về lý thuyết đồ thị Lưu trữ 2012-09-11 tại Wayback Machine