tailieunhanh - Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 (tt) - Nguyễn Đức Nghĩa

Chương này trình bày một số ứng dụng của bài toán luồng cực đại như: 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, bài toán cặp ghép cực đại trong đồ thị hai phía, độ tin cậy của mạng. . | Các ứng dụng của Bài toán luồng cực đại Copyright 2000, Kevin Wayne Max Flow Applications s t Copyright 2000, Kevin Wayne 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ạng Copyright 2000, Kevin Wayne Một số bài toán luồng tổng quát Copyright 2000, Kevin Wayne 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 s2 sp t1 t2 tq Copyright 2000, Kevin Wayne 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 s2 sp t1 t2 tq s t b2 bq b1 a1 a2 ap Copyright 2000, Kevin Wayne 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µ w V f(w,v) d(v). T×m luång cùc ®¹i từ s đến t trong m¹ng G. s v t u ds du dt dv 5 4 1 2 3 Copyright 2000, Kevin Wayne 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. s v t u ds du dt dv 5 4 1 2 3 s- v+ t+ u+ ds du dt dv 5 4 1 2 3 s+ t- u- v- Qui về . | Các ứng dụng của Bài toán luồng cực đại Copyright 2000, Kevin Wayne Max Flow Applications s t Copyright 2000, Kevin Wayne 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ạng Copyright 2000, Kevin Wayne Một số bài toán luồng tổng quát Copyright 2000, Kevin Wayne 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 s2 sp t1 t2 tq Copyright 2000, Kevin Wayne 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à .