Bài toán dòng chảy lớn nhất maximal flow năm 2024

Trong lý thuyết đồ thị, mạng luồng là một đồ thị có hướng, trong đó mỗi cạnh có một độ thông qua và một giá trị luồng. Lượng luồng trên mỗi cạnh không được vượt quá độ thông qua của cạnh đó. Lượng luồng đi vào một đỉnh phải bằng lượng luồng đi ra khỏi nó, trừ khi đó là đỉnh nguồn (có nhiều lượng luồng đi ra hơn), hay đỉnh đích (có nhiều lượng luồng đi vào hơn). Mạng luồng có thể dùng để mô hình hóa hệ thống đường giao thông, dòng chảy của chất lỏng trong ống, dòng điện trong mạch, hay bất kỳ các bài toán nào tương tự khi có sự di chuyển trong một mạng các nút.

Mô hình các ống dẫn nước bằng một mạng luồng. Mỗi ống nước có đường kính xác định nên chỉ cho phép một lưu lượng nước xác định chảy qua. Ở nơi giao điểm giữa các ống, lưu lượng nước đi vào phải bằng lưu lượng nước đi ra nếu không nước sẽ nhanh chóng bị thất thoát. Ta có một bồn nước, hay đỉnh phát, và một vòi nước, hay đỉnh thu. Một cách trực quan, giá trị luồng trên mạng chính là vận tốc nước chảy ra từ vòi. Luồng còn có thể mô hình sự lưu chuyển của người hay hàng hóa trên các mạng giao thông, dòng điện trong hệ thống phân phối,… Đối với các hệ thống mạng này, luồng đi vào các nút trung gian cần phải bằng luồng đi ra khỏi nút đó. Tính chất này cũng giống như định luật dòng điện Kirchhoff. Mạng luồng còn được ứng dụng trong sinh thái học: mạng luồng xuất hiện khi xem xét sự lưu chuyển chất dinh dưỡng và năng lượng giữa các nhóm khác nhau trong một mạng thức ăn. Các bài toán gắn với loại mạng sinh thái này hoàn toán khác với trường hợp mạng chất lỏng hay mạng giao thông.

Bài toán luồng cực đại trên mạng yêu cầu tìm một luồng tương thích có giá trị lớn nhất trong mạng luồng có một đỉnh phát và một đỉnh thu. Bài toán luồng cực đại trên mạng có thể xem như trường hợp đặc biệt của lớp các bài toán mạng phức tạp hơn, chẳng hạng như bài toán lưu thông. Định lý luồng cực đại-lát cắt hẹp nhất (max-flow min-cut theorem) chỉ ra giá trị luồng cực đại từ s đến t (đỉnh phát đến đỉnh thu) bằng giá trị của lát cắt s-t hẹp nhất trên mạng.

Bạn hãy thử giải quyết bài toán luồng cực đại trên mạng: cho một mạng luồng, hãy tìm giá trị luồng cực đại.

Presentation on theme: "Chương 6 Bài toán luồng cực đại Maximum Flow Problem"— Presentation transcript:

1 Chương 6 Bài toán luồng cực đại Maximum Flow Problem 11/09/15 Chương 6 Bài toán luồng cực đại Maximum Flow Problem w s v u t z 3/3 1/9 1/1 4/7 4/6 3/5 2/2 

2 Bài toán luồng cực đại Maximum Flow Problem 11/09/15 w s v u t z 3/3 1/9 1/1 4/7 4/6 3/5 2/2 

3 NỘI DUNG Bài toán luồng cực đại trong mạng. Lát cắt, Đường tăng luồng. 11/09/15 Bài toán luồng cực đại trong mạng. Lát cắt, Đường tăng luồng. Định lý về luồng cực đại và lát cắt hẹp nhất. Thuật toán Ford-Fulkerson Thuật toán Edmond-Karp. Các ứng dụng 3 3

