Bài giảng Lý thuyết đồ thị - Chương 8: Luồng trong mạng

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 8: Luồng trong mạng

1. Môn học: Lý thuyết đồ thị Chương 8: Luồng trong mạng Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
2. Nội dung I. Bài toán luồng cực đại II. Định lý Ford-Fulkerson III. Thuật toán tìm luồng cực đại trong mạng Chương 8 – Luồng trong mang 2 Lý thuyết đồ thị
3. I. Bài toán luồng cực đại ™Mạng Mạng là một đồ thị có hướng G= (V, E) ƒ ∃! đỉnh s (Điểm phát) mà deg-(s) = 0 ƒ ∃! đỉnh t (Điểm thu) mà deg+(t) = 0 ƒ ∀ cung e = (v, w) ∈ E được gán với một số không âm c(e) = c(v, w) ≥ 0 gọi là Khả năng thông qua của cung e. s : Điểm phát t : Điểm thu Nếu không có cung (v, w) thì c(v, w) = 0 Chương 8 – Luồng trong mang 3
4. I. Bài toán luồng cực đại ™ Luồng trong mạng ƒ Cho mạng G= (V, E), ta gọi luồng f trong mạng G là một ánh xạ f: E Æ R*, với mọi cung e=(v, w) E được gán với một số không âm f(e) = f(v, w) ≥ 0 gọi là luồng trên cung e, thỏa mãn các điều kiện sau: • Luồng trên mỗi cung e E không vượt quá khả năng thông qua của nó: 0 ≤ f(e) ≤ c(e) • Với mọi đỉnh v không trùng với đỉnh phát s, và đỉnh thu t, tổng luồng trên các cung đi vào v bằng tổng luồng các cung đi ra khỏi v. Div f (v) = ∑ f (w,v) − ∑ f (v,w) = 0 w∈Γ− (v) w∈Γ+ (v) Γ − (v) = {w ∈V | (w,v) ∈ E} Với Γ + (v) = {w ∈V | (v, w) ∈ E} Điều kiện cân bằng luồng Chương 8 – Luồng trong mang 4
5. I. Bài toán luồng cực đại ™ Luồng trong mạng ƒ Giá trị của luồng f là tổng luồng trên các cung đi ra khỏi đỉnh phát (bằng tổng luồng trên các cung đi vào đỉnh thu). val ( f ) = ∑ f (s, w) = ∑ f (w, t) w∈Γ + ( s ) w∈Γ − (t ) Chương 8 – Luồng trong mang 5
6. I. Bài toán luồng cực đại ™ Luồng trong mạng 2 3 3 Γ-(v) Γ+(v) 9 5 v 6 12 ∑ f(w, v ) = 2 + 3 + 9 + 6 = 20 − w ∈ Γ ( v ) ∑ f(v, w ) = 3 + 5 + 12 = 20 + w ∈ Γ ( v ) Div f (v ) = 20 − 20 = 0 Chương 8 – Luồng trong mang 6
7. I. Bài toán luồng cực đại ™ Luồng trong mạng 2 3 Γ-(t) 3 5 Γ+(s) t s 9 12 6 ∑ f ( w , t ) = 2 + 3 + 9 + 6 = 20 − w ∈ Γ ( t ) ∑ f ( s, w ) = 3 + 5 + 12 = 20 + w ∈ Γ ( s ) val ( f ) = 20 Chương 8 – Luồng trong mang 7
8. I. Bài toán luồng cực đại Các số màu xanh: Khả năng thông qua trên mỗi cung Các số màu đỏ: Luồng trên mỗi cung Giá trị của luồng: val(f) = 5 4, 2 s : Điểm phát 2, 2 3, 3 9, 0 8, 1 t : Điểm thu stNếu không có 1, 1 3, 3 5, 1 10, 1 cung (v, w) thì c(v, w) = 0 10, 2 20, 1 Chương 8 – Luồng trong mang 8
9. I. Bài toán luồng cực đại ™ Bài toán luồng cực đại ƒ Cho mạng G= (V, E), hãy tìm luồng f trong mạng sao cho giá trị luồng là lớn nhất. ƒ Luồng f như vậy gọi là luồng cực đại ™ Ứng dụng: ƒ Bài toán lập bản đồ giao thông trong thành phố. ƒ Bài toán đám cưới vùng quê. Chương 8 – Luồng trong mang 9
10. Nội dung I. Bài toán luồng cực đại II. Định lý Ford-Fulkerson III. Thuật toán tìm luồng cực đại trong mạng Chương 8 – Luồng trong mang 10 Lý thuyết đồ thị
11. II.1. Lát cắt ƒ Cho mạng G = (V, E). Lát cắt (X, X*) là một phân hoạch tập đỉnh V của mạng thành hai tập X và X* với điểm phát s ∈ X và điểm thu t ∈ X*. ƒ Khả năng thông qua của lát cắt (X, X*) là tổng tất cả các khả năng thông qua của các cung (v, w) có v ∈ X và w ∈ X*. ƒ Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất. Chương 8 – Luồng trong mang 11
12. II.1. Lát cắt ™Lát cắt Khả năng thông qua của lát cắt (X, X*) là: 3 + 8 + 10 = 21. Chương 8 – Luồng trong mang 12
13. II.2. Luồng và lát cắt ™Định lý 1 Giá trị của mọi luồng f trong mạng không lớn hơn khả năng thông qua của lát cắt bất kỳ (X, X*). val(f) ≤ c (X, X*) Khả năng thông qua là 21. Giá trị của luống f: val(f)=5<21. Chương 8 – Luồng trong mang 13
14. II.2. Luồng và lát cắt ™Định lý 1 ™Chứng minh ƒ Với mọi v V, ta cộng các điều kiện cân bằng luồng: ∑∑( f (w, v) − ∑ f (v, w)) = div(s) = - val(f). v∈ X w∈Γ − (v ) w∈Γ + (v ) ƒ Tổng này gồm các số hạng dạng f(u,v) với dấu + và dấu – mà có ít nhất u hoặc v ∈X. Nếu cả u và v đều ∈ X thì f(u,v) sẽ xuất hiện với dấu + trong Div(v) và dấu - trong Div(u) nên chúng triệt tiêu lẫn nhau. Ta thu được: − ∑ f (v , w ) + ∑ f (v , w ) = − val ( f ) v∈ X , w∈ X * v∈ X *, w∈ X ⇔ val ( f ) = ∑ f (v, w) − ∑ f (v, w) ≤ ∑ c(v, w) v∈ X ,w∈ X * v∈ X *, w∈ X v∈ X ,w∈ X * ⇔ val ( f ) ≤ c ( X , X *) (ĐPCM). Chương 8 – Luồng trong mang 14
15. II.2. Luồng và lát cắt ™Hệ quả Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng. ™Định lý Ford-Fulkerson Giá trị luồng cực đại trên mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất. Chương 8 – Luồng trong mang 15
16. II.3. Đồ thị tăng luồng, đường tăng luồng ™ Giả sử f là một luồng trong mạng G = (V, E). Từ mạng G ta xây dựng đồ thị có trọng số Gf=(V, Ef) như sau: ƒ Xét các cạnh e = (v, w) E: • Nếu f(v, w) = 0 : thêm một cung (v, w) có trọng số là c(v, w) vào Gf . • Nếu f(v, w) = c(v, w) : thêm một cung (w, v) có trọng số c(v, w) vào Gf. • Nếu 0 < f(v, w) < c(v, w) : thêm một cung (v, w) có trọng số c(v, w)– f(v,w), và một cung (w, v) có trọng số f(v, w) vào Gf . ƒ Các cung của đồ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ị được gọi là đồ thị tăng luồng. Chương 8 – Luồng trong mang 16
17. II.3. Đồ thị tăng luồng, đường tăng luồng Mạng G=(V, E) Đồ thị tăng luồng Gf=(V, Ef) Chương 8 – Luồng trong mang 17
18. II.3. Đồ thị tăng luồng, đường tăng luồng ™ Giả sử P = (s, , t) là một đường đi từ s đến t trên đồ thị tăng luồng . Gọi d là trọng số nhỏ nhất trong các trọng số của các cung trên đường đi P. Từ luồng f, xây dựng luồng f’ trên mạng G như sau: ƒ Nếu (v, w) P là cung thuận thì f’(v, w) = f(v, w) + d. ƒ Nếu (v, w) P là cung nghịch thì f’(v, w) = f(v, w) – d. ƒ Nếu (v, w) P thì f’(v, w) = f( v, w). ™ Khi đó ta được luồng f’ là luồng trong mạng G và giá trị của luồng f’ tăng thêm d so với giá trị của luồng f. Đường đi P được gọi là đường tăng luồng. Chương 8 – Luồng trong mang 18
19. II.3. Đồ thị tăng luồng, đường tăng luồng Chương 8 – Luồng trong mang 19
20. II.3. Đồ thị tăng luồng, đường tăng luồng ™ Định lý 2 ƒ Cho mạng G=(V, E) và f là một luồng trong mạng G. Các mệnh đề sau 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 (X, X*) là một lát cắt nào đócủa mạng. Chứng minh? Chương 8 – Luồng trong mang 20
21. Nội dung I. Bài toán luồng cực đại II. Định lý Ford-Fulkerson III. Thuật toán tìm luồng cực đại trong mạng Chương 8 – Luồng trong mang 21 Lý thuyết đồ thị
22. III. Thuật toán tìm luồng cực đại trong mạng ™Qui trình thuật toán Ford-Fulkerson ƒ Đặt luồng ban đầu bằng 0 (luồng không). Vì một mạng bất kỳ đều có ít nhất một luồng là luồng không. ƒ Lặp lại hai quá trình tìm đường tăng luồng và tăng luồng cho mạng theo đường tăng luồng đó. Vòng lặp kết thúc khi không tìm được đường tăng luồng nữa. ƒ Khi đã có luồng cực đại, xây dựng lát cắt hẹp nhất của mạng. Chương 8 – Luồng trong mang 22
23. III. Thuật toán tìm luồng cực đại trong mạng ™Thuật toán tìm đường tăng luồng ƒ Đầu tiên, gán nhãn cho s và đặt nó là chưa xét. Tiếp tục ta gán nhãn cho các đỉnh kề của s và s trở thành đỉnh đã xét. Làm tương tự cho các đỉnh kề với s đã được gán nhãn. Thuật toán dừng lại nếu: 1. Đỉnh t được gán nhãn. Khi đóta tìm được đường tăng luồng. 2. Hoặc t chưa có nhãn mà tất cả các đỉnh có nhãn khác đã được xét. Khi đóluồng đang xét là cực đại, không tìm được đường tăng luồng. Chương 8 – Luồng trong mang 23
24. III. Thuật toán tìm luồng cực đại trong mạng Bước 1: Đặt f(e)=0, với mọi cạnh e ∈ E Bước 2: Gán nhãn cho s: p[s]=[-, ε(s)]; ε(s)=∞; Đặt u= s; Bước 3: a) Với mọi v∈Ke+(u), Nếu v chưa có nhãn và s(u,v)=c(u,v)f(u,v)>0 thì: Đặt ε(v) = min(ε(u), s(u,v)); Gán nhãn p[v] = [ +u, ε(v)] ; Với mọi v ∈ Ke-(u), Nếu v chưa có nhãn và f(u,v)>0 thì: Đặt ε(v) = min (ε(u), f(u,v)); Gán nhãn p[v] = [ -u, ε(v)] ; Bước 4: Nếu t đã có nhãn (v == t) Đến Bước 5. Ngược lại : Nếu Mọi đỉnh có nhãn đã xét: Đến Bước 6. Ngược lại: đặt u=v, Đến Bước 3. Cuối nếu. Cuối nếu. Bước 5: Dùng p[t] để tìm đường tăng luồng P bằng cách đi ngược từ t đến s. Đặt f = f + ε(t) ∀ cạnh e ∈ P. Đến Bước 2. Bước 6: X = {Các đỉnh có nhãn đã xét }, X* = V \ X . Lát cắt (X,X*) là cực tiểu. Chương 8 – Luồng trong mang 24
25. III. Thuật toán tìm luồng cực đại trong mạng ™Ví dụ + Gán nhãn: s [-,∞]. + Xét s: cung (s,a) s(s,a) = 3 > 0: ε(a) = min(∞,3) = 3, p[a]= [+s,3]. Đỉnh b: Chưa được gán nhãn. + Xét a: p[c]= [+a,2] + Xét c: cung (b,c) f(b,c) = 5 > 0, ε(c) = min(2,5) = 2 p[b]= [-c,2] + Xét b: p[d]= [+b,2]. + Xét d: p[t]= [+d,2]. Ta có đường tăng luồng: t → d → b → c → a → s Luồng f’ := f + 2 = 7 + 2 = 9. Chương 8 – Luồng trong mang 25