intTypePromotion=1
ADSENSE

Bài giảng Toán rời rạc: Bài 11 - TS. Nguyễn Văn Hiệu

Chia sẻ: Le Xuan Manh | Ngày: | Loại File: PDF | Số trang:39

76
lượt xem
6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các khái niệm bài toán luồng cực đại trên mạng, bài toán luồng cực đại, thuật toán Ford–Fulkerson, minh họa ví dụ là những nội dung chính trong bài 11 "Bài toán luồng cực đại trên mạng" thuộc bài giảng Toán rời rạc. Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Toán rời rạc: Bài 11 - TS. 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 4 2 E): 5 6 3 1. ∃ ! đỉnh s: deg-(s) = 0, s - đỉnh phát. s t 3 2. ∃ ! đỉnh t: deg+(t) = 0, 5 6 t - đỉnh thu. 1 3 5 3. ∀ (i,j) ∈ E: cij >0, cij - khả năng thông qua  Khả năng thông qua: c s3 =5 ,… 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 thông qua cij ∀ 𝑖, 𝑗 ∈ ngoặc màu xanh 𝐸, 𝑠 đỉ𝑛ℎ 𝑝ℎá𝑡, 𝑡 đỉ𝑛ℎ 𝑡ℎ𝑢. 6 (1) 4 2  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 ij ≥0, ∀ (𝑖, 𝑗) ∈ 𝐸 s t 3 (2) f ij :- luồng trên cung (i,j). 5 (4) 6 (3) 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  Nếu (i,j) ∉ 𝐸, 𝑡ℎì f ij = 0 = 𝒊,𝒕 ∈𝑬 f it 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 thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸. của một bản đồ giao thông. Bài 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 luồng mới có gia trị lớn giá trị lớn nhất 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à cij ,∀ 𝑖, 𝑗 ∈ 𝐸. 𝑖, 𝑗 ∈ 𝐸 (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 < cij f ij − 𝛿∀ 𝑖, 𝑗 ∈ P−  ∀ 𝑖, 𝑗 ∈ P- : 0 < f ij  Đặt 𝛿:= min {x | x ∈ M }  Giá trị luồng f* sẽ lớn hơn  M tập các giá trị cij - f ij với 𝑖, 𝑗 ∈ P+ và các giá trị f ij vớ𝑖 luồng f một đơn vi 𝛿 > 0 𝑖, 𝑗 ∈ 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*sb = fsb + 𝛿 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 ij), (i,j) ∈ E 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ịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸 thu t, khả năng thông qua C = (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ịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸  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 {Δ, fWv }  Xét cung dạng (v,W) và (W,v)  Nếu fWv = 0, không gán (theo thứ tự (v,v0 ) (v0 ,v), (v,v1 ) nhãn cho w (v1 ,v), … )  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 Wi+1 = 𝜷` f ij ∀ 𝑖, 𝑗 ∉ 𝑃 f = f ij + 𝛿 , ∀ 𝑖, 𝑗 ∈ P+  … (tiếp tục) f ij − 𝛿 , ∀ 𝑖, 𝑗 ∈ P−  Đặt Wk = s (đỉnh phát)  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ịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸 3 (0) a b 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)
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2