Tiểu luận Thiết kế và phân tích thuật toán luồng cực đại

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC TIỂU LUẬN THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN Đề tài: LUỒNG CỰC ĐẠI Giáo viên hướng dẫn : TS. Hoàng Quang Học viên thực hiện: Nguyễn Văn Sửu (Nhóm trưởng) Nguyễn Đề Nguyễn Thị Thu Nguyễn Đức Nghĩa Nguyễn Đức Quê Lớp : Khoa học máy tính B 2010-2012 Huế, 2011 Mục lục Phân công thực hiện tiểu luận: Nguyễn Văn Sửu: phần 26.1 Nguyễn Đề: phần 26.2 Nguyễn Đức Nghĩa: phần 26.3 Nguyễn Đức Quê: phần 26.4 Nguyễn Thị Thu: phần 26.5  26. Luồng Cực Đại Giống như trường hợp lập mô hình một bản đồ đường xá dưới dạng một đồ thị có hướng để tìm ra lộ trình ngắn nhất từ điểm này đến điểm kia, ta cũng có thể diễn dịch một đồ thị có hướng dưới dạng một "mạng luồng" và dùng nó để giải đáp các câu hỏi về các luồng vật chất [material flows]. Hãy tưởng tượng một luồng di chuyển vật chất qua một hệ thống từ nguồn, ở đó vật chất được tạo, đến một bồn [sink], ở đó nó được tiêu thụ. Nguồn tạo ra vật chất theo một tốc độ đều đặn, và bồn tiêu thụ vật chất theo cùng tốc độ. "Luồng di chuyển" (flow) của vật chất tại một điểm bất kỳ trong hệ thống theo trực giác là tốc độ và vật chất di chuyển. Có thể dùng các mạng luồng để lập mô hình các chất lỏng chảy qua các ống dẫn, các linh kiện qua các dây chuyền lắp ráp, dòng điện qua các mạng lưới điện, thông tin qua các mạng truyền thông, và …. Mỗi cạnh có hướng trong một hạng luồng có thể được xem như một ống dẫn cho vật chất. Mỗi ống dẫn có một dung lượng đã định, được nêu dưới dạng tốc độ cực đại qua đó vật chất có thể lưu chuyển qua ống dẫn, như 200 gallon chất lỏng mỗi giờ qua một ống dẫn hoặc 20 ampere dòng điện qua một dây dẫn. Các đỉnh là các khớp nối của ống dẫn, và khác với nguồn và bồn, vật chất chảy qua các đỉnh mà không ứ đọng lại trong chúng. Nói cách khác, tốc độ mà vật chất này là "sự bảo toàn luồng lưu", và nó giống như Luật Dòng Điện [Current Law] của Kirchhoff khi vật chất là dòng điện. Bài toán luồng cực đại là bài toán đơn giản nhất liên quan đến các mạng luồng. Nó đặt vấn đề, Đâu là tốc độ lớn nhất mà vật có thể chuyển đi từ nguồn đến bồn mà không vi phạm bất kỳ hạn chế dung lượng nào? Như sẽ thấy trong chương này, bài toán này có thể được giải quyết bằng các thuật toán hiệu quat. Hơn nữa, ta có thể thích ứng các kỹ thuật căn bản mà các thuật toán này sử dụng để giải quyết các bài toán luồng mạng khác. Chương này trình bày hai phương pháp chung để giải quyết bài toán luồng cực đại. Đoạn 26, trình bày các khái niệm về các mạng luồng và các luồng lưu chuyển, chính thức định nghĩa bài toán luồng cực đại. Đoạn 26.2 mô tả phương pháp cổ điển của Ford và Fulkerson để tìm các luồng cực đại. Đoạn 26.3 mô tả một ứng dụng của phương pháp này: tìm một so khớp cực đại trong một đồ thị hai nhánh không hướng. Đoạn 26.4 trình bày phương pháp đẩy luồng trước [preflow - push], làm cơ sở cho nhiều thuật toán nhanh nhất để giải quyết các bài toán luồng mạng. Đoạn 26.5 đề cập thuật toán "nâng tới trước" [lift - to - front], một thực thi cụ thể của phương pháp đẩy luồng trước chạy trong thời gian O(V3). Tuy thật toán này không phải là thuật toán nhanh nhất được biết, song nó minh họa vài kỹ thuật được dùng trong các thuật toán nhanh nhất theo tiệm cận, và nó tương đối hiệu quả trong thực tế. 26.1 Các mạng luồng Trong đoạn này, ta nêu một định nghĩa về các mạng luồng theo lý thuyết đồ thị, đề cập các tính chất chúng, và định nghĩa bài toán luồng cực đại một cách chính xác. Ta cũng giới thiệu một hệ ký hiệu hữu ích. Các mạng luồng và các luồng Một mạng luồng [flow network] G = (V, E) là một đồ thị có hướng ở đó mỗi cạnh (u, v) E có một dung lượng không âm c(u ,v) ≥ o. Nếu (u, v) E, ta mặc nhận c(u, v) = 0. Ta phân biệt hai đỉnh trong một mạng luồng: một nguồn [source] s và một bồn [sink] t. Để tiện dụng, ta mặc nhận rằng mọi đỉnh nằm trên một lộ trình nào đó từ nguồn đến bồn. Nghĩa là, với mọi đỉnh v V, ta có một lộ trình s ~> v~> t. Do đó, đồ thị được liên thông, và |E| ≥ |V| - 1. Hình 26.1 có nêu một ví dụ của một mạng luồng. Giờ đây, ta đã sẵn sàng để định nghĩa các luồng chính thức hơn. Cho G = (V,E) là một mạng luồng (với một hàm dung lượng mặc định c). Cho s là nguồn của mạng, và cho t là bồn. Một luồng trong G là một hàm có giá trị thực f: V x V ® R thỏa ba tính chất dưới đây: Ràng buộc dung lượng: Với tất cả u,v V, ta yêu cầu f (u ,v) ≤ c (u, v). Tính đối xứng ghềnh: Với tất cả u,v V, ta yêu cầu f (u ,v) = -f (u, v). Bảo toàn luồng lưu: Với tất cả u V - [s,t], ta yêu cầu: Khối lượng f (u,v), có thể là dương hoặc âm, được gọi là luồng mạng [net flow] từ đỉnh u đến đỉnh v. Giá trị của một luồng f được định nghĩa là: |f| = (26.1) Nghĩa là, tổng luồng rời nguồn. (Ở đây, hệ ký hiệu |.| thể hiện giá trị luồng, chứ không phải là giá trị tuyệt đối hoặc bản số.) Trong bài toán luồng cực đại, ta có một mạng luồng G với nguồn s và bồn t, và ta muốn tìm một luồng của giá trị cực đại từ s đến t, và ta muốn tìm một luồng của giá trị cực đại từ s đến t. Hình 26.1. (a) Một mạng luồng G = (V,E) cho bài toán vận chuyển của công ty Lucky Puck. Nhà máy Vancouver là nguồn s, và nhà khoa Winnipeg là bồn t. Các quả khúc côn cầu được chuyển đi qua các thành phố trung gian, nhưng chỉ c (u,v) thùng hàng mỗi ngày có thể đi từ thành phố u đến thành phố v. Mỗi cạnh được gán nhãn with của nó dung lượng. (b) A flow f trong G with giá trị Nếu /f/ = 19. Chỉ các mạng luồng được nêu. Nếu f (u,v) > 0, cạnh (u,v) > 0, cạnh (u,v) được gắn nhãn bẵng f (u,v)/c (u,v). (Hệ ký hiệu dấu sổ (/) được dùng để đơn thuần tách biệt luồng với dung lượng; nó không biểu hiện phép chia.) Nếu f (u,v) ≤, cạnh (u,v) chỉ được gắn nhãn bằng dung lượng của nó. Trước khi xem một ví dụ về bài toán luồng mạng, ta hãy khảo sát ngắn gọn ba tính chất luồng. Sự ràng buộc dung lượng đơn giản muốn nói luồng mạng từ đỉnh này đến đỉnh khác không được vượt quá dung lượng đã cho. Tính đối xứng ghềnh nói rằng luồng mạng từ một đỉnh u đến một đỉnh v là âm của luồng mạng theo hướng nghịch đảo. Như vậy, luồng mạng từ một đỉnh đến chính nó sẽ là 0. Tính chất bảo toàn luồng lưu nói rằng tổng luồng mạng rời một đỉnh khác với nguồn hoặc bồn sẽ là 0. Theo tính đối xứng ghềnh, ta có thể viết lại tính chất bảo toàn luồng lưu là. với tất cả v V - [s,t]. Nghĩa là, tổng luồng mạng vào một đỉnh là 0. Cũng quan sát thấy có thể không có luồng mạng nào giữa u và v nếu không có cạnh nào giữa chúng. Nếu không có (u, v)E cũng không có (v,u) E, thì c (u,v)=c (u,v) = 0. Do đó, theo sự ràng buộc dung lượng, f (u,v) ≤ 0. Nhưng bởi f (u,v) = 0. Như vậy, luồng mạng phi zero từ xứng ghềnh, ta có f (u,v) = f (v,u) = 0. Như vậy, luồng mạng phí zero từ đỉnh đến u đến đỉnh v hàm ý rằng (u,v) E hoặc (v,u)E (hoặc cả hai). Nhận xét cuối cùng của chúng ta về các tính chất luồng có liên quan đến luồng mạng dương. Luồng mạng dương nhập một đỉnh v được định nghĩa bởi. (26.2) Luồng mạng dương rời một đỉnh được định nghĩa một cách đối xứng. Một diễn dịch về tính chất bảo toàn luồng lưu đó là luồng mạng dương nhập một đỉnh khác với nguồn hoặc bồn phải bằng với luồng mạng dương rời đỉnh. Một ví dụ về luồng mạng Một mạng luồng [flow network] có thể lập mô hình bài toán vận chuyển nêu trong Hình 26.1 Công ty Lucky Puck có một nhà myas (nguồn s) ở Vancouver chế tạo các quả bóng khúc côn cầu, và có một nhà kho (bồn t) ở Winnipeg lưu trữ chúng. Lucky Puck thuê không gian trên các xe tải một hãng khác để vận chuyển các quả bóng khúc côn cầu từ nhà máy đến nhà kho. Do các xe tải di chuyển trên các tuyến đường đã định giữa các thành phố và có một dung lượng hạn chế, Lucky Puck có thể vận chuyển tối đa c(u,v) thùng hàng mỗi ngày giữa mỗi cặp thành phố u và y trong Hình 26.1 (a). Mục tiêu của họ đó là xác định khối lượng lớn nhất p thùng hàng mỗi ngày có thể chuyển đi để rồi tạo ra khối lượng này, bởi không cần gì phải chế tạo số lượng quả bóng khúc côn cầu nhiều hơn mức có thể chuyển chúng đến nhà kho. Tốc độ mà các quả bóng khúc côn cầu được chuyển đi dọc theo một tuyến đường vận chuyển bất kỳ được xem là một luồng. Các quả bóng khúc côn cầu xuất phát từ nhà máy với tốc độ p thùng hàng mỗi ngày, và p thùng hàng phải đến nhà kho mỗi ngày. Lucky Puck không quan tâm đến thời gian mà một quả bóng đã cho di chuyển từ nhà máy đến nhà kho; học chỉ quan tâm rằng p thùng hàng mỗi ngày đến nhà kho. Các hạn chế dung lượng bị khống chế bởi mức hạn chế mà luồng f (u,v) từ thành phố u đến thành phố v tối đa là c(u,v) thùng hàng mỗi ngày. Trong một trạng thái ổn định, tốc độ mà các quả bóng khúc côn cầu nhập một thành phố trung gian trong mạng vận chuyển phải bằng tốc độ mà chúng rời đi; bằng không, chúng sẽ ùn đống. Do đó, sự bảo toàn luồng được tuân thủ. Như vậy, một luồng cực đại trong mạng xác định số lượng cực đại p thùng hàng mỗi ngày có thể được di chuyển đi. Hình 26.1 (b) nêu một luồng khả dĩ trong mạng được biểu thị cho một cách tương ứng tự nhiên với các chuyến hàng. Với bất kỳ hai đỉnh u và v trong mạng, luồng mạng f(u,v) tương ứng với một chuyến hàng gồm f (u,v) thùng hàng mỗi ngày từ u đến v. Nếu f (u,v) là 0 hoặc âm, thì không có chuyến hàng nào từ u đến v. Như vậy, trong Hình 26.1 (b), chỉ có các cạnh có luồng mạn dương mới được nêu, theo sau là một dấu sổ ngả trước và dung lượng của cạnh. Để hiểu rõ mối quan hệ giữa các luồng mạng và các chuyến hàng, ta tập trung vào các chuyến hàng giữa hai đỉnh. Hình 26.2 (a) nêu đồ thị con được cảm sinh bởi các đỉnh v1 và v2 trong mạng luồng của Hình 26.1. Nếu Lucky Puck chuyển 8 thùng hàng mỗi ngày từ v1 và v2, kết quả được nêu trong Hình 26.2 (b): luồng mạng từ v1 đến v2 là 8 thùng hàng mỗi ngày. Theo tính đối xứng ghềnh, ta cũng nói rằng luồng mạng theo hướng ngược lại, từ v2 đến v1 là -8 thùng hàng mỗi ngày, cho dù ta không chuyển quả bóng khúc côn cầu nào từ v2 đến v1. Nói chung, luồng mạng từ v1 đến v2 trừ số lượng mỗi ngày được chuyển đi từ v2 đến v1. Quy ước của chúng ta để biểu thị các luồng mạng đó là chỉ nêu các luồng mạng dương, bởi chúng nêu rõ các chuyến hàng thực tế: như vậy, chỉ một 8 xuất hiện trong hình, mà không có -8 tương ứng. Hình 26.2 Sự khử. (a) Các đỉnh v1 và v2 và v2, với c (v1 - v2)) = 10 và c (v2 - v1) = 4. (b) Các nêu rõ luồng mạng khi 8 thùng hàng mỗi ngày được chuyển đi từ v1 đến v2 (c). Một chuyến hàng bổ sung 3 thùng hàng mỗi ngày được thực hiện từ v2 đến v1. (d) Bằng cách khử luồng đi theo các hướng ngược lại, ta có thể biểu diễn tình huống trong (c) bằng luồng mạng dương theo chỉ một hướng. (e) Một chuyến 7 thùng hàng mỗi ngày khác được chuyển đi từ v2 đến v1. Giờ đây ta bổ sung một chuyến hàng khác, lần này là 3 thùng hàng mỗi ngày từ v2 đến v1. Hình 26.2 (c) có nêu phần biễu diễn tự nhiên của kết quả. Giờ đây ta có một tình huống ở đó có các chuyến hàng theo cả hai giữa v1 và v2. Ta chuyển 8 thùng hàng mỗi ngày từ v1 đến v2 và 3 thùng hàng mỗi ngày từ v2 đến v1. Đâu là các luồng mạng giữa hai đỉnh? Luồng mạng từ v1 đến v2 là 8 - 3 = 5 thùng hàng mỗi ngày, và luồng mạng từ v2 các v1 là 3 - 8 = -5 các thùng hàng mỗi ngày. Tình huống tương đương trong kết quả của nó với tình huống nêu trong Hình 26.2 (d), ở đó 5 thùng hàng mỗi ngày được chuyển đi từ v1 đến v2 và không có chuyến hàng nào được thực hiện từ v2 đến v1. Trên thực tế, 3 thùng hàng mỗi ngày từ v2 đến v1 được khử bởi 3 trong số 8 thùng hàng mỗi ngày từ v1 đến v2. Trong cả hai tình huống, luồng mạng từ v1 đến v2 là 5 thùng hàng mỗi ngày, nhưng trong (d), các chuyến hàng thực tế thực hiện theo chỉ một hướng. Nói chung, phép cho phép ta biểu diễn các chuyến hàng giữa hai thành phố bằng một luồng lạng dương dọc theo tối đa một trong hai cạnh giữa các đỉnh tương ứng. Nếu có luồng mạng zero hoặc âm từ đỉnh này đến đỉnh khác, ta không cần thực hiện chuyến hàng nào theo hướng đó. Nghĩa là, bất kỳ tình huống nào ở đó các quả bóng khúc côn cầu được chuyển đi theo cả hai hướng giữa hai thành phố đều có thể dùng phép hủy để biến đổi thành một tình huống tương đương ở đó các quả bóng khúc côn cầu được chuyển đi theo chỉ một hướng: hướng của luồng mạng dương. Các hạn chế dung lượng không bị vi phạm bởi phép biến đổi này, bởi ra rút gọn các chuyến hàng trong cả hai hướng, và các hạn chế bảo toàn không bị vi phạm, bởi luồng mạng giữa hai đỉnh là giống nhau. Tiếp tục với ví dụ của chúng ta, hãy xác định hiệu ứng của việc chuyển một chuyến 7 thùng hàng mỗi ngày khác từ v2 đến v1. Hình 26.2 (e) nêu kết quả dùng quy ước chỉ biểu thị các luồng mạng dương. Luồng mạng từ v1 đến v2 trở thành 5 - 7 = -2 và luồng mạng từ v2 đến v1 trở thành 7 - 5 = 2. Bởi luồng mạng từ v2 đến v1 là dương, nó biểu diễn một chuyến 2 thùng hàng mỗi ngày từ v2 đến v1. Luồng mạng từ v1 đến v2 là - 2 thùng hàng mỗi ngày, và bởi luồng mạng không dương, nên không có các quả bóng khúc côn cầu được chuyển đi theo hướng này. Một cách khác, trong số 7 thùng hàng bảo đảm mỗi ngày từ v2 đến v1, ta có thể xem 5 thùng là khả chuyến hàng 5 thùng mỗi ngày từ v1 đến v2, để lại 2 thùng hàng làm chuyến hàng thực tế mỗi ngày từ v2 đến v1. Hình 26.3 Chuyển đổi một bài toán luồng cực đại đa nguồn, đa bồn thành một bài toán có một nguồn đơn và một bồn đơn. (a). Một mạng luồng với năm nguồn S = [s1, s2,s3,s4,s5] và ba bồn T = [t1,t2,t3]. (b) Một mạng luồng nguồn đơn, bồn đơn tương đương. Ta bổ sung một siêu nguồn [supersource] s' và một cạnh có dung lượng vô hạn từ s' đến mỗi trong số nhiều nguồn. Ta cũng bổ sung một siêu bồn [supersink] t' và một cạnh có dung lượng vô hạn từ mỗi trong số nhiều bồn đến t'. Các mạng có nhiều nguồn và bồn Một bài toán luồng cực đại có thể có nhiều nguồn và bồn, thay vì chỉ có một. Ví dụ, công ty Lucky Puck có thể thực tế có một tập hợp m nhà máy [s1,s2,....sm] và một tập hợp n nhà kho [t1,t2.....,tn], như đã nêu trong hình 26.3 (b) nêu cách chuyển đổi mạng từ (a) thành mạng luồng cực đại bình thường. Ta có thể rút gọn bài toán xác định một luồng cực đại trong một mạng có nhiều nguồn và nhiều bồn thành bài toán luồng cực đại bình thường. Hình 26.3 (b) nêu cách chuyển đổi mạng từ (a) thành mạng luồng bình thường với chỉ một nguồn đơn và một bồn đơn. Ta bổ sung một siêu nguồn s và bổ sung một cạnh có hướng (s,si) với dung lượng c(s,si) = cho mỗi i = 1,2,.....,m. Ta cũng tạo một siêu bồn mới t và bổ sung một cạnh có hướng (tj,t) cho mỗi i = 1, 2,....n. Theo trực giác, bất kỳ luồng nào trong mạng của (a) tương ứng với một luồng trong mạng của (b), và ngược lại. Nguồn đơn s đơn giản cung cấp luồng theo như mong muốn của nhiều nguồn si, và bồn đơn t cũng vậy, nó tiêu thụ luồng theo như mong muốn của nhiều bồn t cũng vậy, nó tiêu thụ luồng theo như mong muốn của nhiều bồn ti. Bài tập 26.1-3 yêu cầu bạn chứng minh theo hình thức rằng hai bài toàn là tương đương. Làm việc với các luồng Ta sẽ đề cập đến vài hàm (như f) tiếp nhận hai đỉnh trong một mạng luồng làm đối số. Trong chương này, ta sẽ dùng một hệ ký hiệu phép lấy tổng ẩn ở đó một trong hai, hoặc cả hai, đối số có thể là một tập hợp các đỉnh, và giá trị được biểu hiện được hiểu là tổng của tất cả cách thay thế các đối số khả dĩ bằng các phần tử của chúng. Ví dụ, nếu X và Y là những tập hợp các đỉnh, thì F (X,Y) = Để lấy một ví dụ khác, ta có thể diễn sự ràng buộc bảo toàn luồng như là điều kiện f (u,V) = 0 với tất cả u V - [s,t]. Ngoài ra, để tiện dụng, ta thường bỏ qua các dấu ngoặc ôm tập hợp khi chúng được dùng trong hệ ký hiệu phép lấy tổng ẩn. Ví dụ, trong chương trình f (s, V - s) = f (s,V), số hạng V - s có nghĩa là tập hợp V - [s]. Ký hiệu tập hợp ẩn thường đơn giản hóa các phương trình có liên quan đến các luồng. Bổ đề dưới đây, mà phần chứng minh của nó được để lại làm Bài tập 26.1-4, sẽ chốt giữ vài đồng nhất thức thường gặp nhất có liên quan đến các luồng và ký hiệu tập hợp ẩn. Bổ đề 26.1 Cho G = (V, E) là một mạng luồng, và cho f là một luồng trong G. Thì, với X V, F (X, X) = 0. Với X, YV, F (X, Y) = -f (Y, X). Với X, Y, Z V mà X Y = f. F (X ∪ Y, Z) = f (X, Z) + f (Y, Z) và f (Z, X ∪ Y) = f (Z, X) + f (Z, X). Để lấy ví dụ về cách làm việc với hệ ký hiệu phép lấy tổng ẩn, ta có thể chứng minh rằng giá trị của một tổng luồng mạng vào bồn; nghĩa là |f| = f (V,t) (26.3) Theo trực giác điều này là đúng, bởi tất cả các đỉnh khác với nguồn và bồn đều có một luồng mạng 0 do sự bảo toàn luồng lưu, và như vậy bồn là đỉnh duy nhất khác có thể có một luồng mạng phi zero để so khớp luồng mạng phi zero của nguồn. Phần chứng minh hình thức của chúng ta sẽ như sau: |f| = f (s, V) (theo định nghĩa) = f (V, V) - f (V-s, V) (theo Bồ đề 26.1) = f (V, V-s) (theo Bồ đề 26.1) = f (V, t) + f (V, V-s-t) (Theo bồ đề 26.1) = f (V, t) (theo sự bảo toàn luồng lưu). Ở phần sau trong chương trình này, ta sẽ tổng quát hóa kết quả này (Bổ đề 26.5). Bài tập 26.1-1 Cho các đỉnh u và v trong một mạng luồng, ở đó c (u,v) = 5 và c (v,u) = 8, giả sử 3 đơn vị của luồng được chuyển đi từ u đến v và 4 đơn vị được chuyển đi từ v đến u. Đâu là luồng mạng từ u đến v? Vẽ tình huống theo kiểu dáng của Hình 26.2. 26.1-2 Xác minh mỗi trong số ba tính chất luồng f nêu trong Hình 26.1 (b). 27.1-3 Mở rộng các tính chất luồng và phần định nghĩa cho bài toán đa nguồn, đa bồn. Chứng tỏ bất kỳ luồng nào trong một mạng luồng đa nguồn, đa bồn đều tương ứng với một luồng có giá trị đồng nhất trong mạng nguồn đơn, bồn đơn có được bằng cách bổ sung một siêu nguồn và một siêu bồn, và ngược lại. 26.1-4 Chứng minh Bổ đề 26.1. 26.1-5 Với mạng luồng G = (V,E) và luồng f nêu trong Hình 27.1 (b), hãy tìm một cặp tập hợp con X,YV mà f (X,Y) = - f (V - X,YI). Sau đó, tìm một cặp tập hợp con X,YV ,à f (X,Y) ≠ - f (V - X,Y). 26.1-6 Căn cứ vào một mạng luồng G = (V,E), cho f1 và f2 là các hàm từ V x V đến R. tổng luồng f1 + f2 là hàm từ V x X đến R được định nghĩa bởi. (f1 + f2) (u,v) + f2 (u,v) (26.4) với tất cả u,vV. Nếu f1 và f2 là các luồng trong G, tổng luồng f1 + f2 phải thỏa tính chất nào trong số ba tính chất luồng, và có thể vi phạm tính chất nào? 26.1-7 Cho f là một luồng trong một mạng, và cho là một số thực. Tích luồng vô hướng f là một hàm từ V x V đến R được định nghĩa bởi (f) (u,v) = . (u,v). Chứng minh các luồng trong một mạng hình thành một tập hợp lồi bằng cách chứng tỏ nếu f1 và f2 là các luồng, thì như vậy là một f1 + (1-) f2 với tất cả trong miền giá trị 0 ≤ ≤ 1. 26.1-8 Phát biểu bài toán luồng cực đại dưới dạng một bài toán lập trình tuyến tính. 26.1-9 Mô hình mạng luồng đã giới thiệu trong đoạn này hỗ trợ luồng của một mặt hàng; một mạng luồng nhiều mặt hàng hỗ trợ luồng p mặt hàng giữa một tập hợp p đỉnh nguồn S = [s1,s2,....,sp] và một tập hợp p đỉnh bồn T = [t1,t2,....,tp] Luồng mạng của mặt hàng thứ i từ u đến v được ký hiệu là fi (u,v). Với mặt hàng thứ i, nguồn duy nhất là si và bồn duy nhất là ti. Ta có sự bảo toàn luồng lưu độc lập cho mỗi mặt hàng: luồng mạng của mỗi mặt hàng rời mỗi đỉnh là zero trừ phi đỉnh là nguồn hoặc bồn cho mặt hàng đó. Tổng các luồng mạng của tất cả các mặt hàng từ u đến v không được vượt quá c (u,v), và các luồng mặt hàng tương tác theo cách này. Giá trị của luồng mỗi mặt hàng là luồng mạng rời nguồn cho mặt hàng đó. Tổng giá trị luồng là tổng các giá trị của tất cả p luồng mặt hàng. Chứng minh có một thuật toán thời gian đa thức giải quyết bài toàn tìm tổng giá trị luồng cực đại của một mạng luồng đa mặt hàng bằng cách trình bày toán dưới dạng một chương trình tuyến tính. 26.2. Phương pháp Ford - Fulkerson Phần này sẽ trình bày phương pháp Ford - Fulkerson để giải quyết bài toán luồng cực đại. Ta gọi nó là “phương pháp” thay vì một “thuật toán” bởi nó bao hàm vài thực thi có các thời gian thực hiện khác nhau. Phương pháp Ford-Fulkerson tuỳ thuộc vào ba ý tưởng quan trọng vượt trên phương pháp và có nhiều liên quan đến thuật toán và bài toán luồng: các mạng thặng dư, các lộ trình tăng cường và các phần cắt. Các ý tưởng này là thiết yếu đối với định lý max-flow min-cut quan trọng (Định lý 26.7), định rõ đặc điểm đối với giá trị của một luồng cực đại theo dạng các phần cắt của mạng luồng. Để kết thúc đoạn này, ta trình bày một kiểu thực thi cụ thể của phương pháp Ford-Fulkerson và phân tích thời gian thực hiện của nó. Ford-F