TAILIEUCHUNG - 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ề .
đang nạp các trang xem trước
