Bài giảng Toán rời rạc 2 - Chương 7: Bài toán luồng cực đại trong mạng - Ngô Xuân Bách
Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1
Toán rời rạc 2
Bài toán luồng cực đại trong mạng
Ngô Xuân Bách
Mạng
Định nghĩa 1: Mạng là đồ thị có hướng 퐺 =< 푉, 퐸 >
trong đó:
o Có duy nhất một đỉnh 푠 không có cung đi vào gọi là điểm phát
o Có duy nhất một đỉnh 푡 không có cung đi ra gọi là điểm thu
o Mỗi cung e = (푢, 푣) ∈ 퐸 được gán với một số thực không âm
c e = 푐(푢, 푣) gọi là khả năng thông qua (băng thông) của cung
o Quy ước: Nếu không có cung (푢, 푣) thì khả năng thông qua được
gán bằng 0
2
3
1
3
4
2
1
s
t
4
3
3
3
4
3
Luồng trong mạng
Định nghĩa 2: Giả sử cho mạng 퐺 =< 푉, 퐸 >. Ta gọi luồng 푓
trong mạng 퐺 =< 푉, 퐸 > là ánh xạ 푓: 퐸 → 푅+ gán cho mỗi
cung 푒 = (푢, 푣) ∈ 퐸 một số thực không âm 푓(푒) = 푓(푢, 푣), gọi
là luồng trên cung 푒, thỏa mãn các điều kiện sau:
1) Luồng trên mỗi cung e ∈ 퐸 không vượt quá khả năng thông
qua của nó: 0 ≤ 푓 푒 ≤ 푐 푒
2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: Tổng
luồng trên các cung đi vào đỉnh 푣 bằng tổng luồng trên các
cung đi ra khỏi đỉnh 푣 với mọi 푣 ≠ 푠, 푡:
푢∈Γ (푣) 푓 푢, 푣 = 푢∈Γ (푣) 푓 푣, 푢 ,
−
+
Γ− 푣 = 푢 ∈ 푉: 푢, 푣 ∈ 퐸 , Γ+ 푣 = 푢 ∈ 푉: 푣, 푢 ∈ 퐸
3) Ta gọi giá trị của luồng 푓 là số:
푣푎푙 푓 = 푢∈Γ (푠) 푓 푠, 푢 = 푢∈Γ (푡) 푓 푢, 푡
−
+
4
Ví dụ: Luồng trong mạng
(2)
2
3
1
3
(3)
4
(1)
(1)
2
1
s
t
(1)
풗풂풍(풇) = ퟒ
4
(1)
(3)
3
(1)
3
3
4
5
Bài toán luồng cực đại
Phát biểu bài toán
o Cho mạng 퐺 =< 푉, 퐸 >, hãy tìm luồng 푓∗ trong mạng với giá trị
luồng 푣푎푙 푓∗ lớn nhất
Ví dụ
o Xét đồ thị có hướng tương ứng với hệ thống đường ống dẫn dầu
o Các ống dẫn dầu tương ứng với các cung của đồ thị
o Điểm phát là tàu chở dầu, điểm thu là bể chứa dầu
o Điểm nối giữa các ống tương ứng với các đỉnh của đồ thị
o Khả năng thông qua của các cung tương ứng với tiết diện các ống
o Cần tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể
chứa?
6
Lát cắt
Định nghĩa 3: Lát cắt (푋, 푋∗) là một cách phân hoạch
tập đỉnh 푉 của mạng thành hai tập 푋 và 푋∗, trong đó
푠 ∈ 푋 và 푡 ∈ 푋∗.
o Khả năng thông qua của lát cắt (푋, 푋∗) được định nghĩa:
푐 푋, 푋∗ = 푐(푣, 푤)
∗
푣∈푋,푤∈푋
o Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp
nhất
Bồ đề 1: Giá trị của mọi luồng 푓 trong mạng luôn nhỏ
hơn hoặc bằng khả năng thông qua của lát cắt (푋, 푋∗)
bất kỳ trong mạng: 푣푎푙 푓 ≤ 푐(푋, 푋∗)
o Hệ quả: Giá trị của luồng cực đại trong mạng không vượt quá
khả năng thông qua của lát cắt hẹp nhất trong mạng
8
Ví dụ: Lát cắt
Xét lát cắt 푋, 푋∗ :
- với 푋 = *푆, 3, 4+, 푋∗ = 푡, 1, 2
- c 푋, 푋∗ = 4 + 1 + 2 + 4 = 11
1
s
9
Đồ thị tăng luồng
Giả sử 푓 là một luồng trong mạng 퐺 =< 푉, 퐸 >. Từ mạng
này ta xây dựng đồ thị có trọng số 퐺푓 =< 푉, 퐸푓 >, với tập
các cung 퐸푓 và trọng số trên các cung được xác định như
sau:
o Nếu 푒 = (푣, 푤) ∈ 퐸 với 푓(푣, 푤) = 0, thì (푣, 푤) ∈ 퐸푓 với trọng số
c(푣, 푤)
o Nếu 푒 = (푣, 푤) ∈ 퐸 với 푓(푣, 푤) = 푐(푣, 푤), thì (푤, 푣) ∈ 퐸푓 với trọng
số c(푣, 푤)
o Nếu 푒 = (푣, 푤) ∈ 퐸 với 0 < 푓 푣, 푤 < 푐(푣, 푤), thì (푣, 푤) ∈ 퐸푓 với
trọng số 푐 푣, 푤 − 푓(푣, 푤) và (푤, 푣) ∈ 퐸푓 với trọng số 푓(푣, 푤)
Các cung của 퐺푓 đồng thời là cung của 퐺 được gọi là
cung thuận, các cung còn lại được gọi là cung nghịch. Đồ
thị 퐺푓 được gọi là đồ thị tăng luồng.
10
Ví dụ: Đồ thị tăng luồng
Xét mạng 퐺 với luồng 푓 như sau:
Cung nghịch
2
(2)
3
Cung thuận
2
2
1
1
3
1
1
1
(3)
3
4
3
(1)
3
1
2
1
(1)
s
t
t
s
(1)
1
(1)
3
4
3
3
(3)
1
(1)
2
1
3
4
3
4
Mạng 푮 và luồng 풇
Đồ thị tăng luồng 푮풇
11
Tăng luồng theo đường đi
Xét 푃 = (푠 = 푣0 , 푣1 , 푣2 , … , 푣푘 = 푡) là một đường đi từ 푠
đến 푡 trên đồ thị tăng luồng 퐺푓
Gọi là giá trị nhỏ nhất của các trọng số của các cung
trên đường đi 푃
Xây dựng luồng 푓′ trên mạng 퐺 theo quy tắc sau
, nếu (u,v) P là cung thuận
f (u,v)
, nếu (u,v) P là cung nghịch
, nếu (u,v) P
f '(u,v) f (u,v)
f (u,v)
푓′ là luồng trong mạng và val 푓′ = 푣푎푙 푓 + 훿
Thủ tục biến đổi luồng như trên là tăng luồng dọc theo đường 푃
12
Ví dụ: Tăng luồng theo đường đi
2
(2)
3
2
2
1
1
3
1
1
1
(1)→(2)
(3)
3
3
(1)
3
4
1
= 1
1
2
s
t
s
t
(1)→(0)
1
(1)→(2)
3
3
3
(3)
4
1
(1)→(2)
2
1
3
4
3
4
Đồ thị tăng luồng 푮풇
Mạng 푮 và luồng mới 풇’
푽풂풍(풇’) = ퟓ
13
Đường tăng luồng
Định nghĩa 4: Đường tăng luồng 푓 là một đường đi bất
kỳ từ 푠 đến 푡 trong đồ thị tăng luồng 퐺푓
Định lý 1: Các mệnh đề sau là tương đương:
o 푓 là luồng cực đại trong mạng
o Không tìm được đường tăng luồng 푓
o 푣푎푙(푓) = 푐(푋, 푋∗) với một lát cắt (푋, 푋∗) nào đó
14
Thuật toán Ford-Fulkerson
Bắt đầu từ một luồng 푓 bất kỳ - có thể là luồng 0
Xây dựng đồ thị tăng luồng 퐺푓
Từ 퐺푓, tìm đường tăng luồng 푃
o Nếu không có đường tăng luồng nào thì kết thúc
o Nếu có đường tăng luồng 푃 thì xây dựng luồng mới 푓’ và lặp lại
quá trình trên cho đến khi không tìm thêm được đường tăng
luồng mới
Để tìm đường tăng luồng trong 퐺푓 có thể sử dụng thuật toán tìm kiếm
theo chiều rộng (hoặc theo chiều sâu) bắt đầu từ đỉnh 푠.
15
Một số kết quả lý thuyết
Định lý 2: Luồng cực đại trong mạng bằng khả năng
thông qua của lát cắt hẹp nhất
Định lý 3: Nếu tất cả các khả năng thông qua là các số
nguyên thì luôn tìm được luồng cực đại với luồng trên
các cung là các số nguyên
16
16 trang
25940
Free
Bạn đang xem tài liệu "Bài giảng Toán rời rạc 2 - Chương 7: Bài toán luồng cực đại trong mạng - Ngô Xuân Bách", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_2_chuong_7_bai_toan_luong_cuc_dai_tro.pdf
