BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN
MẠNG
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
Giáo viên: TS. Nguyễn Văn Hiệu
Email: nvhieuqt@dut.udn.vn
Nội dung
•Các khái niệm
•Bài toán luồng cực đại
•Thuật toán Ford –Fulkerson
•Minh họa ví dụ
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 2
Các khái niệm
Mạng
Mạng là một đồ thị có
hướng, có trong số G = (V,
E):
1.
∃ ! đỉnh s: deg-(s) = 0,
s - đỉnh phát.
2.
∃ ! đỉnh t: deg+(t) = 0,
t - đỉnh thu.
3.
∀ (i,j) ∈ E: cij >0,
cij - khả năng thông qua
của cung (i,j).
4. Đồ thị liên thông yếu
Ví dụ
Đồ thị có đỉnh phát s và đỉnh thu t
Khả năng thông qua: c s3 =5 ,…
3
5
5
6
3
1
3 6
6
s
2 4
t
5 3
Các khái niệm
Luồng
Cho mạng G và khả năng
thông qua cij ∀ 𝑖,𝑗 ∈
𝐸,𝑠 đỉ𝑛ℎ 𝑝ℎá𝑡,𝑡 đỉ𝑛ℎ 𝑡ℎ𝑢.
Luồng vận tải trên mạng G
là hàm f: E R+ :
1. f ij ≥0, ∀ (𝑖,𝑗) ∈𝐸
f ij :- luồng trên cung (i,j).
2. 0 f ij c ij , ∀ 𝑖,𝑗 ∈𝐸.
3. ∀𝑣∶ v ≠ s, v ≠ t:
f iv
𝑖,𝑣∈𝐸 =
f vj
𝑣,𝑗∈𝐸
Ví dụ
Tập luồng f ij được miêu tả trong
ngoặc màu xanh
4
5 (3)
5 (4)
6 (1)
3 (3)
1 (1)
3 (2) 6 (3)
6 (4)
s
2 4
t
5 3
Các khái niệm
Định lý
Cho {f ij } tập luồng trên
mạng G và s đỉnh phát và t là
đỉnh thu:
f si
𝒔𝒊∈𝑬 =
f it
𝒊,𝒕∈𝑬
Nếu (i,j) ∉𝐸,𝑡ℎì f ij = 0
f ij
𝑖∈𝑉𝑗∈𝑉 =
f ji
𝑖∈𝑉𝑗∈𝑉
Giá trị của luồng
Cho luồng f trên G giá trị
của luồng được định nghĩa
là đại lượng:
Val (f) =
f si
𝒔𝒊∈𝑬
=
f it
𝒊,𝒕∈𝑬
5