Xem mẫu
- Luồng trên mạng
V0.1
Trần Vĩnh Đức
HUST
Ngày 20 tháng 11 năm 2019
CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 34
- Tài liệu tham khảo
▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2006.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Bài toán chuyển dầu
ng drawing with capacities drawing with flow flow rep
0 1
0 2
1 3
1 4
2 3
2 4
3 5
4 5
sink
Anatomy of a network-flow problem
CuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 34
- Mô hình bài bài toán
a 2 d
3 10 1 2
s 3 b 1 1 t
4 5
c 5 e
▶ Đồ 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ể.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 34
- Một luồng chuyển 7 đơn vị dầu từ s tới t
luồng khả năng thông qua
a 2/2 d
2/3 0/10 1/1 2/2
s 1/3 b 1/1 0/1 t
4/4 5/5
c 5/5 e
Liệu có cách nào làm tốt hơn?
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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: ∑ ∑
fwu = fuz .
(w,u)∈E (u,z)
Nói cách khác, mạng là bảo toàn (theo luật Kirchhoff).
CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 34
- Luồng và lượng dầu chuyển
luồng khả năng thông qua
a 2/2 d
2/3 0/10 1/1 2/2
s 1/3 b 1/1 0/1 t
4/4 5/5
c 5/5 e
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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) = fsu .
(s,u)∈E
▶ 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 10 / 34
- Ví dụ
Bài toán tìm luồng cực đại trong mạng
a
1 1
s 1 t
1 1
b
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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt
- 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.
CuuDuongThanCong.com https://fb.com/tailieudientucntt 13 / 34
- Khởi tạo Tăng luồng
a a
0/1 0/1 1/1 1/1
s 0/1 t s 0/1 t
0/1 0/1 0/1 0/1
b b
Tăng luồng Luồng cực đại
a a
1/1 1/1 1/1 1/1
s 0/1 t s 0/1 t
1/1 1/1 1/1 1/1
b b
CuuDuongThanCong.com https://fb.com/tailieudientucntt 14 / 34
- Khởi tạo Tăng luồng
a a
0/1 0/1 1/1 0/1
s 0/1 t s 1/1 t
0/1 0/1 0/1 1/1
b b
Hủy luồng trên cạnh a → b Luồng cực đại
a a
1/1 1/1 1/1 1/1
s 0/1 t s 0/1 t
1/1 1/1 1/1 1/1
b b
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 .
CuuDuongThanCong.com https://fb.com/tailieudientucntt 16 / 34
- Đường tăng luồng
Cạnh gốc
Cạnh ngược
▶ e = (u, v) ∈ E
▶ eR = (v, u)
▶ Luồng fe
▶ “Giảm” luồng fe đã gửi
▶ Khả năng ce
Khả năng thông qua còn lại Ví dụ
a
{ 1/1 0/1
ce − fe nếu e ∈ E s 1/1 t
cf (e) =
fe nếu eR ∈ E. 0/1 1/1
b
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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 < ce } ∪ {eR : fe > 0}.
Ví dụ
Mạng G với luồng f và đồ thị tăng luồng Gf tương ứng.
a a
1/1 0/1 1 1
s 1/1 t s 1 t
0/1 1/1 1 1
b b
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 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
CuuDuongThanCong.com https://fb.com/tailieudientucntt 20 / 34
nguon tai.lieu . vn
