MAXIMUM FLOW
•
Flow networks Minh Hòa
•
The Fork-Fulkerson method Hoài Nhân
•
Maximum biparite matching Phú Lộc
•
Push-relabel algorithms Quang Minh
•
The relabel-to-front algorithms Thế Quân
2
FLOW NETWORKS
(MẠNG VẬN TẢI)
Người thực hiện: Nguyễn Thị Minh Hòa
3
Nội dung
•
Mạng vận tải.
•
Luồng.
•
Mạng có nhiều đỉnh phát và nhiều đỉnh thu.
•
Làm việc với nhiều luồng.
Mạng vận tải
4
Mạng vận tải
Định nghĩa

Là đơn đồ thị có hướng G = (V, E)

v4
t
v3
v1
4
14
v2
s
7
20
9
4
12
10
16
13
Đỉnh thu
Đỉnh phát
Mạng vận tải
Ví dụ
6
Cho N = (G = (V, E), c, s, t) là một mạng
vận tải. Một luồng trong N là ánh xạ f: V x
V -> R thỏa mãn các điều kiện sau:
•
Tính ràng buộc về khả năng thông qua
của luồng :
∀u, v ∈ V: ƒ(u, v) ≤ c(u, v).
•
Tính đối xứng:

f f s v
∈
=
∑
, ( , ) 0v V f v v∀ ∈ =
8
•
Cung (u,v) được
gán nhãn như sau:
f(u,v)/c(u,v)
•
|f|=f(s,v1) + f(s,v2)
= 11 + 8 = 19
v2
v4
t
v3
v1
s
8
/
1
3
11/14
4
/
4
7/7
1
5

7
20
9
3
12
8
16
13
Ví dụ sự khác biệt giữa vận chuyển và luồng
Luồng
10
•
Họ không kiểm soát những lộ trình
giữa các thành phố (các đỉnh) và các
khả năng thông qua của các lộ trình.
•
Mục đích: xác định số lượng thùng
lớn nhất p có thể được vận chuyển
mỗi ngày.
•
Họ chỉ quan tâm đến số lượng thùng
p
rời nhà máy và số lượng thùng
p

đến kho mỗi ngày.
Luồng
Ví dụ sự khác biệt giữa vận chuyển và luồng
11
•

Nếu bóng được vận chuyển theo cả hai
hướng giữa hai thành phố thì có thể hủy
bỏ thành một trường hợp, trong đó bóng
được vận chuyển chỉ theo hướng có giá trị
dương.
•
Phương pháp hủy bỏ sẽ phát sinh trong
toàn bộ thuật toán.
Luồng
Ví dụ sự khác biệt giữa vận chuyển và luồng
14
•
Giả sử cung (u, v) tương ứng với một
luồng có giá trị ƒ(u, v).
•
Trong quá trình khai triển thuật toán,
có thể tăng luồng trên cung (v, u)
bằng cách thêm giá trị d.
•
Thao tác đó làm giảm ƒ(u, v) một
lượng d.
Luồng
Ví dụ sự khác biệt giữa vận chuyển và luồng
15
•
Một bài toán luồng cực đại có thể có nhiều
hơn một đỉnh phát và đỉnh thu.
•
Có thể chuyển đổi bài toán luồng cực đại
với nhiều đỉnh phát và đỉnh thu về bài

5
8
2
1
0
1
5
1
3
1
4
7
1
1
3
Ví dụ
Mạng có nhiều đỉnh phát và nhiều
đỉnh thu
17
•
Thêm vào 1 đỉnh
phát giả s và 1 cung
với khả năng thông
qua vô hạn từ s đến
mỗi đỉnh phát si,
•
Thêm 1 đỉnh thu giả
t và 1 cung với khả
năng thông qua vô
hạn từ mỗi đỉnh thu

1
0
1
5
1
3
1
4
7
1
1
3
∞
Ví dụ
Mạng có nhiều đỉnh phát và nhiều
đỉnh thu
18
s1
s5
s4
s3
s2
t3
t2
t1
6
2
0
1
8

s2
t3
t2
t1
6
2
0
1
8
1
2
5
8
2
1
0
1
5
1
3
1
4
7
1
1
3
∞
a)
b)
Chuyển đổi bài toán luồng cực đại với nhiều đỉnh phát và đỉnh thu về bài toán

∈ ∈
= −
∑ ∑
| |
v
f
w
\{ , }: ( , ) (w, )
u V V
v V s t f v u f v
∈ ∈
∀ ∈ =
∑ ∑
( , ) 0
( , )
u V
f v u
f v u
∈
>
∑
20
•
Cho X, Y V, ta
có:
•
Ví dụ:
X={s, v1, v2},
Y={v3, v4, t}
f(X,Y) = f(v1,v3) +

1
/
1
6
X Y
( , ) ( , )
u X v Y
f X Y f u v
∈ ∈
=
∑∑
Ký hiệu
Làm việc với nhiều luồng
21
•
Nếu v V, ta có:
f(X, v) = f(X, {v})
Ví dụ: f(X,v3) = 12 – 4 = 8
•
Tính bảo toàn luồng được viết lại:
ƒ(u, V) = 0, ∀ u ∈V\{s, t}.
∈
Ký hiệu
Làm việc với nhiều luồng
22
•
Cho N là một mạng vận tải và ƒ là một
luồng trong N. Khi đó có các tính chất
sau:


Mạng thặng dư
•
Đường tăng luồng
•
Lát cắt
•
Thuật toán Fork-Fulkerson.
Nội dung
Phương pháp Fork-Fulkerson