4 11/09/15 L. R. Ford; D. R. Fulkerson (1962). Flows in Networks. Princeton, NJ: Princeton University Press. 4

5 Lester Randolph Ford, Jr (1927 ~) 11/09/15 Lester Randolph Ford, Jr. (born September 23, 1927), son of Lester R. Ford, Sr., is an American mathematician specializing in network flow programming. His 1956 paper with D. R. Fulkerson on the maximum flow problem established the maxflow-mincut theorem. 5

6 Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976) 11/09/15 Delbert Ray Fulkerson was a mathematician who co- developed the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks. Ph.D, Univ. of Wisconsin-Madison, 1951. In 1956, he published his famous paper on the Ford- Fulkerson algorithm together with Lester Randolph Ford. In 1979, the renowned Fulkerson Prize was established which is now awarded every three years for outstanding papers in discrete mathematics jointly by the Mathematical Programming Society and the American Mathematical Society. 6

7 Network Flows 11/09/15 Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993. 1 1 4 2 1 2 1 s 2 t 3 1 2 3 864 pages! 1 1 7

8 Mạng và luồng trong mạng 11/09/15 Mạng và luồng trong mạng 8

9 Mạng là đồ thị có hướng G = (V,E) : MẠNG (Network) 11/09/15 Mạng là đồ thị có hướng G = (V,E) : Có duy nhất một đỉnh s không có cung đi vào gọi là đỉnh phát (nguồn) và duy nhất một đỉnh t không có cung đi ra gọi là đỉnh thu (đích). Mỗi cung e của G được gắn với một số không âm c(e) được gọi là khả năng thông qua của e. Ví dụ: v 3 6 1 7 t s 3 w 9 5 1 5 u z 2 9

10 LUỒNG TRONG MẠNG 1) Hạn chế về khả năng thông qua (Capacity Rule): 11/09/15 Định nghĩa. Luồng f trong mạng G=(V,E) là phép gán số f(e) cho mỗi cạnh e ( f(e) được gọi là luồng trên cạnh e) thoả mãn các điều kiện: 1) Hạn chế về khả năng thông qua (Capacity Rule): Với mỗi cung e, 0  f (e)  c(e) 2) Điều kiện cân bằng luồng (Conservation Rule): Với mỗi v  s, t trong đó E(v) và E(v) tương ứng là tập các cung đi vào và đi ra khỏi đỉnh v. Định nghĩa. Giá trị của luồng f là (Đẳng thức (*) thu được bằng cách cộng tất cả các điều kiện cân bằng luồng.)

11 LUỒNG TRONG MẠNG – Ví dụ 11/09/15 Ví dụ: w s v u t z 3/3 2/9 1/1 1/3 3/7 2/6 4/5 3/5 2/2 Trong 2 số viết bên mỗi cạnh: giá trị luồng trên cạnh là số màu đỏ, số còn lại là khả năng thông qua. Các điều kiện 1) và 2) được thoả mãn => f là luồng trên mạng. Giá trị luồng là: 8 = f(s,v) + f(s,u) + f(s,w) = f(v,t) + f(w,t) + f(z,t) 11

12 Bài toán luồng cực đại 11/09/15 Luồng trong mạng G được gọi là luồng cực đại nếu trong số tất cả các luồng trong mạng G nó là luồng có giá trị lớn nhất Bài toán tìm luồng cực đại trong mạng G được gọi là bài toán luồng cực đại v 1/3 2/6 1/1 3/7 t s 3/3 w 2/9 4/5 1/1 3/5 u z 2/2 Luồng với giá trị 8 = = v 3/3 4/6 1/1 3/7 t s 3/3 w 2/9 4/5 1/1 3/5 u z 2/2 Luồng cực đại có giá trị 10 = = 12

