Toán học - Bài toán luồng cực đại trên mạng

BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN MẠNG Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1 Giáo viên: TS. Nguyễn Văn Hiệu Email: [email protected] 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 Các khái niệm Mạng  Mạng là một đồ thị có hướng, có trong số G = (V, E): 1. ∃ ! đỉnh s: deg-(s) = 0, s - đỉnh phát. 2. ∃ ! đỉnh t: deg+(t) = 0, t - đỉnh thu. 3. ∀ (i,j) ∈ E: cij >0, cij - khả năng thông qua của cung (i,j). 4. Đồ thị liên thông yếu Ví dụ  Đồ thị có đỉnh phát s và đỉnh thu t  Khả năng thông qua: c s3 =5 , 3 5 5 6 3 1 3 6 6 s 2 4 t 5 3 Các khái niệm Luồng  Cho mạng G và khả năng thông qua cij ∀ 𝑖, 𝑗 ∈ 𝐸, 𝑠 đỉ𝑛ℎ 𝑝ℎá𝑡, 𝑡 đỉ𝑛ℎ 𝑡ℎ𝑢.  Luồng vận tải trên mạng G là hàm f: E  R+ : 1. f ij ≥0, ∀ (𝑖, 𝑗) ∈ 𝐸 f ij :- luồng trên cung (i,j). 2. 0  f ij  c ij , ∀ 𝑖, 𝑗 ∈ 𝐸. 3. ∀𝑣 ∶ v ≠ s, v ≠ t: f iv𝑖,𝑣 ∈𝐸 = f vj𝑣,𝑗 ∈𝐸 Ví dụ  Tập luồng f ij được miêu tả trong ngoặc màu xanh 4 5 (3) 5 (4) 6 (1) 3 (3) 1 (1) 3 (2) 6 (3) 6 (4) s 2 4 t 5 3 Các khái niệm Định lý  Cho {f ij } tập luồng trên mạng G và s đỉnh phát và t là đỉnh thu: f si𝒔𝒊 ∈𝑬 = f it 𝒊,𝒕 ∈𝑬  Nếu (i,j) ∉ 𝐸, 𝑡ℎì f ij = 0 f ij 𝑖∈𝑉𝑗∈𝑉 = f ji 𝑖∈𝑉𝑗∈𝑉 Giá trị của luồng  Cho luồng f trên G giá trị của luồng được định nghĩa là đại lượng: Val (f) = f si𝒔𝒊 ∈𝑬 = f it 𝒊,𝒕 ∈𝑬 5 Các khái niệm • Xác định giá trị của luồng f • 6 5(5) 5(2) 6(5) 3(1) 1(1) 3(0) 6(1) 6(6) 2 4 t 5 3 s Val(f) = ? Bài toán luồng cực đại Bài toán  Cho mạng G với đỉnh phát s, đỉnh thu là t, và khả năng thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸.  Trong số các luồng trên mạng G tìm luồng có giá trị lớn nhất Ứng dụng  Xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao thông. Bài toán luồng cực đại chỉ ra đoạn đường đông xe nhất.  Hệ thống đường ống dẫn dầu: ố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 Bài toán luồng cực đại Bài toán  Cho mạng G với đỉnh phát s, đỉnh thu là t, và khả năng thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸.  Trong số các luồng trên mạng G tìm luồng có giá trị lớn nhất Ý tưởng  Xuất phát từ một luồng nào đó, ta tìm đường đi (không định hướng) từ s đến t,  Tiến hành hiệu chỉnh giá trị luồng trên đường đi sao cho 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 Bài toán luồng cực đại Bài toán  Cho mạng G với đỉnh phát s, đỉnh thu là t, và khả năng thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸.  Trong số các luồng trên mạng G tìm luồng có giá trị lớn nhất Ý tưởng  Giả sử P = (s, a, .,i, j , .,z, t) (i,j) = 𝑖, 𝑗 ∈ 𝐸 (𝑗, 𝑖) ∈ 𝐸  Nếu (i,j) là cung trên P thì cung đó cùng hướng với P. Ký hiệu 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 Bài toán luồng cực đại Cơ sở lý luận  Cho f là luồng trên mạng G  Giả sử đường đi không định hướng từ s đến t: P = (s =a,b,...,i,j,..,z = t)  ∀ 𝑖, 𝑗 ∈ P+ : f ij < cij  ∀ 𝑖, 𝑗 ∈ P- : 0 < f ij  Đặt 𝛿:= min {x | x ∈ M }  M tập các giá trị cij - f ij với 𝑖, 𝑗 ∈ P+ và các giá trị f ij vớ𝑖 𝑖, 𝑗 ∈ P- Cơ sở lý luận  Xây dựng luồng f* như sau:  f* = f ij ∀ 𝑖, 𝑗 ∉ 𝑃 f ij + 𝛿∀ 𝑖, 𝑗 ∈ P+ f ij − 𝛿∀ 𝑖, 𝑗 ∈ P−  Giá trị luồng f* sẽ lớn hơn luồng f một đơn vi 𝛿 > 0 Val(f*) = val(f) + 𝜹 10 Bài toán luồng cực đại Tính đúng đắn  f* là luồng  (s,b) ∈ P+ f*sb = fsb + 𝛿  Val (f*) = f∗ si𝒔𝒊 ∈𝑬 = val(f) + 𝛿 Thuật toán Ford- Fullkerson  Tìm luồng cực đại  Input: Mạng G với đỉnh phát s đỉnh thu t, khả năng thông qua C = (c ij), (i,j) ∈ E  Ký hiệu s = v0, ..,vn = t  Output: F = (f ij), (i,j) ∈ E 11 Thuật toán Ford-Fullkerson  Tìm luồng cực đại  Input:  Mạng G với đỉnh phát s đỉnh thu t, khả năng thông qua C = (c ij), (i,j) ∈ E  Ký hiệu s = v0, ..,vn = t  Output:  F = (f ij), (i,j) ∈ E Thuật toán  Bước 1(khởi tạo luồng ban đầu) fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞) 12 Thuật toán Ford-Fullkerson Thuật toán  Bước 1( khởi tạo luồng ban đầu) fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸  Bước 2( gán nhãn cho đỉnh phát) s( , ∞) Thuật toán  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  Bước 4( xác đỉnh đỉnh đánh dấu)  Xét các đỉnh mang nhãn mà chưa đánh dấu, chọn v: = vi, i chỉ số bé nhất.  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 Thuật toán Ford-Fullkerson Thuật toán  Bước 5( gán nhãn cho các đỉnh chưa có nhãn, kề với v )  Giả sử nhãn của v (𝛼, Δ)  Xét cung dạng (v,W) và (W,v) (theo thứ tự (v,v0 ) (v0 ,v), (v,v1 ) (v1 ,v), )  Cung dạng (v,W):  Nếu fvW < CvW , gán nhãn w (v, x) với x = min {Δ, CvW - fvW }  Nếu fvW = CvW , không gán nhãn cho w Thuật toán  Cung dạng (W,v):  Nếu fWv > 0 , gán nhãn w (v, x) với x = min {Δ, fWv }  Nếu fWv = 0, không gán nhãn cho w  Quay lai bước 3  Lưu ý: chỉ xét các W chưa được gán nhãn 14 Thuật toán Ford-Fullkerson Thuật toán  Bước 6 ( hiệu chỉnh luồng )  Giả sử (𝜷, 𝜹) là nhãn của t (đỉnh thu).  Đặt W0 = t, W1 = 𝜷  Nếu nhãn của wi là (𝜷`, 𝜹`)  Đặt Wi+1 = 𝜷`  (tiếp tục)  Đặt Wk = s (đỉnh phát) Thuật toán  Nhận được đường đi P từ s đến t. (s =Wk ,Wk-1 ,,W1,W0 =t )  Điều chỉnh f trên P: f = f ij ∀ 𝑖, 𝑗 ∉ 𝑃 f ij + 𝛿 , ∀ 𝑖, 𝑗 ∈ P+ f ij − 𝛿 , ∀ 𝑖, 𝑗 ∈ P−  Xóa tất cả các nhãn trên P và quay lại bước 2 15 Vi dụ • Tìm luồng cực đại trên mạng G • Thứ tự các đỉnh: s a b c d t 3 5 2 2 2 4 4 s c d t b a Vi dụ  Bước 1(khởi tạo luồng ban đầu)  fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸  val (f) = 0 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞) 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) Vi dụ  Bước 3 (kiểm tra nhãn của đỉnh thu )  t chưa có nhãn--->bước 4 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) Vi dụ  Bước 4( xác đỉnh đỉnh đánh dấu)  Xét các đỉnh mang nhãn và chưa đánh dấu,  chọn v: = s.  Đánh dấu s (sử dụng màu để đánh dấu) 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) Vi dụ  Bước 5( gán nhãn cho các đỉnh chưa có nhãn, kề với v )  Cung kề với s  Cung (s,a):  fsa = 0< Csa = 3, gán nhãn a (s, 3) với x = min {∞, 3 - 0}  Cung (s,c):  gán nhãn c (s, 5) với  Chuyên sang bước 3 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) (s , 𝟑) (s , 𝟓) Vi dụ  Bước 3 (kiểm tra nhãn của đỉnh thu )  t chưa có nhãn--->bước 4 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) (s , 𝟑) (s , 𝟓) Vi dụ  Bước 4( xác đỉnh đỉnh đánh dấu)  Xét các đỉnh mang nhãn và chưa đánh dấu,  chọn v: = a.  Đánh dấu a (sử dụng màu để đánh dấu) 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) Vi dụ  Bước 5( gán nhãn cho các đỉnh chưa có nhãn, kề với v )  Cung kề với a  Cung (a,b):  fab = 0< Cab = 2, gán nhãn b (s, 2) x = min{3, 2-0} =2  Chuyển sang bước 3 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) ( s, 𝟑) ( s, 𝟓) ( a, 𝟐) Vi dụ  Bước 3 (kiểm tra nhãn của đỉnh thu )  t chưa có nhãn--->bước 4 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) ( s, 𝟑) ( s, 𝟓) ( a, 𝟐) Vi dụ  Bước 4( xác đỉnh đỉnh đánh dấu)  Xét các đỉnh mang nhãn và chưa đánh dấu,  chọn v: = b.  Đánh dấu b (sử dụng màu để đánh dấu) 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) ( s, 𝟑) ( s, 𝟓) ( a, 𝟐) Vi dụ  Bước 5( gán nhãn cho các đỉnh chưa có nhãn, kề với v )  Cung kề với v  Cung (b, t):  fbt = 0< Cbt = 4, gán nhãn t(b, 2) x = min{2, 4-0} =2  Chuyển sang bước 3 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) ( s, 𝟑) ( s, 𝟓) ( a, 𝟐) ( b, 𝟐) Vi dụ  Bước 3 (kiểm tra nhãn của đỉnh thu )  t --->bước 6 3 (0) 5 (0) 2 (0) 2(0) 2 (0) 4(0) 4 (0) s c d t b a ( , ∞) ( s, 𝟑) ( s, 𝟓) ( a, 𝟐) ( b, 𝟐) Vi dụ  Bước 6 ( hiệu chỉnh luồng )  W0 = t, W1 = b  W2 = a, W2 = s  Đường đi P từ s đến t. (s, a, b, t)  Điều chỉnh f trên P: f = f ij ∀ 𝑖, 𝑗 ∉ 𝑃 f ij + 2 , ∀ 𝑖, 𝑗 ∈ P+ 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 3 (2) 5 (0) 2 (2) 2(0) 2 (0) 4(0) 4 (2) s c d t b a ( s, 𝟓) ( b, 𝟐) Vi dụ 3 (2) 5 (0) 2 (2) 2(0) 2 (0) 4(0) 4 (2) s c d t b a Val(f) = 2 Quay lại bước 2 Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞)  Tiếp tục lặp quá trình thu được nhãn: 3 (2) 5 (0) 2 (2) 2(0) 2 (0) 4(0) 4 (2) s c d t b a ( , ∞) 3 (2) 5 (0) 2 (2) 2(0) 2 (0) 4(0) 4 (2) s c d t b a ( , ∞) ( s, 1) ( s, 𝟓) ( c, 𝟐) ( b, 𝟐) ( c, 𝟐) Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞)  P = (s, c, b, t) , 𝛿 = 2 3 (2) 5 (0) 2 (2) 2(0) 2 (0) 4(0) 4 (2) s c d t b a ( , ∞) 3 (2) 5 (2) 2 (2) 2(2) 2 (0) 4(0) 4 (4) s c d t b a ( , ∞) ( s, 1) ( s, 𝟓) ( c, 𝟐) ( b, 𝟐) ( c, 𝟐) Vi dụ Val (f) = 4 Quay lại bước 2 3 (2) 5 (2) 2 (2) 2(2) 2 (0) 4(0) 4 (4) s c d t b a Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞)  Tiếp tục lặp quá trình thu được nhãn: 3 (2) 5 (2) 2 (2) 2(2) 2 (0) 4(0) 4 (4) s c d t b a ( , ∞) 3 (2) 5 (2) 2 (2) 2(2) 2 (0) 4(0) 4 (4) s c d t b a ( ,∞) ( s, 1) ( s, 𝟑) ( d, 𝟐) ( c, 𝟐) Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞)  P = (s, c, d, t) , 𝛿 = 2 3 (2) 5 (2) 2 (2) 2(2) 2 (0) 4(0) 4 (4) s c d t b a ( , ∞) 3 (2) 5 (4) 2 (2) 2(2) 2 (2) 4(2) 4 (4) s c d t b a ( ,∞) ( s, 1) ( s, 𝟑) ( d, 𝟐) ( c, 𝟐) Vi dụ Val (f) = 6 Quay lại bước 2 3 (2) 5 (4) 2 (2) 2(2) 2 (2) 4(2) 4 (4) s c d t b a Vi dụ  Bước 2 (gán nhãn cho đỉnh phát) s( , ∞)  Không tồn tại đỉnh mang nhã mà chưa đánh dấu – KẾT THÚC 3 (2) 5 (4) 2 (2) 2(2) 2 (2) 4(2) 4 (2) s c d t b a ( , ∞) 3 (2) 5 (2) 2 (2) 2(2) 2 (2) 4(2) 4 (4) s c d t b a ( , ∞) ( s, 1) ( s, 𝟑) Bài tập THAT’S ALL; THANK YOU What NEXT?