Giáo trình Toán rời rạc - Bài 21: Luồng trên mạng

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

4 / 34

Mô hình bài bài toán

a

2

1

d

1

10

3

4

2

5

s

t

b

c

e

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

khả năng thông qua

luồng

2/2

1/1

a

d

0/1

e

0/10

2/3

1/3

4/4

2/2

s

t

b

5/5

c

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ị c_e> 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ố f_e, sao cho:

1. Không vi phạm khả năng thông qua:

0 ≤ f_e≤ c_evớ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:

∑

f_wu

=

f_uz.

(w,u)∈E

(u,z)

Nói cách khác, mạng là bảo toàn (theo luật Kirchhoﬀ).

8 / 34

Luồng và lượng dầu chuyển

khả năng thông qua

luồng

2/2

1/1

a

d

0/10

2/3

1/3

4/4

2/2

s

0/1

5/5

e

t

b

5/5

c

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) =

f_su.

(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ị

{f_e: 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

a

1

s

t

1

b

tương đương với bài toán quy hoạch tuyến tính

max f_sa+ f_sb

0 ≤ f_sa, f_sb, f_ab, f_at, f_bt≤ 1

f_sa= f_at+ f_ab

f_sb+ f_ab= f_bt

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

Tăng luồng

a

0/1

1/1

0/1

s

t

0/1

b

Tăng luồng

Luồng cực đại

a

1/1

0/1

s

1/1

b

14 / 34

Khởi tạo

Tăng luồng

a

0/1

1/1

0/1

1/1

0/1

1/1

s

t

0/1

b

Hủy luồng trên cạnh a → b

Luồng cực đại

a

1/1

0/1

s

t

1/1

b

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 c_uvvẫn chưa đầy. Khi đó

f_uvcó thể tăng thêm nhiều nhất là

c_uv− f_uv.

▶

(v, u) ∈ E và có một luồng qua đó, tức là f_vu> 0. Khi đó ta

có thể giảm một phần hoặc toàn bộ f_vu.

16 / 34

Đường tăng luồng

Cạnh gốc

Cạnh ngược

▶

e = (u, v) ∈ E

e^R= (v, u)

▶

Luồng f_e

▶

“Giảm” luồng f_eđã gửi

▶

Khả năng c_e

Ví dụ

Khả năng thông qua còn lại

a

1/1

0/1

1/1

{

1/1

c_e− f_enếu e ∈ E

c^f(e) =

s

t

f_e

nếu e^R∈ E.

b

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ị

G^f= (V, E_f, c^f) với

E_f= {e : f_e< c_e} ∪ {e^R: f_e> 0}.

Ví dụ

Mạng G với luồng f và đồ thị tăng luồng G^ftương ứng.

a

1/1

0/1

1/1

1

1/1

1

s

t

b

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 G^f.

▶

Khả năng thông qua của đường tăng luồng P là

c^f(P) = min{c^f(e) : e ∈ P}

Augment(f, c, P)

δ = c^f(P)

foreach cạnh e ∈ P:

if (e ∈ E) f_e= f_e+ δ

else

return f

f(e^R) = f(e^R) − δ

19 / 34

Thuật toán Ford-Fulkerson

Ford-Fulkerson (G)

foreach cạnh e ∈ E: f_e= 0

G^f= đồ thị tăng luồng của G và f

while (còn đường tăng luồng P trong G^f):

f = Augment(f, c, P)

Cập nhật G^f

return f

20 / 34

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