Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức

Định lý (Luồng Nguyên) Nếu các khả năng thông qua là số nguyên, thì có tồn tại luồng cực đại nguyên. Chứng minh. Thuật toán Ford-Fulkerson kết thúc và luồng cực đại nó tìm được là luồng nguyên. Liên quan đến thuật toán Ford-Fulkerson ▶ Làm thế nào tính được lát cắt cực tiểu? Dễ thôi, xem chứng minh Định lý Max Flow-Min Cut. ▶ Làm thế nào để tìm đường tăng luồng? Dùng BFS! ▶ Nếu thuật toán kết thúc thì luồng thu được có là luồng cực đại? Có chứ. Lát cắt cực tiểu là bằng chứng. ▶ Thuật toán có luôn kết thúc? Có, mỗi lần tìm được đường tăng luồng là luồng lại tăng lên. Luồng không thể tăng vô hạn.

pdf42 trang | Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 462 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Luồng trên mạng V0.1 Trần Vĩnh Đức HUST Ngày 20 tháng 11 năm 2019 1 / 34 Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006. 2 / 34 Nội dung Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson Luồng cực đại và lát cắt cực tiểu Tính hiệu quả của thuật toán Bài toán chuyển dầu ptg12441863 887Network-flow algorithms SIMPLYlLLALLPIPESTOFULLCAPACITY/THERWISE NOTALLPIPESARE FULL BUTOILmOWSTHROUGHTHENETWORK CONTROLLEDBYSWITCH SETTINGS AT THE JUNCTIONS SATISFYING A LOCAL EQUILIBRIUM con- DITIONATTHEJUNCTIONSTHEAMOUNTOFOILmOWINGINTOEACH JUNCTION IS EQUAL TO THE AMOUNTOFOILmOWINGOUT&OR EX- AMPLE CONSIDERTHENETWORKINTHEDIAGRAMONTHEOPPOSITE PAGE/PERATORSMIGHTSTARTTHEmOWBYOPENINGTHESWITCHES ALONGTHEPATH0->1->3->5 WHICHCANHANDLEUNITSOFmOW THENOPENSWITCHESALONGTHEPATH0->2->4->5TOGETANOTHER UNITOFmOWINTHENETWORK3INCE0->1, 2->4, and 3->5AREFULL THEREISNODIRECTWAY TOGETMOREmOWFROM0 to 5 BUTIFWECHANGETHESWITCHAT1TOREDIRECTENOUGHmOW TOlLL1->4 WEOPENUPENOUGHCAPACITYIN3->5TOALLOWUSTOADDAUNITOFmOWON 0->2->3->5%VENFORTHISSIMPLENETWORK lNDINGSWITCHSETTINGSTHATINCREASETHEmOW ISNOTANEASYTASKFORACOMPLICATEDNETWORK WEARECLEARLYINTERESTEDINTHEFOLLOWING QUESTION7HATSWITCHSETTINGSWILLMAXIMIZETHEAMOUNTOFOILmOWINGFROMSOURCE TOSINK7ECANMODELTHISSITUATIONDIRECTLYWITHANEDGE WEIGHTEDDIGRAPHTHATHASA SINGLESOURCEANDASINGLESINK4HEEDGESINTHENETWORKCORRESPONDTOTHEOILPIPES THEVERTICESCORRESPONDTOTHEJUNCTIONSWITHSWITCHESTHATCONTROLHOWMUCHOILGOES INTOEACHOUTGOINGEDGE ANDTHEWEIGHTSONTHEEDGESCORRESPONDTOTHECAPACITYOFTHE PIPES7EASSUMETHATTHEEDGESAREDIRECTED SPECIFYINGTHATOILCANmOWINONLYONEDI- RECTIONINEACHPIPE%ACHPIPEHASACERTAINAMOUNTOFmOW WHICHISLESSTHANOREQUAL TOITSCAPACITY ANDEVERYVERTEXSATISlESTHEEQUILIBRIUMCONDITIONTHATTHEmOWINIS EQUALTOTHEmOWOUT4HISmOW NETWORKABSTRACTIONISAUSEFULPROBLEM SOLVINGMODEL THATAPPLIESDIRECTLYTOAVARIETYOFAPPLICATIONSANDINDIRECTLYTOSTILLMORE7ESOME- TIMESAPPEALTOTHEIDEAOFOILmOWINGTHROUGHPIPESFORINTUITIVESUPPORTOFBASICIDEAS Anatomy of a network-flow problem flow value associated with each edgecapacities 6 8 0 1 2.0 0 2 3.0 1 3 3.0 1 4 1.0 2 3 1.0 2 4 1.0 3 5 2.0 4 5 3.0 0 1 2.0 2.0 0 2 3.0 1.0 1 3 3.0 2.0 1 4 1.0 0.0 2 3 1.0 0.0 2 4 1.0 1.0 3 5 2.0 2.0 4 5 3.0 1.0 tinyFN.txt standard drawing V source sink E drawing with capacities drawing with flow flow representation Local equilibrium in a flow network inflow equals outflow at every vertex (except the source and the sink) 4 / 34 Mô hình bài bài toán s a b c d e t 3 3 10 2 1 4 1 5 1 2 5 ▶ Đồ thị có hướng biểu diễn mạng đường ống, dầu có thể được chuyển qua đường ống này ▶ Mục tiêu là chuyển dầu từ s đến t, nhiều nhất có thể. 5 / 34 Một luồng chuyển 7 đơn vị dầu từ s tới t s a b c d e t 2/3 1/3 0/10 2/2 1/1 4/4 1/1 5/5 0/1 2/2 5/5 luồng khả năng thông qua Liệu có cách nào làm tốt hơn? 6 / 34 Mạng Định nghĩa Một mạng được định nghĩa là bộ G = (V,E, s, t, c), ở đây ▶ (V,E) là một đồ thị có hướng; ▶ s, t ∈ V, gọi là đỉnh nguồn và đỉnh đích; và ▶ c là một hàm gắn trên mỗi cạnh e của G một giá trị ce > 0 gọi là khả năng thông qua. Bài toán Ta muốn chuyển nhiều dầu nhất có thể từ s tới t mà không vượt quá khả năng thông qua trên mỗi cạnh. 7 / 34 Định nghĩa (Luồng) Một luồng trên mạng G là một hàm f : E −→ R+ ∪ {0}, gắn mỗi cạnh e của G với một giá trị số fe, sao cho: 1. Không vi phạm khả năng thông qua: 0 ≤ fe ≤ ce với mọi e ∈ E 2. Với mọi đỉnh u, ngoại trừ s và t, tổng luồng vào u bằng tổng luồng ra khỏi u: ∑ (w,u)∈E fwu = ∑ (u,z) fuz. Nói cách khác, mạng là bảo toàn (theo luật Kirchhoff). 8 / 34 Luồng và lượng dầu chuyển s a b c d e t 2/3 1/3 0/10 2/2 1/1 4/4 1/1 5/5 0/1 2/2 5/5 luồng khả năng thông qua 9 / 34 Định nghĩa Giá trị của luồng là tổng lượng gửi từ s đến t. Theo luật bảo toàn, size(f) bằng lượng rời khỏi s: size(f) = ∑ (s,u)∈E fsu. ▶ Mục đích của chúng ta là tìm được luồng có giá trị cực đại. ▶ Tương đương, tìm cách gán giá trị {fe : e ∈ E} thỏa mãn một số ràng buộc. ▶ Đây là một bài toán quy hoạch tuyến tính. 10 / 34 Ví dụ Bài toán tìm luồng cực đại trong mạng s a b t 1 1 1 1 1 tương đương với bài toán quy hoạch tuyến tính max fsa + fsb 0 ≤ fsa, fsb, fab, fat, fbt ≤ 1 fsa = fat + fab fsb + fab = fbt 11 / 34 Nội dung Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson Luồng cực đại và lát cắt cực tiểu Tính hiệu quả của thuật toán Thuật toán tham lam ▶ Bắt đầu với luồng 0 ▶ Lặp lại : Chọn một đường đi thích hợp từ s tới t và tăng luồng nhiều nhất có thể dọc theo đường này. 13 / 34 Khởi tạo s a b t 0/1 0/1 0/1 0/1 0/1 Tăng luồng s a b t 1/1 0/1 0/1 1/1 0/1 Tăng luồng s a b t 1/1 1/1 0/1 1/1 1/1 Luồng cực đại s a b t 1/1 1/1 0/1 1/1 1/1 14 / 34 Khởi tạo s a b t 0/1 0/1 0/1 0/1 0/1 Tăng luồng s a b t 1/1 0/1 1/1 0/1 1/1 Hủy luồng trên cạnh a→ b s a b t 1/1 1/1 0/1 1/1 1/1 Luồng cực đại s a b t 1/1 1/1 0/1 1/1 1/1 15 / 34 Tìm đường tăng luồng Tìm cạnh (u, v) có một trong hai kiểu ▶ (u, v) ∈ E và khả năng thông qua cuv vẫn chưa đầy. Khi đó fuv có thể tăng thêm nhiều nhất là cuv − fuv. ▶ (v, u) ∈ E và có một luồng qua đó, tức là fvu > 0. Khi đó ta có thể giảm một phần hoặc toàn bộ fvu. 16 / 34 Đường tăng luồng Cạnh gốc ▶ e = (u, v) ∈ E ▶ Luồng fe ▶ Khả năng ce Cạnh ngược ▶ eR = (v, u) ▶ “Giảm” luồng fe đã gửi Khả năng thông qua còn lại cf(e) = { ce − fe nếu e ∈ E fe nếu eR ∈ E. Ví dụ s a b t 1/1 0/1 1/1 0/1 1/1 17 / 34 Đồ thị tăng luồng Định nghĩa Đồ thị tăng luồng của mạng G với luồng f là đồ thị Gf = (V,Ef, cf) với Ef = {e : fe 0}. Ví dụ Mạng G với luồng f và đồ thị tăng luồng Gf tương ứng. s a b t 1/1 0/1 1/1 0/1 1/1 s a b t 1 1 1 1 1 18 / 34 Đường tăng luồng Định nghĩa ▶ Một đường tăng luồng là một đường đi từ s đến t trong đồ thị tăng luồng Gf. ▶ Khả năng thông qua của đường tăng luồng P là cf(P) = min{cf(e) : e ∈ P} Augment(f, c,P) δ = cf(P) foreach cạnh e ∈ P: if (e ∈ E) fe = fe + δ else f(eR) = f(eR)− δ return f 19 / 34 Thuật toán Ford-Fulkerson Ford-Fulkerson (G) foreach cạnh e ∈ E: fe = 0 Gf = đồ thị tăng luồng của G và f while (còn đường tăng luồng P trong Gf): f = Augment(f, c,P) Cập nhật Gf return f 20 / 34 Lecture slides by Kevin Wayne Copyright © 2005 Pearson-Addison Wesley Copyright © 2013 Kevin Wayne Last updated on Sep 8, 2013 6:40 AM 7. NETWORK FLOW I ‣ Ford-Fulkerson demo 2Ford-Fulkerson algorithm demo s t 0 / 2 0 / 10 0 / 6 0 / 10 0 / 4 0 / 8 0 / 9 network G 0 / 10 0 value of flow 0 / 10 flow capacity s t 2 6 10 4 9 residual graph Gf 10 residual capacity 10 10 8 3Ford-Fulkerson algorithm demo 2 6 4 9 residual graph Gf 10 10 s t 0 / 2 0 / 10 0 / 6 0 / 10 0 / 4 0 / 8 0 / 9 network G 0 / 10 0 0 / 10 s t 10 10 8 8 — 8 — 8 — + 8 = 8 4Ford-Fulkerson algorithm demo 4 residual graph Gf 10 s t 0 / 2 8 / 10 0 / 6 8 / 10 0 / 4 8 / 8 0 / 9 network G 0 / 10 8 0 / 10 8 8 8 9s 2 2 — 10 2 — 2 — + 2 = 10 10 6 2 — 2 t 5Ford-Fulkerson algorithm demo 4 residual graph Gf s t 2 / 2 10 / 10 0 / 6 10 / 10 0 / 4 8 / 8 2 / 9 network G 0 / 10 10 0 / 10 8 2 2 10 10 10 7s 10 6 t 6 — 8 — 6 — + 6 = 16 6 — 6Ford-Fulkerson algorithm demo residual graph Gf s t 2 / 2 10 / 10 6 / 6 10 / 10 0 / 4 8 / 8 8 / 9 network G 6 / 10 16 6 / 10 8 8 10 10 1 6 6 6 4 4s 4 t 2 8 — 0 — 2 — 8 — + 2 = 18 7Ford-Fulkerson algorithm demo residual graph Gf s t 0 / 2 10 / 10 6 / 6 10 / 10 2 / 4 8 / 8 8 / 9 network G 8 / 10 18 8 / 10 8 10 10 6 8 2 2 8 1 2 s 2 t2 8 9 — 9 — 7 — 3 — 9 — + 1 = 19 8Ford-Fulkerson algorithm demo residual graph Gf s t 0 / 2 10 / 10 6 / 6 10 / 10 3 / 4 7 / 8 9 / 9 network G 9 / 10 19 9 / 10 10 10 6 9 2 3 9 9 1 s 1 t1 7 1 nodes reachable from s min cut max flow Nội dung Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson Luồng cực đại và lát cắt cực tiểu Tính hiệu quả của thuật toán Phân hoạch L = {s, a, b} và R = {c, d, e, t} s a b c d e t 2/3 1/3 0/10 2/2 1/1 4/4 1/1 5/5 0/1 2/2 5/5 R ▶ Lượng dầu chuyển từ s sang t phải chuyển từ L sang R. ▶ Không luồng nào có thể vượt tổng khả năng thông qua của các cạnh từ L sang R = 4 + 1 + 2 = 7. ▶ Vậy luồng này là tối ưu. 22 / 34 Định nghĩa ▶ Một (s, t)-lát cắt (hay ngắn gọn là lát cắt) là một cách phân hoạch tập đỉnh thành hai phần L và R sao cho s ∈ L và t ∈ R. ▶ Khả năng thông qua của (s, t)-lát cắt là tổng khả năng thông qua của các cạnh từ L đến R. Cụ thể, capacity(L,R) = ∑ u∈L, v∈R cuv. Chặn trên cho luồng Với mỗi luồng f và mỗi lát cắt (L,R), ta luôn có size(f) ≤ capacity(L,R). 23 / 34 Định lý (Max Flow-Min Cut) Kích thước của luồng cực đại trong mạng bằng với khả năng thông qua của lát cắt cực tiểu. Chứng minh. ▶ Xét f là luồng tìm được do thuật toán Ford-Fulkerson. Khi đó t không đến được từ s trong đồ thị Gf. ▶ Xét L là các nút đạt được từ s, và đặt R = V− L. Vậy (L,R) là một lát cắt. ▶ Ta khẳng định rằng size(f) = capacity(L,R). ▶ Bởi vì: Mọi cạnh từ L tới R phải đã đầy khả năng thông qua, và mọi cạnh từ R tới L phải có luồng bằng 0. 24 / 34 Định lý (Luồng Nguyên) Nếu các khả năng thông qua là số nguyên, thì có tồn tại luồng cực đại nguyên. Chứng minh. Thuật toán Ford-Fulkerson kết thúc và luồng cực đại nó tìm được là luồng nguyên. 25 / 34 Q & A Liên quan đến thuật toán Ford-Fulkerson ▶ Làm thế nào tính được lát cắt cực tiểu? Dễ thôi, xem chứng minh Định lý Max Flow-Min Cut. ▶ Làm thế nào để tìm đường tăng luồng? Dùng BFS! ▶ Nếu thuật toán kết thúc thì luồng thu được có là luồng cực đại? Có chứ. Lát cắt cực tiểu là bằng chứng. ▶ Thuật toán có luôn kết thúc? Có, mỗi lần tìm được đường tăng luồng là luồng lại tăng lên. Luồng không thể tăng vô hạn. 26 / 34 Nội dung Bài toán luồng cực đại trên mạng Thuật toán Ford-Fulkerson Luồng cực đại và lát cắt cực tiểu Tính hiệu quả của thuật toán Trường hợp tồi tệ của thuật toán Kể cả khi khả năng thông qua là tối ưu, số đường tăng luồng cần tìm có thể lớn bằng giá trị của luồng! Ví dụ Mạng sau có luồng cực đại là 2× 2100 và thuật toán Ford-Fulkerson có thể dùng đến 2× 2100 đường tăng luồng để tìm được luồng cực đại. s a b t 2100 2100 1 2100 2100 28 / 34 Ví dụ Khởi tạo và tìm đường tăng luồng đầu tiên s a b t 0/2100 0/2100 0/1 0/2100 0/2100 29 / 34 Ví dụ Tìm đường tăng luồng thứ hai s a b t 1/2100 0/2100 1/1 0/2100 1/2100 30 / 34 Ví dụ Tìm đường tăng luồng thứ ba s a b t 1/2100 1/2100 0/1 1/2100 1/2100 Tiếp tục 2× (2100 − 1) lần như vậy, ta được luồng tối ưu. 31 / 34 Trường hợp tồi tệ của thuật toán ▶ Số đường tăng luồng cần tìm có thể lớn bằng giá trị của luồng! ▶ Tuy nhiên, trường hợp này có thể tránh được nếu lựa chọn đường tăng luồng cẩn thận (Ngắn nhất hoặc Đầy nhất). Ví dụ s a b t 2100 2100 1 2100 2100 32 / 34 Lựa chọn đường tăng luồng Đường tăng luồng số đường cài đặt Đường ngẫu nhiên ≤ mℓ hàng đợi ngẫu nhiên Đường DFS ≤ mℓ ngăn xếp (DFS) Đường ngắn nhất ≤ 1/2mn hàng đợi (BFS) Đường đầy nhất ≤ m ln(mℓ) hàng đợi ưu tiên Bẳng: Đồ thị có trọng số với n đỉnh và m cạnh, và các khả năng thông qua là số nguyên trong khoảng 1 đến ℓ 33 / 34 Bài tập Hãy chạy thuật toán Ford-Fulkerson để tìm luồng cực đại cho mạng sau. Bạn nên dùng thuật toán BFS để tìm đường tăng luồng. s a b c d e t 3 3 10 2 1 4 1 5 1 2 5 34 / 34

Các file đính kèm theo tài liệu này:

  • pdfbai_giang_toan_roi_rac_bai_21_luong_tren_mang_tran_vinh_duc.pdf
Tài liệu liên quan