13 Mạng 11/09/15 Mạng: G = (V, E, s, t, c) . (V, E) = đồ thị có hướng, không có cung lặp. Có hai đỉnh đặc biệt: s = phát/nguồn (source), t = thu/đích (sink). c(e) = khả năng thông qua (capacity) của cung e. 2 9 5 10 15 15 4 10 s 5 3 8 6 10 t 4 6 15 Capacity 10 15 4 30 7 13

14 Luồng Luồng từ s đến t là hàm f: E  R thoả mãn: 11/09/15 Luồng từ s đến t là hàm f: E  R thoả mãn: Với mỗi e  E:  f(e)  c(e) (hạn chế kntq) Với mỗi v  V – {s, t}: (cân bằng luồng) * flow: abstract entity generated at source, transmitted across edges, absorbed at sink * flow conservation is analogous to Kirchoff's law 2 9 5 4 10 15 15 4 10 4 4 4 s 5 3 8 6 10 t kntq Capacity 4 6 15 10 15 Luồng Flow 4 30 7 14

15 Luồng 11/09/15 Bài toán luồng cực đại: Tìm luồng có tổng luồng trên các cạnh đi ra khỏi đỉnh phát là lớn nhất: * a more natural quantity to maximize is net flow into t * intuitively net flow into t equal net flow out of s, we'll show this formally later * assume no arcs enter s or leave t (makes a little cleaner, no loss of generality) 2 9 5 4 10 15 15 4 10 4 4 4 s 5 3 8 6 10 t kntq 4 6 15 10 15 Luồng Giá trị = 4 4 30 7 15

16 Luồng Luồng có giá trị 24 trong mạng: kntq Giá trị = 24 Luồng 1 11 s 2 11/09/15 Luồng có giá trị 24 trong mạng: s 2 3 4 5 6 7 t 15 30 10 8 9 11 1 Giá trị = 24 kntq Luồng 16

17 Luồng Luồng có giá trị 28 trong mạng: kntq Giá trị = 28 Luồng 1 14 s 2 11/09/15 Luồng có giá trị 28 trong mạng: s 2 3 4 5 6 7 t 15 30 10 8 9 14 1 Giá trị = 28 kntq Luồng 17

18 Luồng trong mạng Mạng Đỉnh Cung Luồng truyền thông 11/09/15 Mạng Đỉnh Cung Luồng truyền thông trạm giao dịch, máy tính, vệ tinh cáp nối, cáp quang, voice, video, packets mạng điện cổng, registers, processors dây dẫn dòng điện cơ khí joints rods, beams, springs heat, energy thuỷ lợi hồ chứa, trạm bơm, nguồn nước đường ống dòng nước, chất lỏng tài chính nhà băng giao dịch tiền giao thông sân bay, ga tàu, giao lộ đường cao tốc, ray, đường bay hàng hoá, phương tiện, hành khách hoá học sites bonds energy 18

19 Luồng trong mạng Mạng Đỉnh Cung Luồng communication 11/09/15 Mạng Đỉnh Cung Luồng communication telephone exchanges, computers, satellites cables, fiber optics, microwave relays voice, video, packets circuits gates, registers, processors wires current mechanical joints rods, beams, springs heat, energy hydraulic reservoirs, pumping stations, lakes pipelines fluid, oil financial stocks, currency transactions money transportation airports, rail yards, street intersections highways, railbeds, airway routes freight, vehicles, passengers chemical sites bonds energy 19

20 Các ứng dụng/qui dẫn Network connectivity. Network reliability. 11/09/15 Network connectivity. Bipartite matching. Data mining. Open-pit mining. Airline scheduling. Image processing. Project selection. Baseball elimination. Network reliability. Security of statistical data. Distributed computing. Egalitarian stable matching. Many many more . . . 20

21 Lát cắt – Đường tăng luồng 11/09/15 Lát cắt – Đường tăng luồng 21

