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

các cạnh trong mạng thặng dư bao gồm tất cả các cạnh (u, v) của G’ sao cho c(u, v) - [u, v] ≠ 0. Do đó, thời gian để tìm một lộ trình trong một mạng thặng dư là O(E’) = O(E) nếu ta dùng thuật toán tìm kiếm độ sâu đầu tiên hoặc tìm kiếm độ rộng đầu tiên. Như vậy, mỗi lần lặp lại của vòng lặp while sẽ mất O(E) thời gian, khiến tổng thời gian thực hiện của FORD-FULKERSON trở thành O(E|ƒ*|). Khi các dung lượng là tích phân và giá trị luồng tối ưu |ƒ*| nhỏ, thời gian thực hiện của thuật toán Ford-Fulkerson tỏ ra thích hợp. Hình 26.7(a) có nêu một ví dụ về nội dung có thể xảy ra trên một mạng luồng đơn giản mà |ƒ*| là lớn. Một luồng cực đại mạng này có giá trị 2,000,000: 1,000,000 đơn vị của luồng băng ngang lộ trình s → u → t, và một 1,000,000 đơn vị khác băng ngang lộ trình s → v → t. Nếu lộ trình tăng cường đầu tiên mà FORD-FULKERSON tìm thấy là s → u → v → t, xem Hình 26.7(a), luồng có giá trị 1 sau lần lặp lại đầu tiên. Mạng thặng dư kết quả được nêu trong Hình 26.7(b). Nếu lần lặp thứ hai tìm thấy lộ trình tăng cường s → v → u → t, như đã nêu trong hình 26.7(b), thì luồng sẽ giá trị 2. Hình 26.7(c) nêu mạng thặng dư kết quả. Ta có thể tiếp tục chọn lộ trình tăng cường s → u → v → t trong các lần lặp lại đánh số lẻ và lộ trình tăng cường s → u → v → t trong các lần lặp lại đánh số chẵn. Ta sẽ thực hiện một tổng 2,000,000 lần tăng cường, mỗi lần chỉ tăng giá trị luồng lên 1 đơn vị. Có thể cải thiện cận trên FORD-FULKERSON nếu ta thực thi phép tính của lộ trình tăng cường p trong dòng 4 bằng một thuật toán tìm kiếm độ rộng đầu tiên, nghĩa là, nếu lộ trình tăng cường là một lộ trình ngắn nhất từ s đến t trong mạng thặng dư, ở đó mỗi cạnh có một khoảng cách đơn vị (trọng số). Ta gọi phương pháp Ford-Fulkerson đó là đã thực thi thuật toán Edmonds-Karp. Giờ đây ta chứng minh thuật toán Edmonds-Karp chạy trong O(VE2) thời gian. Phần phân tích tuỳ thuộc vào các khoảng cách đến các đỉnh trong mạng thặng dư . Bổ đề dưới đây sử dụng hệ ký hiệu (u, v) với khoảng cách lộ trình ngắn nhất từ u đến v trong ở đó mỗi cạnh có khoảng cách đơn vị. Bổ đề 26.8 Nếu thuật toán Edmonds-Karp chạy trên mạng luồng G = (V, E) với nguồn s và bồn t, thì với tất cả các đỉnh v Î V - {s, t}, khoảng cách lộ trình ngắn nhất (s, t) trong mạng thặng dư sẽ tăng đơn điệu với mỗi phép tăng cường luồng. Chứng minh Vì sự mâu thuẫn, ta giả sữ với một đỉnh v Î V - {s, t}, ta có một phép tăng cường luồng khiến (s, v) giảm. Cho ƒ’ là luồng ngay trước phép tăng cường và cho ƒ là luồng ngay sau đó. Thì, (s, v) < (s, v) Ta có thể mặc nhận mà không làm mất tính tổng quát rằng (s, v) ≤ (s, u) với tất cả các đỉnh u Î V - {s, t} sao cho (s, u) < (s, u). Tương đương, ta có thể mặc nhận rằng với tất cả các đỉnh u Î V - {s, t}, (s, u) < (s, v) hàm ý (s, u) ≤ (s, u) (26.7) Giờ đây ta lấy một lộ trình ngắn nhất p’ trong có dạng s u → v và xét đỉnh u đứng trước v trên lộ trình này. Ta phải có (s, u) = (s, v) -1 theo Hệ luận 26.2, bởi (u, v) là một cạnh trên p’, chính là một lộ trình ngắn nhất từ s đến v. Do đó, theo giả thuyết (26.7) của chúng ta, (s, u) ≤ (s, u) . Như vậy, với các đỉnh v và u được thiết lập, ta có thể xát luồng mạng ƒ từ u đến v trước khi phép tăng cường của luồng trong . Nếu ƒ[u, v] < c(u, v), thì ta có (s, v) ≤ (s, u) + 1 (theo Bổ đề 26.3) ≤ (s, u) + 1 = (s, v), mâu thuẫn với giả thuyết của chúng ta rằng phép tăng cường luồng giảm khoảng cách từ s đến v. Như vậy, ta phải có ƒ[u, v] = c(u, v), có nghĩa là (u, v) . Giờ đây, lộ trình tăng cường p đã được chọn trong để tạo ra phải chứa cạnh (u, v) theo hướng từ v đến u, bởi (u, v)Î (theo giả thuyết) và (u, v) như ta vừa nêu. Nghĩa là, việc tăng cường luồng dọc theo lộ trình p đẩy luồng trở lại dọc theo (u, v) và v xuất hiện trước u trên p. Bởi p là một lộ trình ngắn nhất từ s đến t, các lộ trình con của nó là các lộ trình ngắn nhất (Bổ đề 26.1) và như vậy ta có (s, u) = (s, v) + 1. Bởi vậy, (s, v) = (s, u) - 1 ≤ (s, u) - 1 = (s, v) - 2 < (s, v), mâu thuẫn với giả thuyết ban đầu của chúng ta. Định lý dưới đây định cận số lần lặp lại của thuật toán Edmonds-Karp. Định lý 26.9 Nếu thuật toán Edmonds-Karp chạy trên một mạng luồng G = (V, E) với nguồn s và bồn t, thì tổng số lần tăng cường luồng mà thuật toán thực hiện sẽ tối đa là O(VE). Chứng minh Ta nói một cạnh (u, v) trong một mạng thặng dư là tới hạn trên một lộ trình tăng cường p nếu dung lượng thặng dư của p là dung lượng thăng dư của (u, v), nghĩa là, nếu (p) = (u, v). Sau khi đã tăng cường luồng dọc theo một lộ trình tăng cường, mọi cạnh tới hạn trên lộ trình đều sẽ biến mất khỏi mạng thặng dư. Hơn nữa, ít nhất một cạnh trên bất kỳ lộ trình tăng cường nào đều phải tới hạn. Cho u và v là các đỉnh trong V được liên thông bởi một cạnh trong E. (u, v) có thể là một cạnh tới hạn bao nhiêu lần trong khi thi hành thuật toán Edmonds-Karp? Bởi các lộ trình tăng cường là các lộ trình ngắn nhất, khi (u, v) tới hạn đầu tiên, nên ta có (s, v) = (s, u) + 1 . Một khi luồng được tăng cường, cạnh (u, v) biến mất khỏi mạng thặng dư. Nó không thể tái xuất hiện về sau trên một lộ trình tăng cường khác cho đến sau khi luồng mạng từ u đến v giảm và đều này chỉ xảy ra nếu (v, u) xuất hiện trên một lộ trình tăng cường. Nếu ’ là luồng trong G khi sự kiện này xảy ra, thì ta có (s, u) = (s, v) + 1 Bởi (s, v) ≤ (s, u) theo Bổ đề 26.8, ta có (s, u) = (s, v) + 1 (s, v) + 1 = (s, u) + 2. Kết quả là, từ lúc mà (u, v) trở thành tới hạn đến lúc đó nó trở thành tới hạn sau đó, khoảng cách của u từ nguồn sẽ gia tăng ít nhất 2. Thoạt đầu khoảng cách của u từ nguồn ít nhất là 1 và cho đến khi nó trở thành bất khả dụng từ nguồn, nếu như có thì khoảng cách của nó tối đa là |V| - 2. Như vậy, (u, v) có thể trở thành tới hạn tối đa O(V) lần. Bởi có O(E) cặp đỉnh có thể có một cạnh giữa chúng trong một đồ thị thặng dư, nên tổng các cạnh tới hạn trong nguyên cả tiến trình thi hành thuật toán Edmonds-Karp là O(E). Mỗi lộ trình tăng cường có ít nhất một cạnh tới hạn và do đó định lý đứng vững. Bởi mỗi lần lặp lại của FORD-FULKERSON có thể được thực thi trong O(E) Thời gian khi thuật toán tìm kiếm độ rộng đầu tiên tìm thấy lộ trình tăng cường, nên tổng thời gian thực hiện của thuật toán Edmonds-Karp là O(VE2). Thuật toán trong đoạn 26.4 cho ta phương pháp để đạt được một thời gian thực hiện O(V2E), lập thành cơ sở cho thuật toán O(V3) thời gian của Đoạn 26.5. Bài tập 26.2-1 Trong Hình 26.1(b), nêu luồng qua phần cắt ({s, v2, v4} , {v1, v3, t})? Đâu là dung lượng của phần cắt này? 26.2-2 Nêu tiến trình thi hành thuật toán Edmonds-Karp trên mạng luồng của Hình 26.1(a). 26.2-3 Trong ví dụ của Hình 26.6, nêu phần cắt cực tiểu tương ứng với luồng cực đại đã nêu? Trong số các lộ trình tăng cường xuất hiện trong ví dụ, nêu hai lộ trình khử luồng đã được chuyển đi trước đó? 26.2-4 Chứng minh với bất kỳ cặp đỉnh u và v bất kỳ dung lượng và hàm luồng c và ƒ, ta có (u, v) + (v, u) = c(u, v) + c(v, u). 26.2-5 Hãy nhớ lại phần xây dựng trong Đoạn 26.1 chuyển đổi một mạng luồng đa nguồn, đa luồng thành một mạng luồng đơn, bồn đơn bổ sung các cạnh có dung lượng vô hạn. Chứng minh rằng bất kỳ luồng nào trong mạng kết quả đều có một giá trị hữu hạn nếu các cạnh của mạng đa nguồn, đa luồng ban đầu có dung lượng hữu hạn. 26.2-6 Giả sử mỗi nguồn trong một bài toán đa nguồn, đa luồng tạo ra chính xác đơn vị của luồng, sao cho ƒ(s, V) = . Cũng giả sử mỗi bồn tiêu thụ chính xác đơn vị, sao cho ƒ(V, ) = , ở đó = . Nêu cách chuyển đổi bài toán tìm luồng ƒ tuân thủ hạn chế bổ sung này thành bài toán tìm một luồng cực đại trong một mạng luồng nguồn đơn, bồn đơn. 26.2-7 Chứng minh Bổ đề 26.3 26.2-8 Chứng tỏ một luồng cực đại trong một mạng G = (V, E) luôn có thể tìm thấy bởi một dãy tối đa |E| lộ trình tăng cường. (Mách nước: Xác định các lộ trình sau khi tìm luồng cực đại.) 26.2-9 Khả năng liên thông cạnh [edge connectivity] của một đồ thị không hướng là số lượng cực tiểu k cạnh phải được gỡ bỏ để làm gián đoạn đồ thị. Ví dụ, khả năng liên thông cạnh của một cây là 1, khả năng liên thông cạnh của một xích chu trình các đỉnh là 2. Nêu cách xác định khả năng liên thông cạnh của một đồ thị không hướng G = (V, E) bằng cách chạy một thuật toán luồng cực đại trên tối đa |V| mạng luồng, mỗi mạng có O(V) đỉnh và O(E) cạnh. 26.2-10 Chứng tỏ thuật toán Edmonds-Karp kết thúc sau tối đa |V| |E| /4 lần lặp lại. (Gợi ý: Với một cạnh (u, v), xét cách thay đổi của cả δ(s, u) lẫn δ(u, t) giữa các lần ở đó (u, v) là tới hạn.) 26.3. So khớp hai nhánh cực đại Có thể dễ dàng áp đổi vài bài toán tổ hợp dưới dạng bài toán luồng cực đại. Bài toán luồng cực đại đa nguồn, đa bồn trong Đoạn 26.1 đã cho ta một ví dụ. Có các bài toán tổ hợp khác bề ngoài có vẻ như chẳng dính dáng gì mấy đến các mạng luồng. Song thực tế có thể rút gọn thành một bài toán luồng cực đại. Đoạn này trình bày một bài toán như vậy: tìm một so khớp cực đại trong một đồ thị hai nhánh (xem Đoạn 5.4). Để giải quyết bài toán này, ta sẽ vận dụng một tính chất của tính tích phân mà phương pháp Ford-Fulkerson cung cấp. Ta cũng sẽ thấy phương pháp Ford-Fulkerson có thể được thực hiện để giải quyết bài toán so khớp hai nhánh cực đại trên một đồ thị G = (V,E) trong O(VE) thời gian. Bài toán so khớp hai nhánh cực đại Cho một đồ thị không hướng G = (V,E), một so khớp [matching] là một tập hợp các cạnh M Í E sao cho với tất cả các đỉnh v Î V, có tối đa một số cạnh của M là liên thuộc trên v. Ta nói rằng một định v Î V được so khớp bằng cách so khớp M nếu có một cạnh f trong M là liên thuộc trên v; bằng không, v không khớp [unmatched]. Một so khớp cực đại [maximum matching] là một so khớp bản số cực đại, nghĩa là, một so khớp M sao cho với một so khớp M’ bất kỳ, ta có ïMï ³ ïM’ï. Trong đoạn này, ta sẽ hạn chế sự chú ý để tìm các lần so khớp cực đại trong hai nhánh đồ thị. Ta mặc nhận tập hợp đỉnh có thể phân hoạch thành V = L È R, ở đó L và R rời nhau và tất cả các cạnh trong E nằm giữa L và R. Hình 26.8 minh họa khái niệm của một so khớp. Bài toán tìm một so khớp cực đại trong một đồ thị hai nhánh có nhiều ứng dụng thực tiễn. Để lấy ví dụ, ta có thể xét việc so khớp một tập hợp L máy với một tập hợp R công việc được thực hiện đồng thời. Hình 26.8. Một đồ thị hai nhánh G = (V,E) với phân hoạch định V = L È R. (a) Một so khớp với bản số 2. (b) Một so khớp cực đại với bản số 3. Ta xem sự hiện diện của cạnh (u,v) trong E có nghĩa là một máy cụ thể uÎL có thể thực hiện một công việc cụ thể vÎR. Một so khớp cực đại trung cấp công việc cho càng nhiều máy càng tốt. Tìm một so khớp hai nhánh cực đại Ta có thể dùng phương pháp Ford-Fulkerson để tìm ra một so khớp cực đại trong một đồ thị hai hánh không hướng G = (V,E) trong thời gian đa thức trong ïVï và ïEï. Điểm tinh tế đó là kiến tạo một mạng luồng ở đó các luồng tương ứng với các lần so khớp, như đã nêu trong Hình 26.9. Ta định nghĩa mạng luồng tương ứng G’ = (V’, E’) với đồ thị hai nhánh G như sau. Ta cho nguồn s và bồn t là các đỉnh mới không nằm trong V, và ta cho V’ = V È {s, t}. Nếu phân hoạch đỉnh của G là V = L È R, các cạnh có hướng của G’ sẽ căn cứ vào: E’ = {(s,u): uÎL} È {(u,v): uÎL, vÎR và (u,v) ÎE } È {(v,t): vÎR} Để hoàn thành phần xây dựng, ta gán dung lượng đơn vị cho mỗi cạnh trong E’. Định lý dưới đây chứng tỏ một so khớp trong G tương ứng trực tiếp với một luồng trong mạng luồng tương ứng G’ của G. Ta nói rằng một luồng f trên một mạng luồng G = (V,E) có giá trị số nguyên nếu f (u,v) là một số nguyên với tất cả (u,v) Î V x V. Hình 26.9. Mạng luồng tương ứng với một đồ thị hai nhánh. (a) Đồ thị hai nhánh G = (V,E) có phân hoạch đỉnh V = L È R từ Hình 26.8. Một so khớp cực đại được nêu bởi các cạnh tô bóng. (b) Mạng luồng tương ứng G’ có một luồng cực đại đã nêu. Mỗi cạnh có dung lượng đơn vị. Các cạnh tô bóng có một luồng là 1, và tất cả các cạnh khác không mang luồng nào cả. Các cạnh tô bóng từ L đến R tương ứng với các cạnh trong một so khớp cực đại của đồ thị hai nhánh. Bổ đề 26.10 Cho G = (V,E) là một đồ thị hai nhánh có phân hoạch đỉnh V=LÈR, và cho G’=(V’,E’) là mạng luồng tương ứng của nó. Nếu M là một so khớp trong G, thì có một luồng có giá trị số nguyên f trong G’ với giá trị ïfï = ïMï. Ngược lại, nếu f là một luồng có giá trị số nguyên trong G’, thì có một so khớp M trong G với bản số ïMï = ïfï. Chứng minh. Trước tiên ta chứng tỏ a so khớp M trong G tương ứng với một luồng có giá trị số nguyên trong G’. Định nghĩa f như sau. Nếu (u,v)ÎM, thì f(s,u) = f(u,v) = f(v,t) = 1 và f (u,s) = f(v,u) = f(t,v) = -1. Với tất cả các cạnh khác nhau (u,v) ÎE’, ta định nghĩa f(u,v) = 0. Theo trực giác, mỗi cạnh (u,v)ÎM tương ứng với 1 đơn vị của luồng trong G’ băng ngang lộ trình s ®u®v®t. Hơn nữa, các lộ trình mà các cạnh trong m cảm sinh có đỉnh rời nhau, ngoại trừ s và t. Để xác minh f thỏa tính đối xứng ghềnh, các hạn chế dung lượng, sự bảo toàn luồng lưu, ta chỉ cần nhận xét rằng có thể có f bằng cách tăng cường luồng dọc theo mỗi lộ trình như vậy. Luồng mạng qua phần cắt (LÈ{s}, RÈ{t} bằng với ïMï ; như vậy, theo Bổ đề 26.5 giá trị của luồng là ïfï =ïMï . Để chứng minh đảo đề, ta cho f là một luồng có giá trị số nguyên trong G’ và cho M = {(u,v): uÎL, vÎR, và (u,v)>0} Mỗi đỉnh uÎL chỉ có một cạnh vào, tức (s,v), và dung lượng của nó là 1. Như vậy, mỗi uÎL có tối đa một đơn vị của luồng mạng dương nhập vào nó. Bởi f có giá trị số nguyên, với mỗi uÎL, 1 đơn vị của luồng mạng dương sẽ nhập vào u nếu và chỉ nếu có chính xác một đỉnh vÎR sao cho f(u,v) = 1. Như vậy, có tối đa một cạnh rời từng uÎL sẽ mang luồng mạng dương. Có thể tạo một đối số đối xứng cho mỗi vÎR. Do đó, tập hợp M được định nghĩa trong phát biểu của định lý là một so khớp. Để thấy ïMï=ïfï, ta nhận xét rằng với mọi đỉnh so khớp uÎL, 1 đơn vị của luồng mạng dương sẽ nhập vào u nếu và chỉ nếu có chính xác một đỉnh vÎR sao cho f(u,v)=1. Như vậy, có tối đa một cạnh rời từng u ÎL sẽ mang luồng mạng dương. Có thể tạo một số đối xứng cho mỗi vÎR. Do đó, tập hợp M được định nghĩa trong phát biểu của định lý là một so khớp. Để thấy ïMï=ïfï, ta nhận thấy rằng với mọi đỉnh so khớp uÎL, ta có f(s,u)=1, và với mọi cạnh (u,v)ÎE-M, ta có f(u,v)=0. Bởi vậy, dùng Bổ đề 26.1, tính đối xứng ghềnh, và không có cạnh nào từ L đến t, ta được: ïMï = f(L,R) = f(L,V’)-f(L,L)-f(L,s)-f(L,t) = 0 - 0 + f(s,L) - 0 = f(s, V’) = ïfï Theo trực giác, một so khớp cực đại trong một đồ thị hai nhánh G tương ứng với một luồng cực đại trong mạng luồng tương ứng G’ của nó. Như vậy, ta có thể tính toán một so khớp cực đại trong G bằng cách chạy một thuật toán luồng cực đại trên G’. Khó khăn duy nhất trong biện luận này là thủ thuật toán luồng cực đại có thể trả về một luồng trong G’ bao gồm các lượng phi tích phân. Định lý dưới đây chứng tỏ nếu ta dùng phương pháp Ford-Fulkerson, khó khăn đó không thể nảy sinh. Định lý 26.11 (định lý tính tích phân) Nếu hàm dung lượng c chỉ tiếp nhận các giá trị tích phân, thì luồng cực đại f được tạo bằng phương pháp Ford-Fulkerson sẽ có tính chất ïfïcó giá trị số nguyên. Hơn nữa, với tất cả các đỉnh u và v, giá trị của f(u,v) là một số nguyên. Chứng minh. Phần chứng minh sẽ theo phương pháp quy nạp trên số lần lặp lại. Ta để nó làm Bài tập 26.3-2. Giờ đây, ta có thể chứng minh hệ luận dưới đây theo Bổ đề 26.10. Hệ luận 26.12 Bản số của một so khớp cực đại trong một đồ thị hai nhánh G là giá trị của một luồng cực đại trong mạng luồng tương ứng G’ của nó. Chứng minh. Ta dùng danh pháp trong Bổ đề 26.10. Giả sử rằng M là một so khớp cực đại trong G và luồng tương ứng f trong G’ không cực đại. Thì có một luồng cực đại f trong G’ sao cho ïf’ï > ïfï. Bởi các dung lượng trong G’ có giá trị số nguyên, theo Định lý 26.11 và f cũng vậy. Như vậy, f’ tương ứng với một so khớp M’ trong G có bản số ïM’ï=ïf’ï > ïfï= ïMï, mâu thuẫn với tính cực đại của M. Cũng vậy, ta có thể chứng tỏ nếu f là một luồng cực đại trong G’, so khớp tương ứng của nó là một so khớp cực đại trên G. Như vậy, cho một đồ thị hai nhánh không hướng G, ta có thể tìm ra một so khớp cực đại bằng cách tạo mạng luồng G’, chạy phương pháp Ford-Fulkerson, và trực tiếp có được một so khớp cực đại M từ luồng cực đại có giá trị số nguyên f đã tìm thấy. Do bất kỳ so khớp nào trong một đồ thị hai nhánh đều có bản số tối đa min(L,R) = O(V), nên giá trị của luồng cực đại trong G’ là O(V). Do đó, ta có thể tìm một so khớp cực đại trong một đồ thị hai nhánh trong thời gian O(VE) Bài tập 26.3-1 Chạy thuật toán Ford-Fulkerson trên mạng luồng trong Hình 26.9 (b) và nêu mạng thặng dư sau mỗi phép tăng cường luồng. Đánh số các đỉnh trong L từ trên xuống từ 1 đến 5 và trong R từ trên xuống từ 6 đến 9. Với mỗi lần lặp lại, bạn chọn lộ trình tăng cường nhỏ nhất theo thứ tự từ điển. 26.3-2 Chứng minh Định l ý 26.11 26.3-3 Cho G = (V,E) là một đồ thị hai nhánh với phân hoạch đỉnh V=LÈR, và cho G’ là mạng luồng tương ứng nhỏ của nó. Nêu một cận trên thích hợp trên chiều dài của bất kỳ lộ trình tăng cường nào tìm thấy trong G’ trong khi thi hành FORD-FULKERSON. 26.3-4* Một so khớp hoàn hảo [perfect matching] là một so khớp ở đó mọi đỉnh đều ăn khớp. Cho G = (V,E) là một đồ thị hai nhánh không hướng có phân hoạch đỉnh V=LÈR, ở đó ïLï=ïRï. Với bất kỳ X Í V, hay định nghĩa láng giềng của X khi N(X) = {yÎV: (x,y)ÎE với một xÎX}, nghĩa là, tập hợp các đỉnh kề với một phần tử của X. Chứng minh định lý Hall: ở đó tồn tại một so khớp hoàn hảo trong G nếu và chỉ nếu ïAï≤ïN(A)ï với mọi tập hợp con AÍL. 26.3-5 Một đồ thị hai nhánh G=(V,E), ở đó V=LÈR, là đều-d [d-regular] nếu mọi đỉnh vÎV có độ chính xác d. Mọi đồ thị hai nhánh đều - d có ïLï=ïRï. Chứng minh mọi đồ thị nhánh đều - d có một so khớp của bản số ïLï bằng cách chứng tỏ một phần cắt cực tiểu của mạng luồng tương ứng có dung lượng ïLï. 26.4. Các thuật toán đầy luồng trước Đoạn này trình bày cách tiếp cận “đẩy luồng trước” [preflow-push] để tính toán các luồng cực đại. Các thuật toán luồng cực đại nhanh nhất cho đến nay là các thuật toán đẩy luồng trước, và các bài toán luồng khác, như bài toán luồng có mức hao phí cực tiểu, có thể được giải quyết một cách hiệu quả bằng phương pháp đẩy luồng trước. Đoạn này giới thiệu thuật toán luồng cực đại “chung” của Goldberg, có một kiểu thực thi đơn giản chạy trong O(V2E) thời gian, và do đó cải thiện đối với cận O(VE2) của thuật toán Edmonds-Karp. Đoạn 26.5 tu chính thuật toán chung để có được một thuật toán luồng trước khác chạy trong O(V3) thời gian. Các thuật toán đẩy luồng trước làm việc theo cách cục bộ hóa hơn so với phương pháp Ford-Fulkerson. Thay vì xét nguyên cả mạng thặng dư G=(V,E) để tìm ra một lộ trình tăng cường, các thuật toán đẩy luồng trước lần lượt làm việc trên từng đỉnh một, chỉ xem xét các láng giềng của đỉnh trong mạng thặng dư. Vả lại, khác với phương pháp Ford-Fulkerson, các thuật toán đẩy luồng trước không duy trì tính chất bảo toàn luồng lưu xuyên suốt tiến trình thi hành. Tuy nhiên, chúng duy trì một luồng trước [preflow], làm một hàm f: V x V ® R thoả tính đối xứng ghềnh, các hạn chế dung lượng, và phép nới lỏng dưới đây về sự bảo toàn luồng lưu: f (V,u) ³ 0 với tất cả các đỉnh u Î V - {s}. Nghĩa là, ngoài luồng ra, luồng mạng vào mỗi đỉnh đều không âm. Ta gọi luồng mạng vào một đỉnh u là luồng thặng dư vào u, căn cứ vào: E(u) = f(V,u) (27.8) Ta nói rằng một đỉnh u Î V - {s,t} đang tràn nếu e(u) >0. Để bắt đầu đoạn này, ta mô tả trực giác nằm sau phương pháp đầy luồng trước. Sau đó, ta sẽ nghiên cứu hai phép toán mà phương pháp sử dụng: “đẩy” luồng trước và “nâng” một đỉnh. Cuối cùng, ta sẽ trình bày một thuật toán đẩy luồng trước chung và phân tích tính đúng đắn cùng với thời gian thực hiện của nó. Trực giác Trực giác đằng sau phương pháp đẩy luồng trước được hiểu rõ nhất dưới dạng các luồng chất lỏng: ta xét một mạng luồng G=(V,E) là một hệ thống các ống dẫn tương kết của các dung lượng đã cho. Áp dụng tính tương tự này cho phương pháp Ford-Fulkerson, ta có thể nói rằng mỗi lộ trình tăng cường trong mạng sẽ làm cho một luồng chất lỏng bổ sung nâng lên, mà không có các điểm nhánh, chảy từ nguồn đến bồn. Phương pháp Ford-Fulkerson liên tục bổ sung thêm các luồng chảy cho đến khi không thể bổ sung thêm được nữa. Thuật toán đẩy luồng tước chung có một trực giác hơi khác. Cũng như trước, các cạnh có hướng tương ứng với các ống dẫn. Các đỉnh, là các khớp nối ống, có hai tính chất đáng quan tâm. Thứ nhất, để điều tiết luồng thặng dư, mỗi đỉnh có một ống thoát dẫn đến một bồn chứa lớn một cách tùy ý có thể tích luỹ chất lỏng. Thứ hai, mỗi đỉnh, bồn chứa của nó, và tất cả các tuyến nối ống của nó nằm trên một nền tảng có chiều cao gia tăng khi thuật toán tiến triển. Các chiều cao đỉnh sẽ xác định luồng sẽ được đẩy ra sao: ta chỉ đẩy luồng đổ xuống đồi, nghĩa là, từ một đỉnh cao hơn xuống một đỉnh thấp hơn. Có thể có luồng mạng dương từ một đỉnh thấp hơn đến một đỉnh cao hơn, nhưng các phép toán đẩy luồng luôn đẩy nó xuống đồi. Chiều cao của các nguồn được cố định tại ïVï, và chiều cao của bốn được cố định tại 0. Tất cả các chiều cao đỉnh khác bắt đầu tại 0 và gia tăng theo thời gian. Trước tiên, thuật toán gửi càng nhiều luồng càng tốt xuống đồi từ nguồn về phía bồn. Lượng mà nó gửi chính xác đủ để điền mỗi ống đi ra từ nguồn đến dung lượng; nghĩa là, nó gửi dung lượng của phần cắt (s,V-s). Khi lần đầu tiên luồng nhập một đỉnh trung gian, nó gom lại trong bồn chứa của đỉnh. Từ đó, cuối cùng nó được đẩy xuống đồi. Chung cuộc có thể xảy ra trường hợp ống dẫn duy nhất rời một đỉnh u và chưa được bão hòa với luồng sẽ nối với các đỉnh nằm trên cùng cấp với u hoặc phía trên thượng nguồn từ u. Trong trường hợp này, để giải thoát một đỉnh tràn u khỏi luồng thặng dư của nó, ta phải gia tăng chiều cao của nó - một phép toán có tên “nâng” đỉnh. Chiều cao của nó được gia tăng lên thêm một đơn vị so với chiều cao của láng giềng trong số các láng giềng thấp nhất mà nó có một ống dẫn không bão hòa. Do đó, sau khi nâng một đỉnh, ta có ít nhất một ống dẫn ra qua đó có thể đẩy thêm luồng. Chung cuộc, toàn bộ luồng có thể đi qua đến bồn đều đến đó. Không còn gì có thể đến, bởi các ống dẫn tuân thủ các hạn chế dung lượng; lượng luồng qua bất kỳ phần cắt nào vẫn được hạn chế bởi dung lượng của phần cắt. Để luồng trước [preflow] trở thành một luồng “hợp pháp”, thuật toán gửi một phần thặng dư gom lại trong các bồn chứa của các đỉnh tràn trở về nguồn bằng cách tiếp tục nâng các đỉnh lên bên trên chiều cao cố định ïVïcủa nguồn. (Việc vận chuyển phần thặng dư trở về nguồn thực tế được hoàn thành bằng cách khử các luồng gây ra phần thặng dư). Như sẽ thấy, một khi tất cả các bồn chứa xả trống, luồng trước không những là luồng “hợp pháp”, mà còn là một luồng cực đại. Các phép toán cơ bản Từ phần mô tả trên đây, ta thấy thuật toán đẩy luồng trước thực hiện hai phép toán cơ bản: đẩy phần thặng dư của luồng từ một đỉnh đến một trong các láng giềng của nó và nâng một đỉnh. Khả năng áp dụng của các phép toán này tuỳ thuộc vào chiều cao của các đỉnh, mà giờ đây ta định nghĩa một cách chính xác. Cho G = (V, E) là một luồng với nguồn s và bồn t, và cho f là một luồng trước trong G. Một hàm h: V®N là một hàm chiều cao nếu h(s) =ïVï. h(t) = 0, và h(u) ≤ h(v) + 1. với mọi cạnh thặng dư (u,V) E1. Ta lập tức có được bổ đề dưới đây. Bổ đề 26.13 Cho G = (V,E) là một mạng luồng, cho f là một luồng trước trong G, và cho h là một hàm chiều cao trên V. Với hai đỉnh bất kỳ u,v V, nếu h(u) > h(v) + 1, thì (u,v) không phải là một cạnh trong đồ thị thặng dư. Có thể áp dụng phép toán cơ bản PUSH(u,v) nếu u là một đỉnh tràn, cf(u,v) > 0, và h(u) = h(v) + 1. Mã giả dưới đây cập nhật luồng trước f trong một mạng mặc định G = (V,E). Nó mặc nhận rằng các dung lượng được căn cứ vào một hàm thời gian bất biến c và các dụng lượng thặng du cũng có thể được tính toán trong thời gian bất biến đã cho c và f. Luồng thặng dư được lưu trữ tại một đỉnh u được duy trì dưới dạng e[u], và chiều cao của u được duy trì dưới dạng h[u]. Biểu thức d1(u,v) là một biến tạm lưu trữ khối lượng luồng có thể được đẩy từ u đến v. PUSH(u,v) w Áp dụng khi: u tràn, cf[u,v] >0, và h[u] = h[v] + 1. w Hành động: Đẩy df(u,v) = min(e[u],c1(u,v)) đơn vị của luồng từ u đến v. df(u,v) min(e[u],cf(u,v)) f[u,v] f[u,v] + df(u,v) f[v,u] - f[u,v] e[u] e[u] – df(u,v) e[v] e[v] + df(u,v) Mã của PUSH hoạt động như sau. Đỉnh u được mặc nhận có một phần thặng dư dương e[u], và dung lượng thặng dư của (u,v) là dương. Như vậy, ta có thể vận chuyển tới d1(u,v) = min(e[u], c1(u,v)) đơn vị của luồng từ u đến v mà không làm cho e[u] trở thành âm hoặc dung lượng c(u,v) trở thành vượt mức. Giá trị này được tính toán trong dòng 3. Ta dời luồng từ u đến v bằng cách cập nhật f trong các dòng 4-5 và e trong các dòng 6-7. Như vậy, nếu f là một luồng trước trước khi PUSH được gọi, nó vẫn giữ nguyên là một luồng trước sau đấy. Nhận thấy không có gì trong mã của PUSH tùy thuộc vào các chiều cao của u và v, vả lại ngăn cấm triệu gọi nó trừ phi h[u] = h[v] + 1. Như vậy, luồng thặng dư chỉ được đẩy xuống đồi theo một vi phân chiều cao là 1. Theo bổ đề 26.13, không có các cạnh thặng dư tồn tại giữa hai đỉnh có