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

Tham khảo

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ị 
 Bài giảng của một môn học về các thuật toán đồ thị 
 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 
 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) 
 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 
 Sưu tập các liên kết về đồ thị
 Các tạp chí lý thuyết đồ thị 
 Sách về lý thuyết đồ thị 

Lý thuyết đồ thị
Đồ 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) =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< 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→ 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) =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 Tham khảo 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ị Bài giảng của một môn học về các thuật toán đồ thị 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 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 Indepen dent Set) , phủ đỉnh nhỏ nhất (Minimum Vertex Cover) và tô màu đỉnh (Vertex Coloring) Sưu tập ảnh số một số mạng lưới thực Sưu tập ảnh số một số mạng lưới thực Sưu tập các liên kết về đồ thị Các tạp chí lý thuyết đồ thị Sách về lý thuyết đồ thị Lý thuyết đồ thị