22 Lát cắt (Cuts) 11/09/15 Lát cắt là cách phân hoạch tập đỉnh (S, T) sao cho s  S, t  T. Khả năng thông qua cap(S,T) của lát cắt (S, T) là số: Lát cắt nhỏ nhất (hẹp nhất) là lát cắt với kntq nhỏ nhất. 2 9 5 10 15 15 4 10 s 5 3 8 6 10 t 4 6 15 10 15 kntq = 30 4 30 7 22

23 Lát cắt 11/09/15 Lát cắt (S1, T1), S1={s,2,3,4}, T={5,6,7,t) có khả năng thông qua 62: s 2 3 4 5 6 7 t 15 30 10 8 9 cap(S1,T1)= 62 23

24 Lát cắt 11/09/15 Lát cắt (S2, T2), S2={s,3,4,7}, T2={2,5,6,t) có khả năng thông qua 28: Caveat: from now on, we'll use terms "flow" and "cut" to mean s-t flow and s-t cut. 2 9 5 10 15 15 4 10 s 5 3 8 6 10 t 4 6 15 10 15 cap(S2,T2) = 28 4 30 7 24

25 Luồng và lát cắt 11/09/15 Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: trong đó S  T = {(v,w)E: vS, wT} và T S = {(v,w)E: vT, w S} 6 total amount of flow that leaves S minus amount flow that "swirls" back 2 9 5 10 6 Giá trị = 24 10 15 15 4 10 4 4 8 8 s 5 3 8 6 10 t 10 4 6 15 10 15 10 4 30 7 10 25

26 Luồng và lát cắt 11/09/15 Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 10 6 4 8 s 2 3 5 7 t 15 30 9 Giá trị = 24 26

27 Luồng và lát cắt 11/09/15 Bổ đề 1. Giả sử f là luồng, và (S, T) là lát cắt. Khi đó giá trị luồng chảy qua lát cắt chính bằng giá trị của luồng: 10 6 4 8 s 2 3 5 7 t 15 30 9 Giá trị = 24 27

28 Luồng và lát cắt 11/09/15 Chứng minh bổ đề: Giả sử f là luồng còn (S, T) là lá cắt. Khi đó CM. Cộng tất cả các ràng buộc cân bằng luồng theo mọi vS, đơn giản biểu thức ta thu được: s v t u w tổng theo các cung xanh tổng theo các cung tím S T từ đó suy ra đẳng thức cần chứng minh 28

29 Luồng và lát cắt 11/09/15 Bổ đề 2. Giả sử f là luồng, còn (S, T) là lát cắt. Khi đó, val(f) cap(S, T). CM. S T 4 8 t s 7 6 29

30 Luồng cực đại và lát cắt nhỏ nhất Max Flow and Min Cut 11/09/15 Hệ quả. Giả sử f là luồng, còn (S, T) là lát cắt. Nếu val(f) = cap(S, T), thì f là luồng cực đại còn (S, T) là lát cắt hẹp nhất. CM. Xét f’ là luồng bất kỳ và (S’,T’) là lát cắt bất kỳ. Theo bổ đề ta có val(f’)  cap(S,T) = val(f)  cap(S’,T’). 9 2 9 5 10 1 9 10 15 15 4 10 4 8 9 s 5 3 8 6 10 t 4 10 4 6 15 10 15 14 4 30 7 14 Giá trị luồng = 28 kntq của lát cắt = 28 30

31 Định lý về luồng cực đại và lát cắt nhỏ nhất Max-Flow Min-Cut Theorem 11/09/15 Đinh lý (Ford-Fulkerson, 1956): Trong mạng bất kỳ, giá trị của luồng cực đại luôn bằng khả năng thông qua của lát cắt nhỏ nhất. Proof (muộn hơn). s 2 3 4 5 6 7 t 15 30 10 8 9 14 1 Flow value = 28 Cut capacity = 28 31

