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