Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức
Mô hình bài bài toán Đồ 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ể. 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 2 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.
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
SIMPLY lLL ALL PIPES TO FULL CAPACITY /THERWISE NOT ALL PIPES ARE
FULL BUT OIL mOWS THROUGH THE NETWORK CONTROLLED BY SWITCH
SETTINGS AT THE JUNCTIONS SATISFYING A LOCAL EQUILIBRIUM con-
DITION AT THE JUNCTIONS THE AMOUNT OF OIL mOWING INTO EACH
JUNCTION IS EQUAL TO THE AMOUNT OF OIL mOWING OUT &OR EX-
AMPLE CONSIDER THE NETWORK IN THE DIAGRAM ON THE OPPOSITE
PAGE /PERATORS MIGHT START THE mOW BY OPENING THE SWITCHES
ALONG THE PATH 0->1->3->5 WHICH CAN HANDLE UNITS OF mOW
THEN OPEN SWITCHES ALONG THE PATH 0->2->4->5 TO GET ANOTHER
UNIT OF mOW IN THE NETWORK 3INCE 0->1, 2->4, and 3->5 ARE FULL THERE IS NO DIRECT WAY
TO GET MORE mOW FROM 0 to 5 BUT IF WE CHANGE THE SWITCH AT 1 TO REDIRECT ENOUGH mOW
TO lLL 1->4 WE OPEN UP ENOUGH CAPACITY IN 3->5 TO ALLOW US TO ADD A UNIT OF mOW ON
0->2->3->5 %VEN FOR THIS SIMPLE NETWORK lNDING SWITCH SETTINGS THAT INCREASE THE mOW
IS NOT AN EASY TASK FOR A COMPLICATED NETWORK WE ARE CLEARLY INTERESTED IN THE FOLLOWING
QUESTION 7HAT SWITCH SETTINGS WILL MAXIMIZE THE AMOUNT OF OIL mOWING FROM SOURCE
TO SINK 7E CAN MODEL THIS SITUATION DIRECTLY WITH AN EDGE
WEIGHTED DIGRAPH THAT HAS A
SINGLE SOURCE AND A SINGLE SINK 4HE EDGES IN THE NETWORK CORRESPOND TO THE OIL PIPES
THE VERTICES CORRESPOND TO THE JUNCTIONS WITH SWITCHES THAT CONTROL HOW MUCH OIL GOES
INTO EACH OUTGOING EDGE AND THE WEIGHTS ON THE EDGES CORRESPOND TO THE CAPACITY OF THE
PIPES 7E ASSUME THAT THE EDGES ARE DIRECTED SPECIFYING THAT OIL CAN mOW IN ONLY ONE DI-
RECTION IN EACH PIPE %ACH PIPE HAS A CERTAIN AMOUNT OF mOW WHICH IS LESS THAN OR EQUAL
TO ITS CAPACITY AND EVERY VERTEX SATISlES THE EQUILIBRIUM CONDITION THAT THE mOW IN IS
EQUAL TO THE mOW OUT 4HIS mOW
NETWORK ABSTRACTION IS A USEFUL PROBLEM
SOLVING MODEL
THAT APPLIES DIRECTLY TO A VARIETY OF APPLICATIONS AND INDIRECTLY TO STILL MORE 7E SOME-
TIMES APPEAL TO THE IDEA OF OIL mOWING THROUGH PIPES FOR INTUITIVE SUPPORT OF BASIC IDEAS
Anatomy of a network-!ow 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 !ow !ow representation
Local equilibrium in a !ow 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