32 Ý tưởng thuật toán Thuật toán tham lam: 11/09/15 Thuật toán tham lam: Bắt đầu từ luồng 0 (Luồng có giá trị = 0). Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). Tăng luồng dọc theo đường đi P. Lặp lại cho đến khi gặp bế tắc. 4 5 4 4 4 4 s 10 2 13 3 10 t Luồng có giá trị = 0 32

33 Ý tưởng thuật toán Thuật toán tham lam: 11/09/15 Thuật toán tham lam: Bắt đầu từ luồng 0 (Luồng có giá trị = 0). Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). Tăng luồng dọc theo đường đi P. Lặp lại cho đến khi gặp bế tắc. 4 5 4 4 4 4 10 X s 10 2 13 3 10 t Giá trị luồng = 10 33

34 Ý tưởng thuật toán Thuật toán tham lam: 11/09/15 Thuật toán tham lam: Bắt đầu từ luồng 0 (Luồng có giá trị = 0). Tìm đường đi P từ s đến t trong đó mỗi cung thoả mãn f(e) < c(e). Tăng luồng dọc theo đường đi P. Lặp lại cho đến khi gặp bế tắc. Thuật toán tham lam cho luồng với giá trị 10. s 4 2 5 3 t 10 13 34

35 Ý tưởng thuật toán Thuật toán tham lam không cho lời giải tối ưu. 11/09/15 Thuật toán tham lam không cho lời giải tối ưu. TT tham lam: Giá trị luồng = 10 s 4 2 5 3 t 10 13 Tối ưu: Giá trị luồng = 14 s 4 2 5 3 t 10 13 6 35

36 ĐỒ THỊ TĂNG LUỒNG- ĐƯỜNG TĂNG LUỒNG 11/09/15 ĐỒ THỊ TĂNG LUỒNG- ĐƯỜNG TĂNG LUỒNG 36

37 Đồ thị tăng luồng – Tập cung 11/09/15 Mạng đã cho G = (V, E). Luồng f(e), e  E. Cung e = (v, w)  E. Đồ thị tăng luồng: Gf = (V, Ef ). “thu lại" luồng đã gửi. Ef = {e: f(e) =0 0 }. Khả năng thông qua v w 17 6 kntq Luồng Kntq v w 11 6 e = (u,v)  eR = (v,u) 37

38 Đồ thị tăng luồng - Ví dụ Đồ thị tăng luồng: Gf = (V, Ef ). 11/09/15 Đồ thị tăng luồng: Gf = (V, Ef ). Ef = {e : f(e) < c(e)}  {eR : f(e) > 0}. cf(e) cho biết lượng lớn nhất có thể tăng luồng trên cung e. cf(eR) cho biết lượng lớn nhất có thể giảm luồng trên cung e. s 4 2 5 3 t 10 13 G s 4 2 5 3 t 10 Gf 38

39 Đường tăng luồng cf (P) = min {cf (e): e  P }. cf (P) = 4 11/09/15 Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng Gf. Khả năng thông qua của đường đi P là cf (P) = min {cf (e): e  P }. s 4 2 5 3 t 10 13 4 6 X G s 4 2 5 3 t 10 Gf cf (P) = 4 3 39

40 Đường tăng luồng 11/09/15 Đường tăng luồng = đường đi từ s đến t trên đồ thị tăng luồng. Luồng là cực đại  không tìm được đường tăng luồng??? s 4 2 5 3 t 10 13 6 G s 4 2 5 3 t 10 6 7 Gf Giá trị luồng = 14 40

41 Định lý về luồng cực đại và lát cắt nhỏ nhất 11/09/15 Định lý đường tăng luồng (Ford-Fulkerson, 1956): Luồng là cực đại khi và chỉ khi không tìm được đường tăng luồng. Định lý về luồng cực đại và lát cắt nhỏ nhất (Ford-Fulkerson, 1956): Giá trị của luồng cực đại bằng khả năng thông qua của lát cắt nhỏ nhất. Ta sẽ chứng minh định lý tổng hợp sau: Định lý. Giả sử f là luồng trong mạng. Ba mệnh đề sau là tương đương (i) Tìm được lát cắt (S, T) sao cho val(f) = cap(S, T). (ii) f là luồng cực đại. (iii) Không tìm được đường tăng luồng f. 41

