Các khái niệm bài toán luồng cực đại trên mạng, bài toán luồng cực đại, thuật toán Ford–Fulkerson, minh họa ví dụ là những nội dung chính trong bài 11 "Bài toán luồng cực đại trên mạng" thuộc bài giảng Toán rời rạc. Mời các bạn cùng tham khảo.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Toán rời rạc: Bài 11 - TS. Nguyễn Văn Hiệu
- BÀI TOÁN LUỒNG CỰC ĐẠI TRÊN
MẠNG
Giáo viên: TS. Nguyễn Văn Hiệu
Email: nvhieuqt@dut.udn.vn
Nguyễn Văn Hiệu, 2012, Discrete Mathematics 1
- 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 Ví dụ
Mạng là một đồ thị có Đồ thị có đỉnh phát s và đỉnh thu t
hướng, có trong số G = (V, 6 4
2
E): 5 6
3
1. ∃ ! đỉnh s: deg-(s) = 0,
s - đỉnh phát. s t
3
2. ∃ ! đỉnh t: deg+(t) = 0, 5
6
t - đỉnh thu. 1
3 5
3. ∀ (i,j) ∈ E: cij >0,
cij - khả năng thông qua Khả năng thông qua: c s3 =5 ,…
của cung (i,j).
4. Đồ thị liên thông yếu
3
- Các khái niệm
Luồng Ví dụ
Cho mạng G và khả năng Tập luồng f ij được miêu tả trong
thông qua cij ∀ 𝑖, 𝑗 ∈ ngoặc màu xanh
𝐸, 𝑠 đỉ𝑛ℎ 𝑝ℎá𝑡, 𝑡 đỉ𝑛ℎ 𝑡ℎ𝑢. 6 (1) 4
2
Luồng vận tải trên mạng G 5 (3) 3 (3) 6 (4)
là hàm f: E R+ :
1. f ij ≥0, ∀ (𝑖, 𝑗) ∈ 𝐸 s t
3 (2)
f ij :- luồng trên cung (i,j). 5 (4) 6 (3)
1 (1)
2. 0 f ij c ij , ∀ 𝑖, 𝑗 ∈ 𝐸. 3 5
3. ∀𝑣 ∶ v ≠ s, v ≠ t:
𝑖,𝑣 ∈𝐸 f iv = 𝑣,𝑗 ∈𝐸 f vj
4
- Các khái niệm
Định lý Giá trị của luồng
Cho {f ij } tập luồng trên Cho luồng f trên G giá trị
mạng G và s đỉnh phát và t là của luồng được định nghĩa
đỉnh thu: là đại lượng:
f si = f it
𝒔𝒊 ∈𝑬 𝒊,𝒕 ∈𝑬 Val (f) = 𝒔𝒊 ∈𝑬 f si
Nếu (i,j) ∉ 𝐸, 𝑡ℎì f ij = 0 = 𝒊,𝒕 ∈𝑬 f it
f ij = f ji
𝑗∈𝑉 𝑖∈𝑉 𝑗∈𝑉 𝑖∈𝑉
5
- Các khái niệm
• Xác định giá trị của luồng f 6(5)
2 4
5(5) 6(6)
• Val(f) = ? 3(1)
3(0)
s t
6(1)
5(2)
1(1)
3 5
6
- Bài toán luồng cực đại
Bài toán Ứng dụng
Cho mạng G với đỉnh phát Xác định cường độ lớn nhất
s, đỉnh thu là t, và khả năng của dòng vận tải giữa hai nút
thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸. của một bản đồ giao thông. Bài
toán luồng cực đại chỉ ra đoạn
Trong số các luồng trên đường đông xe nhất.
mạng G tìm luồng có Hệ thống đường ống dẫn dầu:
giá trị lớn nhất ống – cung, s - tàu chở dầu, t -
bể chứa, còn những điểm nối
giữa các ống là các đỉnh của đồ
thị. cij - diện tích ống. Cần phải
tìm luồng lớn nhất để bơm từ
tàu chở dầu vào bể chứa.
7
- Bài toán luồng cực đại
Bài toán Ý tưởng
Cho mạng G với đỉnh phát Xuất phát từ một luồng nào
s, đỉnh thu là t, và khả năng đó, ta tìm đường đi (không
thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸. định hướng) từ s đến t,
Trong số các luồng trên Tiến hành hiệu chỉnh giá trị
mạng G tìm luồng có luồng trên đường đi sao cho
luồng mới có gia trị lớn
giá trị lớn nhất
hớn.
Nếu không tìm được đi như
vậy thì luồng đó là cực đại.
8
- Bài toán luồng cực đại
Bài toán Ý tưởng
Cho mạng G với đỉnh phát Giả sử
s, đỉnh thu là t, và khả năng P = (s, a, ….,i, j , ….,z, t)
thông qua là cij ,∀ 𝑖, 𝑗 ∈ 𝐸. 𝑖, 𝑗 ∈ 𝐸
(i,j) =
(𝑗, 𝑖) ∈ 𝐸
Trong số các luồng trên Nếu (i,j) là cung trên P thì cung
mạng G tìm luồng có đó cùng hướng với P. Ký hiệu
giá trị lớn nhất P+ là tập cung cùng hướng với P
Nếu (j,i) là cung trên P, thì cung
đó ngược hướng với P.
P- là tập cung ngược hướng với P
9
- Bài toán luồng cực đại
Cơ sở lý luận Cơ sở lý luận
Cho f là luồng trên mạng G Xây dựng luồng f* như sau:
Giả sử đường đi không định
hướng từ s đến t: f ij ∀ 𝑖, 𝑗 ∉ 𝑃
P = (s =a,b,...,i,j,..,z = t) f* = f ij + 𝛿∀ 𝑖, 𝑗 ∈ P+
∀ 𝑖, 𝑗 ∈ P+ : f ij < cij f ij − 𝛿∀ 𝑖, 𝑗 ∈ P−
∀ 𝑖, 𝑗 ∈ P- : 0 < f ij
Đặt 𝛿:= min {x | x ∈ M }
Giá trị luồng f* sẽ lớn hơn
M tập các giá trị cij - f ij với
𝑖, 𝑗 ∈ P+ và các giá trị f ij vớ𝑖 luồng f một đơn vi 𝛿 > 0
𝑖, 𝑗 ∈ P- Val(f*) = val(f) + 𝜹
10
- Bài toán luồng cực đại
Tính đúng đắn Thuật toán Ford- Fullkerson
f* là luồng Tìm luồng cực đại
(s,b) ∈ P+ Input: Mạng G với đỉnh
phát s đỉnh thu t, khả năng
f*sb = fsb + 𝛿 thông qua C = (c ij), (i,j) ∈ E
Val (f*) = 𝒔𝒊 ∈𝑬 f∗ si Ký hiệu s = v0, …..,vn = t
= val(f) + 𝛿
Output: F = (f ij), (i,j) ∈ E
11
- Thuật toán Ford-Fullkerson
Thuật toán
Tìm luồng cực đại Bước 1(khởi tạo luồng ban đầu)
Input:
Mạng G với đỉnh phát s đỉnh fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸
thu t, khả năng thông qua C =
(c ij), (i,j) ∈ E
Ký hiệu s = v0, …..,vn = t Bước 2 (gán nhãn cho đỉnh phát)
Output: s( , ∞)
F = (f ij), (i,j) ∈ E
12
- Thuật toán Ford-Fullkerson
Thuật toán Thuật toán
Bước 1( khởi tạo luồng ban đầu) Bước 3 (kiểm tra nhãn của đỉnh thu )
Nếu t có nhãn ----> bước 6
Nếu t chưa có nhãn--->bước 4
fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸
Bước 4( xác đỉnh đỉnh đánh dấu)
Bước 2( gán nhãn cho đỉnh phát) Xét các đỉnh mang nhãn mà
chưa đánh dấu, chọn v: = vi,
i chỉ số bé nhất.
s( , ∞)
Nếu ∃ vi, thì Đánh dấu v.
Nếu ∄ vi, thì Kết thúc và F là
luồng cực đại.
13
- Thuật toán Ford-Fullkerson
Thuật toán Thuật toán
Bước 5( gán nhãn cho các đỉnh chưa Cung dạng (W,v):
có nhãn, kề với v ) Nếu fWv > 0 , gán nhãn w (v,
x) với
Giả sử nhãn của v (𝛼, Δ)
x = min {Δ, fWv }
Xét cung dạng (v,W) và (W,v) Nếu fWv = 0, không gán
(theo thứ tự (v,v0 ) (v0 ,v), (v,v1 ) nhãn cho w
(v1 ,v), … ) Quay lai bước 3
Cung dạng (v,W): Lưu ý: chỉ xét các W chưa được
Nếu fvW < CvW , gán nhãn w gán nhãn
(v, x) với
x = min {Δ, CvW - fvW }
Nếu fvW = CvW , không gán
nhãn cho w
14
- Thuật toán Ford-Fullkerson
Thuật toán Thuật toán
Bước 6 ( hiệu chỉnh luồng ) Nhận được đường đi P từ s
Giả sử (𝜷, 𝜹) là nhãn của t đến t.
(đỉnh thu). (s =Wk ,Wk-1 ,…,W1,W0 =t )
Đặt W0 = t, W1 = 𝜷
Nếu nhãn của wi là (𝜷`, 𝜹`) Điều chỉnh f trên P:
Đặt Wi+1 = 𝜷`
f ij ∀ 𝑖, 𝑗 ∉ 𝑃
f = f ij + 𝛿 , ∀ 𝑖, 𝑗 ∈ P+
… (tiếp tục)
f ij − 𝛿 , ∀ 𝑖, 𝑗 ∈ P−
Đặt Wk = s (đỉnh phát)
Xóa tất cả các nhãn trên P
và quay lại bước 2
15
- Vi dụ
• Tìm luồng cực đại trên mạng G
2
a b
3 4
2
s t
5 4
c d
2
• Thứ tự các đỉnh: s a b c d t
- Vi dụ
Bước 1(khởi tạo luồng ban
đầu) 2 (0)
fịj = 0, ∀ 𝑖, 𝑗 ∈ 𝐸 3 (0)
a b
4 (0)
2(0)
val (f) = 0 s t
4(0)
5 (0)
c d
2 (0)
- Vi dụ
Bước 2 (gán nhãn cho đỉnh phát)
2 (0)
a b
s( , ∞) 3 (0) 4 (0)
( , ∞) 2(0)
s t
4(0)
5 (0)
c d
2 (0)
- Vi dụ
Bước 3 (kiểm tra nhãn của đỉnh thu )
2 (0)
t chưa có nhãn--->bước 4 a b
3 (0) 4 (0)
( , ∞) 2(0)
s t
4(0)
5 (0)
c d
2 (0)
- Vi dụ
Bước 4( xác đỉnh đỉnh đánh dấu)
Xét các đỉnh mang 2 (0)
a b
nhãn và chưa đánh 3 (0) 4 (0)
dấu,
( , ∞) 2(0)
chọn v: = s. s t
Đánh dấu s (sử dụng màu
4(0)
để đánh dấu) 5 (0)
c d
2 (0)
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
