Xem mẫu
- TRƯỜNG ĐẠI HỌC TÂY ĐÔ
KHOA: KỸ THUẬT-CÔNG NGHỆ
LỚP: CAO ĐẲNG TIN HỌC 4
NHÓM: 14
Thành Viên:
1. Nguyễn Trường An
2. Nguyễn Nhật Minh
3. Nguyễn Hoàng Đăng
4. Cái Văn Nam
5. Võ Trường Giang
BÁO CÁO BÀI TOÁN LUỒNG CỰC
ĐẠI TRÊN MẠNG
Nội Dung Chính Gồm 2 Phần:
Phần 1: TRÊN PƯƠNG DIỆN CỦA MÔN TOÁN RỜI
RẠC
1. Luồng vận tải:
1.1. Định nghĩa: Mạng vận tải là một đồ thị có hướng, không
có khuyên và có trọng số G=(V,E) với V={v 0,
v1, ...,vn}thoảmãn:
1) Mỗi cung e ∈ E có trọng số m(e) là một số nguyên không
âm và được gọi là khả năng thông qua của cung e.
2) Có một và chỉ một đỉnh v0 không có cung đi vào, tức là
degt(v0)=0. Đỉnh v0 được gọi là lối vào hay đỉnh phát của
mạng.
3) Có một và chỉ một đỉnh vn không có cung đi ra, tức là
dego(vn)=0. Đỉnh vn được gọi là lối ra hay đỉnh thu của mạng.
1.2. Định nghĩa: Để định lượng khai thác, tức là xác định
lượng vật chất chuyển qua mạng vận tải G=(V,E), người ta
đưa ra khái niệm luồng vận tải và nó được định nghĩa như
sau.
1
- TRƯỜNG ĐẠI HỌC TÂY ĐÔ
KHOA: KỸ THUẬT-CÔNG NGHỆ
LỚP: CAO ĐẲNG TIN HỌC 4
NHÓM: 14
Thành Viên:
1. Nguyễn Trường An
2. Nguyễn Nhật Minh
3. Nguyễn Hoàng Đăng
4. Cái Văn Nam
5. Võ Trường Giang
2
- Hàm ϕ xác định trên tập cung E và nhận giá trị nguyên được
gọi là luồng vận tải của mạng vận tải G nếu ϕ thoả mãn:
1) ϕ (e) ≥ 0, ∀ e ∈ E.
∑ ϕ (e) = ∑ ϕ (e) , ∀ v ∈ V, v≠ v0, v≠ vn. Ở đây, Γ − (v)={e∈ E |
2) e∈Γ + ( v )
e∈Γ − (v )
e có đỉnh cuối là v}, Γ + (v)={e∈ E | e có đỉnh đầu là v}.
3) ϕ (e) ≤ m(e), ∀ e ∈ E.
Ta xem ϕ (e) như là lượng hàng chuyển trên cung
e=(u,v) từ đỉnh u đến đỉnh v và không vượt quá khả năng
thông qua của cung này. Ngoài ra, từ điều kiện 2) ta thấy
rằng nếu v không phải là lối vào v0 hay lối ra vn, thì lượng
hàng chuyển tới v bằng lượng hàng chuyển khỏi v.
Từ quan hệ 2) suy ra:
∑ ϕ (e) = ∑ ϕ (e) =: ϕ v
4) .
e∈Γ − (vn )
e∈Γ + ( v0 ) n
Đại lượng ϕ vn (ta còn ký hiệu là ϕ n ) được gọi là luồng
qua mạng, hay cường độ luồng tại điểm vn hay giá trị của
luồng ϕ . Bài toán đặt ra ở đây là tìm ϕ để ϕ vn đạt giá trị lớn
nhất, tức là tìm giá trị lớn nhất của luồng.
1.3. Định nghĩa: Cho mạng vận tải G=(V,E) và A ⊂ V. Ký
hiệu
Γ − (A)={(u,v)∈ E | v∈ A, u∉ A}, Γ + (A)={(u,v) ∈ E | u∈ A, v∉ A}.
Đối với tập cung M tuỳ ý, đại lượng ϕ (M)= e∑
ϕ (e)
được
∈M
gọi là luồng của tập cung M.
Từ điều kiện 2) dễ dàng suy ra hệ quả sau.
1.4. Hệ quả: Cho ϕ là luồng của mạng vận tải G=(V,E) và A
⊂ V \{v0,vn}. Khi đó:
ϕ ( Γ − (A))=ϕ ( Γ + (A)).
2. Bài toán luồng cực đại:
Cho mạng vận tải G=(V,E). Hãy tìm luồng ϕ để đạt ϕ vn
max trên mạng G.
Nguyên lý của các thuật toán giải bài toán tìm luồng
cực đại là như sau.
3
- 2.1. Định nghĩa: Cho A ⊂ V là tập con tuỳ ý không chứa lối
vào v0 và chứa lối ra vn. Tập Γ − (A) được gọi là một thiết
diện của mạng vận tải G.
∑ m( e)
Đại lượng m( Γ − (A))= e∈Γ− ( A) được gọi là khả năng
thông qua của thiết diện Γ − (A).
Từ định nghĩa thiết diện và khả năng thông qua của nó
ta nhận thấy rằng: mỗi đơn vị hàng hoá được chuyển từ v0
đến vn ít nhất cũng phải một lần qua một cung nào đó của
thiết diện Γ − (A). Vì vậy, dù luồng ϕ và thiết diện Γ − (A) như
thế nào đi nữa cũng vẫn thoả mãn quan hệ:
ϕ n ≤ m( Γ − (A)).
Do đó, nếu đối với luồng ϕ và thiết diện W mà có:
ϕ n = m(W)
thì chắc chắn rằng luồng ϕ đạt giá trị lớn nhất và thiết
diện W có khả năng thông qua nhỏ nhất.
2.2. Định nghĩa: Cung e trong mạng vận tải G với luồng vận
tải ϕ được goi là cung bão hoà nếu ϕ (e)=m(e).
Luồng ϕ của mạng vận tải G được gọi là luồng đầy
nếu mỗi đường đi từ v0 đến vn đều chứa ít nhất một cung
bão hoà.
Từ định nghĩa trên ta thấy rằng, nếu luồng ϕ trong
mạng vận tải G chưa đầy thì nhất định tìm được đường đi
α từ lối vào v0 đến lối ra vn không chứa cung bão hoà. Khi đó
ta nâng luồng ϕ thành ϕ ’ như sau:
ϕ (e) + 1 khi e∈α ,
ϕ ' (e ) =
ϕ (e) khi e∉α .
Khi đó ϕ ’ cũng là một luồng, mà giá trị của nó là:
ϕ ’n = ϕ n +1 > ϕ n.
Như vậy, đối với mỗi luồng không đầy ta có thể nâng
giá trị của nó và nâng cho tới khi nhận được một luồng đầy.
Tuy vậy, thực tế cho thấy rằng có thể có một luồng
đầy, nhưng vẫn chưa đạt tới giá trị cực đại. Bởi vậy, cần
4
- phải dùng thuật toán Ford-Fulkerson để tìm giá trị cực đại
của luồng.
2.3. Thuật toán Ford-Fulkerson:
Để tìm luồng cực đại của mạng vận tải G, ta xuất phát từ
luồng tuỳ ý ϕ của G, rồi nâng luồng lên đầy, sau đó áp dụng
thuật toán Ford-Fulkerson hoặc ta có thể áp dụng thuật toán
Ford-Fulkerson trực tiếp đối với luồng ϕ .
Thuật toán gồm 3 bước:
Bước 1 (đánh dấu ở đỉnh của mạng): Lối vào v0 được đánh
dấu bằng 0.
1) Nếu đỉnh vi đã được đánh dấu thì ta dùng chỉ số +i để
đánh dấu cho mọi đỉnh y chưa được đánh dấu mà (vi,y)∈ E
và cung này chưa bão hoà (ϕ (vi,y)0).
Nếu với phương pháp này ta đánh dấu được tới lối ra
vn thì trong G tồn tại giữa v0 và vn một xích α , mọi đỉnh đều
khác nhau và được đánh dấu theo chỉ số của đỉnh liền trước
nó (chỉ sai khác nhau về dấu). Khi đó chắc chắn ta nâng
được giá trị của luồng.
Bước 2 (nâng giá trị của luồng): Để nâng giá trị của luồng ϕ ,
ta đặt:
ϕ ’(e) = ϕ (e), nếu e∉α ,
ϕ ’(e) = ϕ (e)+1, nếu e∈α được định hướng theo chiều của
xích α đi từ vo đến vn,
ϕ ’(e) = ϕ (e)−1, nếu e∈α được định hướng ngược với chiều
của xích α đi từ vo đến vn.
+i
y vj -j
e
z
vi
5
0 v0 vn
- ϕ ’ thoả mãn các điều kiện về luồng, nên ϕ ’ là một luồng và
ta có:
ϕ ’n = ϕ n+1.
Như vậy, ta đã nâng được luồng lên một đơn vị.
Sau đó lặp lại một vòng mới. Vì khả năng thông qua
của các cung đều hữu hạn, nên quá trình phải dừng lại sau
một số hữu hạn bước.
Bước 3: Nếu với luồng ϕ 0 bằng phương pháp trên ta không
thể nâng giá trị của luồng lên nữa, nghĩa là ta không thể
đánh dấu được đỉnh vn, thì ta nói rằng quá trình nâng luồng
kết thúc và ϕ 0 đã đạt giá trị cực đại, đồng thời gọi ϕ 0 là
luồng kết thúc.
Khi mạng vận tải G=(V,E) đạt tới luồng ϕ 0, thì bước
tiếp theo ta không thể đánh dấu được tới lối ra vn. Trên cơ
sở hiện trạng được đánh dấu tại bước này, ta sẽ chứng
minh rằng luồng ϕ 0 đã đạt được giá trị cực đại.
2.4. Bổ đề: Cho luồng ϕ của mạng vận tải G=(V,E) và A ⊂
V, chứa lối ra vn và không chứa lối vào v0. Khi đó:
ϕ vn = ϕ (Γ − ( A)) − ϕ (Γ + ( A)) .
Chứng minh: Đặt A1=A \{vn}. Theo Hệ quả 1.4, ta có:
ϕ (Γ − ( A1 )) = ϕ (Γ + ( A1 )) (1).
Đặt C1={(a,vn)∈ E | a∉ A}. Khi đó Γ − ( A) = Γ − ( A1 ) ∪ C1 và Γ − ( A1 ) ∩
C1 = ∅ , nên
6
- ϕ (Γ − ( A)) = ϕ (Γ − ( A1 )) + ϕ (C1) (2).
Đặt C2={(b,vn)∈ E | b∈ A1}. Khi đó C2={(b,vn)∈ E | b∈ A},
Γ + ( A1 ) = Γ + ( A) ∪ C2 và Γ + ( A) ∩ C2 = ∅ , nên
ϕ (Γ + ( A)) = ϕ (Γ + ( A1 )) − ϕ (C2) (3).
Ngoài ra, Γ − (v n ) = C1∪ C2 và C1∩ C2 = ∅ , nên
ϕ vn = ϕ (Γ − (v n )) = ϕ (C1)+ ϕ (C2) (4).
Từ (1), (2), (3) và (4), ta có:
ϕ vn = ϕ (Γ − ( A)) − ϕ (Γ + ( A)) .
2.5. Định lý (Ford-Fulkerson): Trong mạng vận tải G=(V,E),
giá trị lớn nhất của luồng bằng khả năng thông qua nhỏ
nhất của thiết diện, nghĩa là
m(Γ − ( A)) .
max ϕ vn = min
ϕ A⊂V ,v0∉A,vn∈A
Chứng minh: Giả sử trong mạng vận tải G, ϕ 0 là luồng cuối
cùng, mà sau đó bằng phương pháp đánh dấu của thuật toán
Ford-Fulkerson không đạt tới lối ra vn. Trên cơ sở hiện
trạng được đánh dấu lần cuối cùng này, ta dùng B để ký
hiệu tập gồm các đỉnh của G không được đánh dấu. Khi đó
v0∉ B, vn∈ B. Do đó Γ − (B) là một thiết diện của mạng vận tải
G và theo Bổ đề 2.4, ta có:
ϕ v = ϕ 0 (Γ − ( B)) − ϕ 0 (Γ + ( B )) (1).
0
n
Đối với mỗi cung e=(u,v)∈ Γ − (B) thì u∉ B và v∈ B, tức là u
được đánh dấu và v không được đánh dấu, nên theo nguyên
tắc đánh dấu thứ nhất, e đã là cung bão hoà:
ϕ 0(e) = m(e).
∑ ϕ 0 (e) = ∑ m(e) = m(Γ − ( B))
ϕ 0 (Γ − ( B )) =
Do đó, (2).
e∈Γ − ( B ) e∈Γ − ( B )
Đối với mỗi cung e=(s,t)∈ Γ + (B) thì s∈ B và t∉ B, tức là s
không được đánh dấu và t được đánh dấu, nên theo nguyên
tắc đánh dấu thứ hai:
ϕ 0(e) = 0.
∑ ϕ 0 (e) = 0
ϕ 0 (Γ + ( B)) =
Do đó, (3).
e∈Γ + ( B )
7
- Từ (1), (2) và (3) ta suy ra:
ϕ v = m(Γ − ( B)) .
0
n
0
ϕv
Vì vậy, là giá trị lớn nhất của luồng đạt được, còn
n
m( Γ − (B)) là giá trị nhỏ nhất trong các khả năng thông qua
của các thiết diện thuộc mạng vận tải G.
Thí dụ 3: Cho mạng vận tải như hình dưới đây với khả năng
thông qua được đặt trong khuyên tròn, luồng được ghi trên
các cung. Tìm luồng cực đại của mạng này.
Luồng ϕ có đường đi (v0,v4), (v4,v6), (v6,v8) gồm các cung
chưa bão hoà nên nó chưa đầy. Do đó có thể nâng luồng của
các cung này lên một đơn vị, để được ϕ 1.
Do mỗi đường xuất phát từ v0 đến v8 đều chứa ít nhất
một cung bão hoà, nên luồng ϕ 1 là luồng đầy. Song nó chưa
phải là luồng cực đại.
Áp dụng thuật toán Ford-Fulkerson để nâng luồng ϕ 1.
4 3
v1 v5
4
4 6
3 6
4
7
8 4 2
v2
55
12 11
v0 v6 v8
5 5 3
4
8 v3 42 6
6
9
2
4
4
4
v4 v7
ϕ
8
- 4 3
v1 v5
4
4 6
3 6
4
7
8 4 2
v2
55
12 12
v0 v6 v8
5 5 3
−6 4
+4 +7
8 v3 42 6
7
9
4
4
4
v4 v7
+0 ϕ1 +3
Xét xích α =(v0, v4, v6, v3, v7, v8). Quá trình đánh dấu từ v0 đến
v8 để có thể nâng luồng ϕ 1 lên một đơn vị bằng cách biến
đổi luồng tại các cung thuộc xích α được đánh dấu. Sau đó
ta có luồng ϕ 2.
−6
+4
3−1
v6 v3 2+1
3+1
+0 +3
v4 v7
6+1
7+1
0 v0 v8 +7
xích α
Xét xích β =(v0, v1, v5, v2, v6, v3, v7, v8). Quá trình đánh dấu từ v0
đến v8 để có thể nâng luồng ϕ 2 lên một đơn vị bằng cách
biến đổi luồng tại các cung thuộc xích β được đánh dấu.
Sau đó ta có luồng ϕ 3.
9
- +0 +1
4 3
v1 v5
4
4 6
3 6
4
7 −5
8 4 2
v2
55 +2 12 12
v0 v6 v8
5 5 2
−6 4
0 +7
8 v3 43 7
8
9
4
4
4
4
v4 v7
ϕ 2
+3
−5 2+1 +2
3−1 v2 v6
+1 2−1 −6
v5
v3
3+1 3+1
+0
v1 +3
v7
7+1 7+1
xích β
0 v0 v8 +7
4 4
v1 v5
4
4 6
2 6
4
8
8 4 3
v2
55
12 12
v0 v6 v8
5 5 1
4
8 v3 44 8
8
9
4
4
4
4
v4 v7
ϕ 3
Tiếp theo ta chỉ có thể đánh dấu được đỉnh v0 nên quá trình
nâng luồng kết thúc và ta được giá trị của luồng cực đại là:
3
ϕ v = 6+12+8 = 26.
8
10
- Mặt khác, thiết diện nhỏ nhất Γ − (B) với B={v1, v2, ..., v8} là
Γ − (B)={(v 0,v1), (v0,v2), (v0,v3), (v0,v4)}.
Phần 2: TRÊN PHƯƠNG DIỆN CỦA MÔN CẤU TRÚC
DỮ LIỆU
1. Đặt vấn đề
Bài toán luồng cực đại trên mạng là một trong số những bài
toán tối ưu trên đồ thị tìm được những ứng dụng rộng rãi trong
thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp.
Bài toán được đề xuất và giải quyết bởi hai nhà toán học Mỹ
Ford và Fulkerson vào đầu những năm 1950 và ngày càng được
các nhà khoa học quan tâm nghiên cứu. Hiện nay, mô hình xử lý
song song đã và đang phát triển mạnh mẽ giải quyết những vấn
đề bế tắc mà mô hình xử lý tuần tự gặp phải như vấn đề thời
gian thực hiện chương trình, tốc độ xử lý, khả năng lưu trữ của
bộ nhớ, xử lý dữ liệu với quy mô lớn....
Trong bối cảnh đó, thuật toán tìm luồng cực đại cần được phát
triển theo hướng song song nhằm phát huy sức mạnh của bài
toán.
2. Bài toán tìm luồng cực đại trên mạng
Cho mạng G(V,E,C), nguồn a, đích z. Trong số các luồng trên
mạng G, hãy tìm luồng có giá trị lớn nhất.
3. Ý tưởng thuật toán
Dựa trên thuật toán truyền thống và thuật toán hoán chuyển
nguồn đích, xây dựng thuật toán song song tìm luồng cực đại. Ý
tưởng của phương pháp này là thay vì trong thuật toán truyền
thống dùng một bộ vi xử lý thực hiện công việc tuần tự từ đỉnh
nguồn đến đỉnh đích. Trong thuật toán song song sử dụng hai bộ
vi xử lý thực hiện công việc song song, vi xử lý 1 xuất phát từ
đỉnh nguồn, vi xử lý 2 xuất phát từ đỉnh đích. Hai vi xử lý trong
quá trình tìm đường tăng luồng sẽ gặp nhau ở đỉnh trung gian t
nào đó, công việc
11
- tiếp theo vi xử lý 1 xử lý công việc từ đỉnh t đến nút nguồn, vi xử
lý 2 xử lý công việc từ đỉnh t đến nút đích.
4. Xây dựng thuật toán song song
Đầu vào: Mạng G = (V , E ) với nguồn a, đích z, khả năng thông
qua: C = ( cij ) , ( i, j ) ∈ G .
Các đỉnh trong G được sắp xếp theo thứ tự nào đó.
Đầu ra: Luồng cực đại F = ( f ij ), ( i, j ) ∈ G .
Các bước
Bước1: Khởi tạo
P1:
Luồng xuất phát: For i:= 1 to (n div 2) do
For j:= 1 to n do if cij>0 then fij=0
Đặt nhãn tiến (↑) cho đỉnh nguồn: a( ↑, φ , ∞ )
Tạo lập tập S gồm các đỉnh đã có nhãn tiến nhưng chưa
được dùng để sinh nhãn tiến: S := { a} ; khởi gán điều kiện kết
thúc Stop:= False;
P2:
Luồng xuất phát: For i:= (n div 2)+1 to n do
For j:= 1 to n do if cij>0 then fij=0
Đặt nhãn lùi (↓) cho đỉnh đích: z (↓, φ , ∞ )
Tạo lập tập T gồm các đỉnh đã có nhãn lùi nhưng chưa được
dùng để sinh nhãn lùi: T := { z} ; khởi gán điều kiện tăng luồng:
inc_flow:= False;
Bước 2: Sinh nhãn
P1 Sinh nhãn tiến
Trường hợp Stop=True; thì xuất luồng cực đại, kết thúc.
Trường hợp inc_flow=True; chuyển sang thực hiện bước 3
2.1. Chọn đỉnh sinh nhãn tiến
* Trường hợp S ≠ φ : Chọn đỉnh u ∈ S nhỏ nhất (theo thứ tự).
Loại u khỏi S, S := S \ { u} . Ký hiệu nhãn tiến của u là (↑, p, α ) và A là
tập các đỉnh chưa có nhãn tiến kề với đỉnh u, Sang bước 2.2.
12
- * Trường hợp S = φ , thì gán Stop:=True; thông báo hệ thống biết
đã gặp điều kiện dừng, xuất luồng cực đại, kết thúc.
2.2. Gán nhãn tiến cho đỉnh chưa có nhãn tiến và kề đỉnh sinh
nhãn tiến u.
Trường hợp Stop=True; thì xuất luồng cực đại, kết thúc.
Trường hợp inc_flow=True; chuyển sang thực hiện bước 3
* Trường hợp A = φ : Quay lại bước 2.
* Trường hợp A ≠ φ : Chọn t ∈ A nhỏ nhất (theo thứ tự). Loại
t khỏi A, A := A \ { t} . Gán nhãn tiến cho t như sau:
Nếu ( u, t ) ∈ E và f ut < cut , đặt nhãn tiến đỉnh t là
(↑, u, min{α , cu , t − f u , t } ) .
Nếu ( t , u ) ∈ E và f tu > 0 , đặt nhãn tiến đỉnh t là ( ↑, u, minα, f tu } ) .
{
Nếu t không được gán nhãn tiến, thì quay lại bước 2.2.
Nếu t được gán nhãn tiến và t có nhãn lùi, thì gán inc_flow:=
True; thông báo cho hệ thống biết đã tìm được đường đi tăng
luồng, sang bước 3, hiệu chỉnh tăng luồng, xóa nhãn.
Nếu t được gán nhãn tiến và t không gán nhãn lùi, thì bổ
sung t vào S, S : = S ∪ { t} và quay ngược lại bước 2.2.
P2: Sinh nhãn lùi
Trường hợp Stop=True; thì kết thúc.
Trường hợp inc_flow=True; chuyển sang thực hiện bước 3
2.3. Chọn đỉnh sinh nhãn lùi
* Trường hợp T ≠ φ : Chọn đỉnh v ∈ T nhỏ nhất (theo thứ tự).
Loại v khỏi T, T := T \ { v} .
Ký hiệu nhãn lùi của v là (↓, q, β ) và B là tập các đỉnh chưa có
nhãn lùi kề đỉnh sinh nhãn lùi v.
Sang bước 2.4.
* Trường hợp T = φ , thì Stop =True; thông báo hệ thống
biết P2 đã gặp điều kiện dừng, kết thúc.
2.4. Gán nhãn lùi cho đỉnh chưa có nhãn lùi và kề đỉnh sinh nhãn
lùi v.
Trường hợp Stop=True; thì kết thúc.
Trường hợp inc_flow=True; chuyển sang thực hiện bước 3
* Trường hợp B = φ : Quay lại bước 2.
13
- *Trường hợp B ≠ φ : Chọn t ∈ B nhỏ nhất (theo thứ tự). Loại t
khỏi B. B := B \ { t} gán nhãn lùi cho t như sau:
Nếu ( t , v ) ∈ E và f tv < ctv , đặt nhãn lùi đỉnh t là (↓, v, min{ β , ctv − f tv } )
.
Nếu ( v, t ) ∈ E và f vt > 0 , đặt nhãn lùi đỉnh t là (↓, v, min{ β , f vt } ) .
Nếu t không được gán nhãn lùi, thì quay lại bước 2.4.
Nếu t được gán nhãn lùi và t có nhãn tiến thì gán inc_flow:=
True; thông báo cho hệ thống biết P2 đã tìm được đường đi tăng
luồng, sang bước 3, hiệu chỉnh tăng luồng, xóa nhãn.
Nếu t được gán nhãn lùi và t không có nhãn tiến, thì bổ sung
t vào T, T := T ∪ { t} và quay lại bước 2.4.
Bước 3: Hiệu chỉnh tăng luồng, xóa nhãn
Ta có t là đỉnh được gán nhãn tiến ở bước 2.2 hoặc nhãn lùi
ở bước 2.4 để thuật toán dẫn đến bước 3. Đỉnh t có nhãn tiến
(↑, p, α ) và nhãn lùi (↓, q, β ) . Đặt δ = min{α , β } .
Ta hiệu chỉnh luồng f và xóa nhãn như sau.
P1
3.1. Hiệu chỉnh ngược từ t về a theo nhãn tiến
3.1.1. Khởi tạo j := t , i := p
3.1.2. Hiệu chỉnh
Nếu cung ( i, j ) ∈ G , thì hiệu chỉnh f ij = f ij + δ .
Nếu cung ( j, i ) ∈ G , thì hiệu chỉnh f ij = f ij − δ .
3.1.3. Tịnh tiến
Nếu i = a , thì xóa tất cả các nhãn tiến trên mạng trừ đỉnh
nguồn a và đỉnh đích z, thông báo hệ thông biết P1 đã thực hiện
việc tăng luồng, xoá nhãn tiến xong, đợi P2 xoá nhãn xong, quay
lại bước 2.
Nếu i ≠ a , thì đặt j := i và i := h , với h là thành phần thứ hai
của nhãn tiến đỉnh j. Sau đó quay lại bước 3.1.2.
P2
3.2. Hiệu chỉnh từ t đến z theo nhãn lùi
3.2.1. Khởi tạo i := t , j := q
3.2.2. Hiệu chỉnh
Nếu cung ( i, j ) ∈ G , thì hiệu chỉnh f ij = f ij + δ .
14
- Nếu cung ( j, i ) ∈ G , thì hiệu chỉnh f ij = f ij − δ .
3.2.3. Tịnh tiến
Nếu i = z , thì xóa tất cả các nhãn lùi trên mạng trừ đỉnh nguồn a
và đỉnh đích z, thông báo hệ thống biết P2 đã thực hiện việc tăng
luồng, xoá nhãn lùi xong, đợi P1 xoá nhãn xong, quay lại bước 2.
Nếu i ≠ z , thì đặt i := j và j := k , với k là thành phần thứ hai
của nhãn lùi đỉnh i. Sau đó quay lại bước 3.2.2.
Sơ đồ mô tả thuật toán cho ở hình 1.
P1 P2
START
Khoi tao: For i:=1 to ( ndiv 2) Khoi tao: For i:=( ndiv 2 +1) to n
For:=1 to n if cij>0 then fij =0;
j For:=1 to n if cij>0 then fij =0;
j
Dat nhan tien dinh nguon : a(↑ ,Þ,∞) Dat nhan lui dinh dich: z(↓ ,Þ,∞)
Tao lap tap S gom cac dinh da co nhan tien chua Tao lap tap T gom cac dinh da co nhan lui
dung sinh nhan tien S :={ a}; Stop := F; c hua dung sinh nhan lui T :={z }; I nc_ flow:=F;
getData
getData
T
T Display
Stop END Stop
Maxflow
F
F
T T
Inc_flow
Inc _flow
Inc_flow ↓
Inc_flow ↑ F
F Del_Label ↓
Del_Label ↑ Stop=T
Stop=T
Doi P1 xoa
Doi P2 xoa
nhan xong
nhan xong
T
T T =Þ
S=Þ
F
F
u
- VÍ DỤ THUẬT TOÁN
Ví dụ sau đây cho thấy những bước ban đầu của thuật toán
Ford-Fulkerson trong một mạng vận tải gồm 4 nút, nguồn A và
thoát D. Các đường đi tăng được tìm bằng phương pháp tìm
kiếm theo chiều sâu, trong đó các đỉnh lân cận được duyệt theo
thứ tự bảng chữ cái. Ví dụ này cho thấy biểu hiện của trường
hợp xấu nhất của thuật toán. Mỗi bước chỉ gửi thêm được một
luồng giá trị 1 qua mạng. Nếu sử dụng phép tìm theo chiều rộng
thay vì theo chiều sâu, ta sẽ chỉ cần hai bước
Đường
Khả năng thông qua Mạng đạt được
đi
Mạng vận tải ban đầu
min(cf(A,B),cf(B,C),cf(C,D)) =
min(c(A,B) − f(A,B),c(B,C) −
A,B,C,D
f(B,C),c(C,D) − f(C,D)) =
min(1000 − 0,1 − 0,1000 − 0) = 1
min(cf(A,C),cf(C,B),cf(B,D)) =
min(c(A,C) − f(A,C),c(C,B) −
A,C,B,D
f(C,B),c(B,D) − f(B,D)) =
min(1000 − 0,0 − ( − 1),1000 − 0) = 1
Mạng vận tải cuối cùng
16
- VÍ DỤ CHỨNG MINH KHI TA CÀI ĐẶT TRÊN
MÁY:
#include
#include
#define nm 1001
using namespace std;
typedef struct node *ptr;
struct node{int data,cost;ptr pnext;};
void chen(ptr &f,int v,int c)
{
ptr p=new node;
p->data=v;
p->cost=c;
p->pnext=f;
f=p;
}
ptr a[nm];
int c[nm][nm];
int f[nm][nm];
int trace[nm];
int n,m,t,s,k;
int u,v;
int res=0;
dequeq;
bool findpath()
{
q.clear();
memset(trace,0,sizeof(trace));
q.push_back(s);
trace[s]=n+1;
while (q.size())
{
int u=q.front();q.pop_front();
ptr p=a[u];
17
- while (p)
{
int v=p->data;
if (!trace[v]&&c[u][v]>f[u][v])
{
trace[v]=u;
if (v==t)return true;
q.push_back(v);
}
p=p->pnext;
}
}
return false;
}
void incflow()
{
int u,v,delta=1000000000;
v=t;
while (v!=s)
{
u=trace[v];
delta=min(delta,c[u][v]-f[u][v]);
v=u;
}
v=t;
while (v!=s)
{
u=trace[v];
f[u][v]+=delta;
f[v][u]-=delta;
v=u;
}
}
int main()
{
18
- scanf ("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i
- khả năng thông qua của các cung tương ứng với tiết diện
các ống.
Cần phải tìm luồng dầu lớn nhất có thể bơm dầu từ tàu
chở dầu vào bể chứa.
Định lý: Các mệnh đề dưới đây là tương đương:
(i) f là luồng cực đại trong mạng.
(ii) Không tìm được đường tăng luồng f.
(iii) Val(f)=c(X,X*) với một lát cắt (X,X*) nào đó.
(Ta gọi lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của
mạng ra thành hai tập X và X*=V\X, trong đó s ∈ X và t ∈ X*.).
Định lý trên là cơ sở để xây dựng thuật toán lặp sau đây để
tìm luồng cực đại trong mạng: Bắt đầu từ luồng trên tất cả
các cung
bằng 0 (ta sẽ gọi luồng như vậy là luồng không), và lặp lại
bước lặp sau đây cho đến khi thu được luồng mà đối với nó
không còn đường tăng:
Bước lặp tăng luồng (Ford – Fulkerson): Tìm đường tăng P đối
với luồng hiện có, tăng luồng dọc theo đường P.
Khi đã có luồng cực đại, lát cắt hẹp nhất có thể tìm theo
thủ tục mô tả trong việc chứng minh định lý trên. Thuật toán
Ford-Fulkerson được mô tả trong thủ tục sau đây:
Procedure Luongcucdai;
Begin
Stop := false;
While not Stop do
If < Tìm đường tăng luồng P> then
< Tăng luồng dọc theo P>
Else Stop := true;
End;
Để tìm đường tăng luồng trong G(f) có thể sử dụng thuật toán
tìm kiếm theo chiều rộng (hay tìm kiếm theo chiều sâu), bắt đầu
từ đỉnh s trong đó không cần xây dựng tường minh đồ thị G(f).
Ford-Fulkerson đề nghị thuật toán gán nhãn chi tiết sau đây để
giải bài toán luồng cực đại trong mạng. Thuật toán bắt đầu từ
20
nguon tai.lieu . vn
