Bài giảng Luồng trên mạng V0.1 - Toán rời rạc thầy Trần Vĩnh Đức | Trường Đại học Bách khoa Hà Nội

rong lý thuyết đồ thị, một luồng trên mạng, thường được gọi tắt là luồng một cách gán các luồng (dòng chảy) cho các cung của một đồ thị có hướng.  Tài liệu được sưu tầm, giúp bạn ôn tập và đạt kết quả cao. Mời bạn đọc đón xem!

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 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
887
Network-flow algorithms


        con-

 -



0->1->3->5
0->2->4->5
0->1, 2->4, and 3->5
0 to 51
1->43->5
0->2->3->5






-



-

Anatomy of a network-ow problem
flow value
associated
with
each edge
capacities
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
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ị hướng biểu diễn mạng đường ống, dầu thể được
chuyển qua đường ống y
Mục tiêu chuyển dầu từ s đến t, nhiều nhất 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ách nào làm tốt hơn?
6 / 34
Mạng
Định nghĩa
Một mạng được định nghĩa b G = (V, E, s, t, c), đây
(V, E) một đồ thị hướng;
s, t V, gọi đỉnh nguồn đỉnh đích;
c 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 khả năng thông qua.
Bài toán
Ta muốn chuyển nhiều dầu nhất thể từ s tới t 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 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
e
với mọi e E
2. Với mọi đỉnh u, ngoại trừ s t, tổng luồng vào u bằng tổng
luồng ra khỏi u:
(w,u)E
f
wu
=
(u,z)
f
uz
.
Nói cách khác, mạng bảo toàn (theo luật Kirchho).
8 / 34
Luồng 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 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
f
su
.
Mục đích của chúng ta tìm được luồng 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 một bài toán quy hoạch tuyến tính.
10 / 34
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 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 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 tăng
luồng nhiều nhất 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) một trong hai kiểu
(u, v) E khả năng thông qua c
uv
vẫn chưa đầy. Khi đó
f
uv
thể tăng thêm nhiều nhất
c
uv
f
uv
.
(v, u) E một luồng qua đó, tức f
vu
> 0. Khi đó ta
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
e = (u, v) E
Luồng f
e
Khả năng c
e
Cạnh ngược
e
R
= (v, u)
“Giảm” luồng f
e
đã gửi
Khả năng thông qua còn lại
c
f
(e) =
{
c
e
f
e
nếu e E
f
e
nếu e
R
E.
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 đồ thị
G
f
= (V, E
f
, c
f
) với
E
f
= {e : f
e
< c
e
} {e
R
: f
e
> 0}.
dụ
Mạng G với luồng f đồ thị tăng luồng G
f
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 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
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 f(e
R
) = f(e
R
) δ
return f
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 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
| 1/42

Preview text:

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 Network-flow algorithms 887 inflow equals outflow at every vertex con- (except the source and the sink) -
Local equilibrium in a flow network 0->1->3->5 0->2->4->5 0->1, 2->4, and 3->5 0 to 5 1 1->4 3->5 0->2->3->5 - ptg12441863 - Bài toán chuyển dầu tinyFN.txt standard drawing drawing with capacities drawing with flow flow representation source V 0 1 2.0 2.0 6 E 0 2 3.0 1.0 8 1 3 3.0 2.0 0 1 2.0 1 4 1.0 0.0 0 2 3.0 2 3 1.0 0.0 1 3 3.0 2 4 1.0 1.0 1 4 1.0 3 5 2.0 2.0 2 3 1.0 4 5 3.0 1.0 2 4 1.0 3 5 2.0 flow value 4 5 3.0 associated with each edge capacities sink
Anatomy of a network-flow problem 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ể. 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? 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 đỉ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 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). 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 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. 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 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 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 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 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 Cạnh ngược
e = (u, v) ∈ EeR = (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 c s 1/1 t cf e − fe nếu e ∈ E (e) = f 0/1 e nếu eR ∈ E. 1/1 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ị
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 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
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 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