Bài giảng Toán rời rạc - Bài 11: Bài toán luồng cực đại trên mạng - Nguyễn Văn Hiệu

Nội dung text: Bài giảng Toán rời rạc - Bài 11: Bài toán luồng cực đại trên mạng - Nguyễn Văn Hiệu

1. BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
2. Nội dung • Các khái niệm • Bài toán luồng cực đại • Thuật toán Ford –Fulkerson • Minh họa ví dụ Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
3. Các khái niệm Mạng Ví dụ . Mạng là một đồ thị có . Đồ thị có đỉnh phát s và đỉnh thu t hướng, có trong số G = (V, 6 2 4 E): 5 3 6 1. ∃ ! đỉnh s: deg-(s) = 0, s - đỉnh phát. s t 3 + 6 2. ∃ ! đỉnh t: deg (t) = 0, 5 t - đỉnh thu. 1 3 5 3. ∀ (i,j) ∈ E: cij >0, . Khả năng thông qua: c =5 , cij - khả năng thông qua s3 của cung (i,j). 4. Đồ thị liên thông yếu 3
4. Các khái niệm Luồng Ví dụ . Cho mạng G và khả năng . Tập luồng f ij được miêu tả trong ngoặc màu xanh thông qua cij ∀ 푖, 푗 ∈ , 푠 đỉ푛ℎ ℎá푡, 푡 đỉ푛ℎ 푡ℎ . 6 (1) 2 4 . Luồng vận tải trên mạng G 5 (3) 3 (3) 6 (4) là hàm f: E R+ : 1. f ≥0, ∀ (푖, 푗) ∈ s t ij 3 (2) f ij :- luồng trên cung (i,j). 6 (3) 5 (4) 1 (1) 2. 0 f ij c ij , ∀ 푖, 푗 ∈ . 3 5 3. ∀푣 ∶ v ≠ s, v ≠ t: 푖,푣 ∈ f iv = 푣,푗 ∈ f vj 4
5. Các khái niệm Định lý Giá trị của luồng . Cho {f ij } tập luồng trên . Cho luồng f trên G giá trị mạng G và s đỉnh phát và t là của luồng được định nghĩa đỉnh thu: là đại lượng: 풔풊 ∈푬 f si = 풊,풕 ∈푬 f it Val (f) = 풔풊 ∈푬 f si = f it . Nếu (i,j) ∉ , 푡ℎì f ij = 0 풊,풕 ∈푬 f ij = f ji 푗∈ 푖∈ 푗∈ 푖∈ 5
6. Các khái niệm • Xác định giá trị của luồng f 6(5) 2 4 5(5) 6(6) • Val(f) = ? 3(1) 3(0) s t 6(1) 5(2) 1(1) 3 5 6
7. Bài toán luồng cực đại Bài toán Ứng dụng . Cho mạng G với đỉnh phát . Xác định cường độ lớn nhất s, đỉnh thu là t, và khả năng của dòng vận tải giữa hai nút của một bản đồ giao thông. Bài thông qua là cij ,∀ 푖, 푗 ∈ . toán luồng cực đại chỉ ra đoạn . Trong số các luồng trên đường đông xe nhất. mạng G tìm luồng có . Hệ thống đường ống dẫn dầu: giá trị lớn nhất ống – cung, s - tàu chở dầu, t - bể chứa, còn những điểm nối giữa các ống là các đỉnh của đồ thị. cij - diện tích ống. Cần phải tìm luồng lớn nhất để bơm từ tàu chở dầu vào bể chứa. 7
8. Bài toán luồng cực đại Bài toán Ý tưởng . Cho mạng G với đỉnh phát . Xuất phát từ một luồng nào s, đỉnh thu là t, và khả năng đó, ta tìm đường đi (không thông qua là cij ,∀ 푖, 푗 ∈ . định hướng) từ s đến t, . Trong số các luồng trên . Tiến hành hiệu chỉnh giá trị mạng G tìm luồng có luồng trên đường đi sao cho giá trị lớn nhất luồng mới có gia trị lớn hớn. . Nếu không tìm được đi như vậy thì luồng đó là cực đại. 8
9. Bài toán luồng cực đại Bài toán Ý tưởng . Cho mạng G với đỉnh phát . Giả sử s, đỉnh thu là t, và khả năng P = (s, a, .,i, j , .,z, t) thông qua là c ,∀ 푖, 푗 ∈ . 푖, 푗 ∈ ij (i,j) = . Trong số các luồng trên (푗, 푖) ∈ . Nếu (i,j) là cung trên P thì cung mạng G tìm luồng có đó cùng hướng với P. Ký hiệu giá trị lớn nhất P+ là tập cung cùng hướng với P . Nếu (j,i) là cung trên P, thì cung đó ngược hướng với P. P- là tập cung ngược hướng với P 9
10. Bài toán luồng cực đại Cơ sở lý luận Cơ sở lý luận . Cho f là luồng trên mạng G . Xây dựng luồng f* như sau: . Giả sử đường đi không định hướng từ s đến t: f ∀ 푖, 푗 ∉ 푃 ij P = (s =a,b, ,i,j, ,z = t) . f* = f ij + 훿∀ 푖, 푗 ∈ P+ . ∀ 푖, 푗 ∈ P+ : f ij 0 푖, 푗 ∈ P+ và các giá trị f ij vớ푖 푖, 푗 ∈ P- Val(f*) = val(f) + 휹 10
11. Bài toán luồng cực đại Tính đúng đắn Thuật toán Ford- Fullkerson . f* là luồng . Tìm luồng cực đại . (s,b) ∈ P . Input: Mạng G với đỉnh + phát s đỉnh thu t, khả năng f* = f + 훿 sb sb thông qua C = (c ij), (i,j) ∈ E . Val (f*) = 풔풊 ∈푬 f∗ si . Ký hiệu s = v0, ,vn = t = val(f) + 훿 . Output: F = (f ), (i,j) ∈ E ij 11
12. Thuật toán Ford-Fullkerson Thuật toán . Tìm luồng cực đại . Bước 1(khởi tạo luồng ban đầu) . Input: . Mạng G với đỉnh phát s đỉnh f = 0, ∀ 푖, 푗 ∈ thu t, khả năng thông qua C = ịj (c ij), (i,j) ∈ E . Ký hiệu s = v0, ,vn = t . Bước 2 (gán nhãn cho đỉnh phát) . Output: s( , ∞) . F = (f ij), (i,j) ∈ E 12
13. Thuật toán Ford-Fullkerson Thuật toán Thuật toán . Bước 1( khởi tạo luồng ban đầu) . Bước 3 (kiểm tra nhãn của đỉnh thu ) . Nếu t có nhãn > bước 6 . Nếu t chưa có nhãn >bước 4 f = 0, ∀ 푖, 푗 ∈ ịj . Bước 4( xác đỉnh đỉnh đánh dấu) . Bước 2( gán nhãn cho đỉnh phát) . Xét các đỉnh mang nhãn mà chưa đánh dấu, chọn v: = vi, i chỉ số bé nhất. s( , ∞) . Nếu ∃ vi, thì Đánh dấu v. . Nếu ∄ vi, thì Kết thúc và F là luồng cực đại. 13
14. Thuật toán Ford-Fullkerson Thuật toán Thuật toán . Bước 5( gán nhãn cho các đỉnh chưa  Cung dạng (W,v): có nhãn, kề với v ) . Nếu fWv > 0 , gán nhãn w (v, x) với . Giả sử nhãn của v (훼, Δ) x = min {Δ, f } . Xét cung dạng (v,W) và (W,v) Wv . Nếu fWv = 0, không gán (theo thứ tự (v,v0 ) (v0 ,v), (v,v1 ) nhãn cho w (v ,v), ) 1 . Quay lai bước 3  Cung dạng (v,W): . Lưu ý: chỉ xét các W chưa được . Nếu fvW < CvW , gán nhãn w gán nhãn (v, x) với x = min {Δ, CvW - fvW } . Nếu fvW = CvW , không gán nhãn cho w 14
15. Thuật toán Ford-Fullkerson Thuật toán Thuật toán . Bước 6 ( hiệu chỉnh luồng ) . Nhận được đường đi P từ s . Giả sử (휷, 휹) là nhãn của t đến t. (đỉnh thu). (s =Wk ,Wk-1 , ,W1,W0 =t ) . Đặt W0 = t, W1 = 휷 . Nếu nhãn của wi là (휷`, 휹`) . Điều chỉnh f trên P: . Đặt W = 휷` i+1 f ∀ 푖, 푗 ∉ 푃 ij f = f ij + 훿 , ∀ 푖, 푗 ∈ P+ . (tiếp tục) f ij − 훿 , ∀ 푖, 푗 ∈ P− . Đặt W = s (đỉnh phát) k . Xóa tất cả các nhãn trên P và quay lại bước 2 15
16. Vi dụ • Tìm luồng cực đại trên mạng G 2 a b 3 4 2 s t 5 4 c d 2 • Thứ tự các đỉnh: s a b c d t
17. Vi dụ . Bước 1(khởi tạo luồng ban đầu) 2 (0) . f = 0, ∀ 푖, 푗 ∈ a b ịj 3 (0) 4 (0) 2(0) . val (f) = 0 s t 4(0) 5 (0) c d 2 (0)
18. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) 2 (0) a b s( , ∞) 3 (0) 4 (0) ( , ∞) 2(0) s t 4(0) 5 (0) c d 2 (0)
19. Vi dụ . Bước 3 (kiểm tra nhãn của đỉnh thu ) 2 (0) . t chưa có nhãn >bước 4 a b 3 (0) 4 (0) ( , ∞) 2(0) s t 4(0) 5 (0) c d 2 (0)
20. Vi dụ . Bước 4( xác đỉnh đỉnh đánh dấu) . Xét các đỉnh mang 2 (0) a b nhãn và chưa đánh 3 (0) 4 (0) dấu, ( , ∞) 2(0) . chọn v: = s. s t . Đánh dấu s (sử dụng màu 4(0) để đánh dấu) 5 (0) c d 2 (0)
21. Vi dụ . Bước 5( gán nhãn cho các đỉnh chưa (s , ) có nhãn, kề với v ) 2 (0) a b . Cung kề với s 3 (0) 4 (0) . Cung (s,a): ( , ∞) 2(0) . fsa = 0< Csa = 3, gán s t nhãn a (s, 3) với 4(0) x = min {∞, 3 - 0} 5 (0) c d . Cung (s,c): 2 (0) . gán nhãn c (s, 5) với (s , ) . Chuyên sang bước 3
22. Vi dụ . Bước 3 (kiểm tra nhãn của đỉnh thu ) (s , ) 2 (0) . t chưa có nhãn >bước 4 a b 3 (0) 4 (0) ( , ∞) 2(0) s t 4(0) 5 (0) c d 2 (0) (s , )
23. Vi dụ . Bước 4( xác đỉnh đỉnh đánh dấu) . Xét các đỉnh mang 2 (0) a b nhãn và chưa đánh 3 (0) 4 (0) dấu, ( , ∞) 2(0) . chọn v: = a. s t . Đánh dấu a (sử dụng màu 4(0) để đánh dấu) 5 (0) c d 2 (0)
24. Vi dụ . Bước 5( gán nhãn cho các đỉnh chưa ( s, ) ( a, ) có nhãn, kề với v ) 2 (0) a b . Cung kề với a 3 (0) 4 (0) . Cung (a,b): ( , ∞) 2(0) . fab = 0< Cab = 2, gán s t nhãn b (s, 2) 4(0) x = min{3, 2-0} =2 5 (0) c d 2 (0) . Chuyển sang bước 3 ( s, )
25. Vi dụ . Bước 3 (kiểm tra nhãn của đỉnh thu ) ( s, ) ( a, ) 2 (0) . t chưa có nhãn >bước 4 a b 3 (0) 4 (0) ( , ∞) 2(0) s t 4(0) 5 (0) c d 2 (0) ( s, )
26. Vi dụ . Bước 4( xác đỉnh đỉnh đánh dấu) ( s, ) ( a, ) . Xét các đỉnh mang 2 (0) a b nhãn và chưa đánh 3 (0) 4 (0) dấu, ( , ∞) 2(0) . chọn v: = b. s t . Đánh dấu b (sử dụng màu 4(0) để đánh dấu) 5 (0) c d 2 (0) ( s, )
27. Vi dụ . Bước 5( gán nhãn cho các đỉnh chưa ( s, ) ( a, ) có nhãn, kề với v ) 2 (0) a b . Cung kề với v 3 (0) 4 (0) . Cung (b, t): ( , ∞) 2(0) ( b, ) . fbt = 0< Cbt = 4, gán nhãn s t t(b, 2) 4(0) x = min{2, 4-0} =2 5 (0) c d 2 (0) . Chuyển sang bước 3 ( s, )
28. Vi dụ . Bước 3 (kiểm tra nhãn của đỉnh thu ) ( s, ) ( a, ) 2 (0) . t >bước 6 a b 3 (0) 4 (0) ( , ∞) 2(0) ( b, ) s t 4(0) 5 (0) c d 2 (0) ( s, )
29. Vi dụ . Bước 6 ( hiệu chỉnh luồng ) . W0 = t, W1 = b 2 (2) . W = a, W = s a b 2 2 3 (2) 4 (2) . Đường đi P từ s đến t. ( b, ) (s, a, b, t) 2(0) s t . Điều chỉnh f trên P: 4(0) f ∀ 푖, 푗 ∉ 푃 5 (0) ij c d f = f ij + 2 , ∀ 푖, 푗 ∈ P+ 2 (0) ( s, ) f ij − 2 , ∀ 푖, 푗 ∈ P− . Val(f) = 2 . Xóa tất cả các nhãn trên P và quay lại bước 2
30. Vi dụ Val(f) = 2 Quay lại bước 2 2 (2) a b 3 (2) 4 (2) 2(0) s t 4(0) 5 (0) c d 2 (0)
31. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) . Tiếp tục lặp quá trình thu được nhãn: s( , ∞) ( s, 1) ( c, ) 2 (2) 2 (2) a b a b 3 (2) 4 (2) 3 (2) 4 (2) ( , ∞) 2(0) ( , ∞) 2(0) ( b, ) s t s t 4(0) 4(0) 5 (0) 5 (0) c d c d 2 (0) 2 (0) ( s, ) ( c, )
32. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) . P = (s, c, b, t) , 훿 = 2 s( , ∞) ( s, 1) ( c, ) 2 (2) 2 (2) a b a b 3 (2) 4 (2) 3 (2) 4 (4) ( , ∞) 2(0) ( , ∞) 2(2) ( b, ) s t s t 4(0) 4(0) 5 (0) 5 (2) c d c d 2 (0) 2 (0) ( s, ) ( c, )
33. Vi dụ Val (f) = 4 Quay lại bước 2 2 (2) a b 3 (2) 4 (4) 2(2) s t 4(0) 5 (2) c d 2 (0)
34. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) . Tiếp tục lặp quá trình thu được nhãn: s( , ∞) ( s, 1) 2 (2) 2 (2) a b a b 3 (2) 4 (4) 3 (2) 4 (4) ( , ∞) 2(2) ( ,∞) 2(2) ( d, ) s t s t 4(0) 4(0) 5 (2) 5 (2) c d c d 2 (0) 2 (0) ( s, ) ( c, )
35. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) . P = (s, c, d, t) , 훿 = 2 s( , ∞) ( s, 1) 2 (2) 2 (2) a b a b 3 (2) 4 (4) 3 (2) 4 (4) ( , ∞) 2(2) ( ,∞) 2(2) ( d, ) s t s t 4(0) 4(2) 5 (2) 5 (4) c d c d 2 (0) 2 (2) ( s, ) ( c, )
36. Vi dụ Val (f) = 6 Quay lại bước 2 2 (2) a b 3 (2) 4 (4) 2(2) s t 4(2) 5 (4) c d 2 (2)
37. Vi dụ . Bước 2 (gán nhãn cho đỉnh phát) . Không tồn tại đỉnh mang nhã mà chưa đánh dấu – KẾT THÚC s( , ∞) ( s, 1) 2 (2) 2 (2) a b a b 3 (2) 4 (2) 3 (2) 4 (4) ( , ∞) 2(2) ( , ∞) 2(2) s t s t 4(2) 4(2) 5 (4) 5 (2) c d c d 2 (2) 2 (2) ( s, )
38. Bài tập
39. THAT’S ALL; THANK YOU What NEXT?