42 Thuật toán Ford-Fulkerson: 11/09/15 Để tìm luồng cực đại của mạng vận tải G, ta xuất phát từ luồng tuỳ ý ϕ của G, rồi nâng luồng lên đầy, sau đó áp dụng thuật toán Ford-Fulkerson. Thuật toán gồm 3 bước: Bước 1 (đánh dấu ở đỉnh của mạng):Lối vào v0 được đánh dấu bằng 0. Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số +i để đánh dấu cho mọi đỉnh y chưa được đánh dấu mà (vi,y)∈E và cung này chưa bão hoà (ϕ(vi,y)0). 42

43 Thuật toán Ford-Fulkerson: 11/09/15 Nếu với phương pháp này ta đánh dấu được tới lối ra vn thì trong G tồn tại giữa v0 và vn một xích α, mọi đỉnh đều khác nhau và được đánh dấu theo chỉ số của đỉnh liền trước nó (chỉ sai khác nhau về dấu). Khi đó chắc chắn ta nâng được giá trị của luồng. 43

44 Thuật toán Ford-Fulkerson: 11/09/15 Bước 2 (nâng giá trịcủa luồng): Đểnâng giá trịcủa luồng ϕ, ta đặt: ϕ’(e) = ϕ(e), nếu e∉α ϕ’(e) = ϕ(e)+1, nếu e∈α được định hướng theo chiều của xích α đi từ vo đến vn ϕ’(e) = ϕ(e)−1, nếu e∈α được định hướng ngược với chiều của xích α đi từ vo đến vn ϕ’ thoả mãn các điều kiện về luồng, nên ϕ’ là một luồng và ta có: ϕ’n= ϕn+1. Như vậy, ta đã nâng được luồng lên một đơn vị. Sau đó lặp lại một vòng mới. Vì khả năng thông qua của các cung đều hữu hạn, nên quá trình phải dừng lại sau một số hữu hạn bước. 44

45 Thuật toán Ford-Fulkerson: 11/09/15 Bước 3: Nếu với luồng ϕ0 bằng phương pháp trên ta không thể nâng giá trị của luồng lên nữa, nghĩa là ta không thể đánh dấu được đỉnh vn, thì ta nói rằng quá trình nâng luồng kết thúc và ϕ0 đã đạt giá trịcực đại, đồng thời gọi ϕ0 là luồng kết thúc. 45

46 Thuật toán Ford – Fulkerson 11/09/15 Augment(f,P) b  cf(P) FOR e  P DO IF (e  E) THEN // cạnh thuận f(e)  f(e) + b ELSE // cạnh nghịch f(eR)  f(e) – b RETURN f Tăng luồng f dọc theo đường tăng P Ví dụ Ford_Fulkerson(G,c,s,t); FOR e  E DO // Khởi tạo luồng 0 f(e)  0 Gf  đồ thị tăng luồng f WHILE (tìm được đường tăng luồng P) DO f  augment(f, P) Sửa lại Gf RETURN f Thuật toán Ford-Fulkerson 46

47 Ví dụ: 11/09/15 Cho mạng vận tải như hình dưới đây với khả năng thông qua được đặt trong khuyên tròn, luồng được ghi trên các cung. Tìm luồng cực đại của mạng này. 47

48 Mạng vận tải G có đỉnh phát là V0 và đỉnh thu là V8. Giải: 11/09/15 Mạng vận tải G có đỉnh phát là V0 và đỉnh thu là V8. Luồng ϕ có đường đi (v0,v4), (v4,v6), (v6,v8) gồm các cung chưa bão hoà nên nó chưa đầy. Do đó có thể nâng luồng của các cung này lên một đơn vị, để được ϕ1