Bài giảng Toán rời rạc: Các ứng dụng của bài toán luồng cực đại - Nguyễn Đức Nghĩa

Bài giảng "Toán rời rạc: Các ứng dụng của bài toán luồng cực đại" trình bày một số bài toán luồng tổng quát luồng cực đại (bài toán với nhiều điểm phát và điểm thu, bài toán với hạn chế thông qua ở nút), ứng dụng trong tổ hợp (bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng). Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Các ứng dụng của bài toán luồng cực đại - Nguyễn Đức Nghĩa Các ứng dụng củaBài toán luồng cực đạiBM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • NGUYỄN ĐỨC NGHĨA Max Flow Applications sToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA t Bộ môn KHMT 2 NỘI DUNG  Một số bài toán luồng tổng quát – Bài toán với nhiều điểm phát và điểm thu – Bài toán với hạn chế thông qua ở nút  Một số ứng dụng trong tổ hợp – Bài toán cặp ghép cực đại trong đồ thị hai phía – Độ tin cậy của mạngToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 3 Một số bài toán luồng tổng quátToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 4 M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu  XÐt m¹ng G víi p ®iÓm ph¸t s1, s2,..., sp với lượng ph¸t là a1, a2, ..., ap vµ q ®iÓm thu t1, t2,..., tq với lượng thu là b1, b2, ..., bq  Gi¶ sö r»ng luång cã thÓ ®i tõ mét ®iÓm ph¸t bÊt kú ®Õn tÊt c¶ c¸c ®iÓm thu.  T×m luång cùc ®¹i tõ c¸c ®iÓm ph¸t ®Õn c¸c ®iÓm thu s1 t1 s2 t2 sp tqToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 5 M¹ng víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu  Đa vµo mét ®iÓm ph¸t gi¶ s vµ mét ®iÓm thu gi¶ t vµ c¸c c¹nh nèi s víi tÊt c¶ c¸c ®iÓm ph¸t vµ c¸c c¹nh nèi c¸c ®iÓm thu víi t.  Kntq cña cung (s,si) sÏ b»ng ai là lîng ph¸t cña si.  Kntq cña (ti, t) sÏ bằng bi là lîng thu cña ®iÓm thu ti.  Bài to¸n dẫn về bài to¸n với 1 điểm ph¸t và một điểm thu. s1 t1 a1 b1 s2 t2 a2 b2 t s ap bq sp tqToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 6 Bài toán với hạn chế thông qua ở nút  Gi¶ sö trong m¹ng G, ngoµi kh¶ n¨ng th«ng qua cña c¸c cung c(u, v), ë mçi ®Ønh v V cßn cã kh¶ n¨ng th«ng qua cña ®Ønh lµ d(v), vµ ®ßi hái tæng luång ®i vµo ®Ønh v kh«ng ®îc vît qu¸ d(v), tøc lµ  f(w,v)  d(v). wV 5 du u 4 dt ds s 1 t 2 3 v dv • T×m luång cùc ®¹i từ s đến t trong m¹ng G.Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 7 Bài toán với hạn chế thông qua ở nút  X©y dùng mét m¹ng G sao cho: mçi ®Ønh v cña G t¬ng øng víi 2 ®Ønh v+, v- trong G, mçi cung (u, v) trong G øng víi cung (u-, v+) trong G, mçi cung (v,w) trong G øng víi cung (v-, w+) trong G. Ngoµi ra, mçi cung (v+, v-) trong G cã kh¶ n¨ng th«ng qua lµ d(v), tøc lµ b»ng kh¶ n¨ng th«ng qua cña ®Ønh v trong G. du du u+ u- 5 4 5 u 4 dtds ds dt 1 t+ t- s 1 t s+ s- 2 3 ...