Bài giảng Luồng trên mạng V0.1 - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội
rong lý thuyết đồ thị, một luồng trên mạng, thường được gọi tắt là luồng, là một cách gán các luồng (dòng chảy) cho các cung của một đồ thị có hướng. Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!
Môn: Toán rời rạc (BKHN)
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
Preview text:
Luồng trên mạng V0.1 Trần Vĩnh Đức HUST Ngày 20 tháng 11 năm 2019 1 / 34 Tài liệu tham khảo
▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2006. 2 / 34 Nội dung
Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson
Luồng cực đại và lát cắt cực tiểu
Tính hiệu quả của thuật toán Network-flow algorithms 887 inflow equals outflow at every vertex con- (except the source and the sink) -
Local equilibrium in a flow network 0->1->3->5 0->2->4->5 0->1, 2->4, and 3->5 0 to 5 1 1->4 3->5 0->2->3->5 - ptg12441863 - Bài toán chuyển dầu tinyFN.txt standard drawing drawing with capacities drawing with flow flow representation source V 0 1 2.0 2.0 6 E 0 2 3.0 1.0 8 1 3 3.0 2.0 0 1 2.0 1 4 1.0 0.0 0 2 3.0 2 3 1.0 0.0 1 3 3.0 2 4 1.0 1.0 1 4 1.0 3 5 2.0 2.0 2 3 1.0 4 5 3.0 1.0 2 4 1.0 3 5 2.0 flow value 4 5 3.0 associated with each edge capacities sink
Anatomy of a network-flow problem 4 / 34 Mô hình bài bài toán a 2 d 3 10 1 2 s 3 b 1 1 t 4 5 c 5 e
▶ Đồ thị có hướng biểu diễn mạng đường ống, dầu có thể được
chuyển qua đường ống này
▶ Mục tiêu là chuyển dầu từ s đến t, nhiều nhất có thể. 5 / 34
Một luồng chuyển 7 đơn vị dầu từ s tới t luồng khả năng thông qua a 2/2 d 2/3 0/10 1/1 2/2 s 1/3 b 1/1 0/1 t 4/4 5/5 c 5/5 e
Liệu có cách nào làm tốt hơn? 6 / 34 Mạng Định nghĩa
Một mạng được định nghĩa là bộ G = (V, E, s, t, c), ở đây
▶ (V, E) là một đồ thị có hướng;
▶ s, t ∈ V, gọi là đỉnh nguồn và đỉnh đích; và
▶ c là một hàm gắn trên mỗi cạnh e của G một giá trị ce > 0
gọi là khả năng thông qua. Bài toán
Ta muốn chuyển nhiều dầu nhất có thể từ s tới t mà không vượt
quá khả năng thông qua trên mỗi cạnh. 7 / 34 Định nghĩa (Luồng)
Một luồng trên mạng G là một hàm
f : E −→ R+ ∪ {0},
gắn mỗi cạnh e của G với một giá trị số fe, sao cho:
1. Không vi phạm khả năng thông qua: 0 ≤ fe ≤ ce với mọi e ∈ E
2. Với mọi đỉnh u, ngoại trừ s và t, tổng luồng vào u bằng tổng luồng ra khỏi u: ∑ ∑ fwu = fuz. (w,u)∈E (u,z)
Nói cách khác, mạng là bảo toàn (theo luật Kirchhoff). 8 / 34
Luồng và lượng dầu chuyển luồng khả năng thông qua a 2/2 d 2/3 0/10 1/1 2/2 s 1/3 b 1/1 0/1 t 4/4 5/5 c 5/5 e 9 / 34 Định nghĩa
Giá trị của luồng là tổng lượng gửi từ s đến t. Theo luật bảo
toàn, size(f) bằng lượng rời khỏi s: ∑ size(f) = fsu. (s,u)∈E
▶ Mục đích của chúng ta là tìm được luồng có giá trị cực đại.
▶ Tương đương, tìm cách gán giá trị {fe : e ∈ E}
thỏa mãn một số ràng buộc.
▶ Đây là một bài toán quy hoạch tuyến tính. 10 / 34 Ví dụ
Bài toán tìm luồng cực đại trong mạng a 1 1 s 1 t 1 1 b
tương đương với bài toán quy hoạch tuyến tính max fsa + fsb
0 ≤ fsa, fsb, fab, fat, fbt ≤ 1
fsa = fat + fab
fsb + fab = fbt 11 / 34 Nội dung
Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson
Luồng cực đại và lát cắt cực tiểu
Tính hiệu quả của thuật toán Thuật toán tham lam
▶ Bắt đầu với luồng 0
▶ Lặp lại: Chọn một đường đi thích hợp từ s tới t và tăng
luồng nhiều nhất có thể dọc theo đường này. 13 / 34 Khởi tạo Tăng luồng a a 0/1 0/1 1/1 1/1 s 0/1 t s 0/1 t 0/1 0/1 0/1 0/1 b b Tăng luồng Luồng cực đại a a 1/1 1/1 1/1 1/1 s 0/1 t s 0/1 t 1/1 1/1 1/1 1/1 b b 14 / 34 Khởi tạo Tăng luồng a a 0/1 0/1 1/1 0/1 s 0/1 t s 1/1 t 0/1 0/1 0/1 1/1 b b
Hủy luồng trên cạnh a → b Luồng cực đại a a 1/1 1/1 1/1 1/1 s 0/1 t s 0/1 t 1/1 1/1 1/1 1/1 b b 15 / 34 Tìm đường tăng luồng
Tìm cạnh (u, v) có một trong hai kiểu
▶ (u, v) ∈ E và khả năng thông qua cuv vẫn chưa đầy. Khi đó
fuv có thể tăng thêm nhiều nhất là cuv − fuv.
▶ (v, u) ∈ E và có một luồng qua đó, tức là fvu > 0. Khi đó ta
có thể giảm một phần hoặc toàn bộ fvu. 16 / 34 Đường tăng luồng Cạnh gốc Cạnh ngược
▶ e = (u, v) ∈ E ▶ eR = (v, u) ▶ Luồng fe
▶ “Giảm” luồng fe đã gửi ▶ Khả năng ce
Khả năng thông qua còn lại Ví dụ a { 1/1 0/1 c s 1/1 t cf e − fe nếu e ∈ E (e) = f 0/1 e nếu eR ∈ E. 1/1 b 17 / 34 Đồ thị tăng luồng Định nghĩa
Đồ thị tăng luồng của mạng G với luồng f là đồ thị
Gf = (V, Ef, cf) với
Ef = {e : fe < ce} ∪ {eR : fe > 0}. Ví dụ
Mạng G với luồng f và đồ thị tăng luồng Gf tương ứng. a a 1/1 0/1 1 1 s 1/1 t s 1 t 0/1 1/1 1 1 b b 18 / 34 Đường tăng luồng Định nghĩa
▶ Một đường tăng luồng là một đường đi từ s đến t trong đồ thị tăng luồng Gf.
▶ Khả năng thông qua của đường tăng luồng P là
cf(P) = min{cf(e) : e ∈ P} Augment(f, c, P)
δ = cf(P) foreach cạnh e ∈ P:
if (e ∈ E) fe = fe + δ else
f(eR) = f(eR) − δ return f 19 / 34 Thuật toán Ford-Fulkerson Ford-Fulkerson (G)
foreach cạnh e ∈ E: fe = 0
Gf = đồ thị tăng luồng của G và f
while (còn đường tăng luồng P trong Gf):
f = Augment(f, c, P) Cập nhật Gf return f 20 / 34