›
›

Bài giảng Toán rời rạc 2 - Chương 6: Bài toán luồng cực đại trong mạng

Download
CHƯƠNG 6. BÀI TOÁN LUꢀNG CꢁC ĐꢂI TRONG MꢂNG  
NꢃI DUNG:  
Giới thiệu bài toán  
Định lý Ford-Fulkerson  
Thuật toán tìm luồng cực đại trong mạng  
Một số bài toán luồng tổng quát  
ꢀng dụng  
 
 
1
6.1 Giới thiệu bài toán  
1. Mꢄng  
Mạng là đồ thị có hướng G = (V, E) thỏa mãn:  
- Có duy nhất đỉnh s không có cung đi vào gọi là điểm phát;  
- Có duy nhất đỉnh t không có cung đi ra gọi là điểm thu;  
- Mỗi cung e = (u, v) E có trọng số không âm c(e) = c(u, v) gọi là khả năng thông qua cꢁa cung  
e.  
2
2. Luꢅng trong mꢄng  
Luồng f trong mạng G = (V, E) là ánh xạ f: E R gán mỗi cung e = (u, v) E một số thực  
không âm f(e) = f(u, v) gọi là luồng trên cung e thỏa mãn các điều kiện:  
(1) Luồng trên mỗi cung e E không vượt quá khả năng thông qua:  
0 ≤ f(e) ≤ c(e);  
(2) Điều kiện cân bằng luồng tại mỗi đỉnh v V, v ≠ s, t: Tổng luồng trên các cung đi vào v bằng  
tổng luồng trên các cung đi ra khỏi v.  
Ký hiệu Γ-(v) = {u V: (u, v) E},  
Γ+(v) = {w V: (v, w) E}.  
-
+
Divf(v) = ∑u Γ (v) f(u, v) - ∑w Γ (v) f(v, w) = 0.  
3
3. Giá trị luꢅng  
+
-
Giá trị cꢁa luồng f là val(f) = ∑v Γ (s) f(s, v) = ∑u Γ (t) f(u, t).  
4. Bài toán luꢅng cꢆc đꢄi  
Input: Mạng G = (V, E);  
Output: Luồng f* có giá trị luồng val(f*) lớn nhất;  
4
Ví dụ về luꢅng:  
- Hệ thống ống dẫn dầu bơm từ tàu chở dầu vào bể chꢂa dầu.  
- Hệ thống các tuyến đường giao thông nối sân bay Nội bài về Hồ Hoàn kiếm.  
5
6.2 Định lý Ford-Fulkerson  
1. Lát cắt:  
Cho X là tập các đỉnh và X* = V\X với s X và t X* (X, X*) gọi là một lát cắt.  
Khả năng thông qua cꢁa lát cắt:  
c(X, X*) = ∑uX, vX* c(u, v).  
Lát cắt có khả năng thông qua nhỏ nhất gọi là lát cắt hẹp nhất.  
Bổ đề 1. Giá trị cꢁa mọi luồng f không vượt quá khả năng thông qua cꢁa lát cắt bất kỳ:  
val(f) ≤ c(X, X*).  
Giá trị luồng cực đại không vượt quá khả năng thông qua cꢁa lát cắt hẹp nhất.  
6
2. Mꢇt sꢈ khái niệm  
- Cho luồng f trong mạng G = (V, E). Xét đồ thị có trọng số Gf như sau:  
(1) Nếu e = (u, v) E với f(u, v) = 0 e = (u, v) Ef với trọng số c(u, v);  
(2) Nếu e = (u, v) E với f(u, v) = c(u, v) e = (v, u) Ef với trọng số f(u, v);  
(3) Nếu e = (u, v) E với 0 < f(u, v) < c(u, v) e = (u, v) Ef với trọng số c(u, v) - f(u, v) và  
e = (v, u) Ef với trọng số f(u, v).  
- Các cung cꢁa Gf cũng là cung cꢁa G gọi là cung thuận.  
- Các cung cꢁa Gf không là cung cꢁa G gọi là cung nghịch.  
- Gf gọi là đồ thị tăng luồng.  
7
- Gọi P = (s = v0, v1, ..., vk = t) là một đường đi từ s đến t trên Gf và là giá trị nhỏ nhất cꢁa các  
trọng số trên các cung thuộc P. Xây dựng luồng f’:  
(1) Nếu (u, v) P là cung thuận thì f’(u, v) = f(u, v) + ;  
(2) Nếu (u, v) P là cung nghịch thì f’(u, v) = f(u, v) - ;  
(3) Nếu (u, v) P thì f’(u, v) = f(u, v).  
val(f*) = val(f) +   
Thꢁ tục tăng luồng dọc theo P.  
- Mọi đường đi từ s đến t trên Gf là đường tăng luồng f.  
8
Định lý Ford-Fullkerson  
Các mệnh đề sau là tương đương:  
(1) f là luồng cực đại trong mạng;  
(2) Không tìm được đường tăng luồng;  
(3) Giá trị luồng f bằng khả năng thông qua cꢁa một lát cắt nào đó: val(f) = c(X, X*).  
9
6.3 Thuật toán tìm luꢅng cꢆc đꢄi trong mꢄng  
Input: Mạng G = (V, E) cho bởi ma trận trọng số c[i][j];  
Đỉnh phát s; Đỉnh thu t;  
Output: Luồng cực đại f; giá trị luồng val(f);  
10  
Thuật toán Max_Flow {  
// Khởi tạo  
for u V  
for v V {f(u, v) = 0; }  
//Lặp  
Stop = 0;  
while (!Stop) {  
if (Tìm được được đường tăng luồng P) {  
<Tăng luồng f dọc theo P>;  
}
else Stop = 1;  
}
return (f, val(f));  
}
11  
void FindPath(){  
int cq, dq, u, v;  
int Stop = 1;  
for (u = 1; u <= n; u++) vs[u] = 0;  
cq = 1; dq = 1; q[cq] = s; vs[s] = 1; p[s] = 0; d[s] = 10000;  
while (dq <= cq){  
u = q[dq]; dq++;  
for (v = 1; v <= n; v++)  
if (!vs[v]) {  
if (c[u][v] > 0 && fl[u][v] < c[u][v]) {  
p[v] = u; d[v] = Min(d[u], c[u][v] - fl[u][v]);  
cq++; q[cq] = v; vs[v] = 1;  
if (v = t) return;  
}
if (c[v][u] > 0 && fl[v][u] > 0) {  
p[v] = -u; d[v] = Min(d[u], fl[v][u]); cq++; q[cq] = v; vs[v] = 1;  
if (v = t) return;  
}
}
}
Stop = 0;  
}
12  
13  
6.4 Mꢇt sꢈ bài toán luꢅng tổng quát  
1. Mꢄng có nhiều điểm phát, nhiều điểm thu  
Xét mạng G có p điểm phát s1, …, sp và q điểm thu t1, …, tq. Một luồng có thể xuất phát từ một  
đỉnh phát bất kỳ đến một trong các đỉnh thu và được định nghĩa tương tự như trên.  
- Bài toán luồng cực đại trên G được đưa về bài toán trên bằng cách bổ sung 1 đỉnh phát giả s và  
1 đỉnh thu giả t.  
- Từ đỉnh phát giả s có cạnh nối đến các đỉnh phát s1, …, sp với khả năng thông qua là vô cùng  
lớn.  
- Từ các đỉnh thu t1, …, tq có cạnh nối đến đỉnh thu giả t với khả năng thông qua là vô cùng lớn.  
14  
Thuật toán tìm luꢅng cꢆc đꢄi:  
- Tìm luồng cực đại f* trên mạng G {s, t} bằng thuật toán Max_Flow;  
- Bỏ hai đỉnh giả s và t có luồng cực đại f* trên G với val(f*).  
15  
2. Bài toán với khả năng thông qua cꢉa đỉnh và cꢄnh  
Xét mạng G.  
Ngoài khả năng thông qua c[u][v] trên cạnh (u, v) E, còn có khả năng thông qua cꢁa đỉnh v  
là số nguyên không âm d[v], v V.  
Luồng f trên mạng G phải thỏa mãn thêm điều kiện: tổng luồng đi vào đỉnh v không vượt quá  
d[v].  
Yêu cầu: Tìm luồng cực đại giữa s và t.  
16  
Thuật toán:  
(1) Xây dựng mạng G’sao cho mỗi v G tương ꢂng hai đỉnh v+, v- trong G’ với khả năng  
thông qua:  
c[u-][v+] = c[u][v]; c[v-][w+] = c[v][w]; c[v-][v+] = d[v];  
(2) Tìm luồng cực đại f* trên G’;  
(3) Xuất f* trên G và val(f*);  
17  
3. Mꢄng có khả năng thông qua bị chặn hai phía  
Xét mạng G.  
Khả năng thông qua trên cạnh (u, v) E có cận trên là c[u][v] và cận dưới là d[u][v].  
Luồng f trên mạng G phải thỏa mãn thêm điều kiện:  
d[u][v] ≤ f[u][v] ≤ c[u][v].  
Yêu cầu: Tìm luồng cực đại giữa s và t.  
18  
Thuật toán:  
(1) Đưa vào hai đỉnh phát giả su và thu giả tu;  
Xây dựng mạng Gu sao cho mỗi cung (u, v) có d[u][v] ≠ 0 tương ꢂng hai cung (su, v) và (u, tu)  
với khả năng thông qua d[u][v]; khả năng thông qua cꢁa (u, v) là c[u][v] – d[u][v];  
(2) d* = ∑(u, v) E d[u][v];  
(3) Tìm luồng cực đại f* trên Gu;  
(4) Nếu val(f*) = d* Xuất luồng f tương thích f* trên G và val(f);  
19  
6.5 ꢊng dụng  
1. Bꢇ ghép cꢆc đꢄi  
Cho đồ thị hai phía G với V = X Y, X Y = ;  
Bộ ghép M trên G là các cặp (x, f(x)) với đơn ánh f: X Y.  
Yêu cầu: Tìm M có số lượng phần tử lớn nhất.  
Ví dụ:  
1) Bài toán phân việc;  
2) Bài toán đám cưới vùng quê.  
20  
Tải về để xem bản đầy đủ
pdf 23 trang myanh 35021 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc 2 - Chương 6: Bài toán luồng cực đại trong mạng", để 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:

  • pdfbai_giang_toan_roi_rac_2_chuong_6_bai_toan_luong_cuc_dai_tro.pdf