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 vộ ỉ ộ ỉ 0 không có cung đi vào, t c làứ
degt(v0)=0. Đ nh vỉ0 đ 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 vộ ỉ ộ ỉ n không có cung đi ra, t c làứ
dego(vn)=0. Đ nh vỉn đ 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.
2)
∑
−
Γ∈ )(
)(
ve
e
ϕ
=
∑
+
Γ∈ )(
)(
ve
e
ϕ
, ∀v ∈V, v≠v0, v≠vn. đây, Ở
−
Γ
(v)={e∈E |
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 vằ ế ả ố 0 hay l i ra vốn, 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:ừ ệ
4)
∑
+
Γ∈ )( 0
)(
ve
e
ϕ
=
∑
−
Γ∈ )(
)(
n
ve
e
ϕ
=:
n
v
ϕ
.
Đ i l ng ạ ượ
n
v
ϕ
(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 vạ ườ ộ ồ ạ ể n hay giá tr c aị ủ
lu ng ồϕ. Bài toán đ t ra đây là tìm ặ ở ϕ đ ể
n
v
ϕ
đ 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)=
∑
∈Me
e)(
ϕ
đ cượ
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 ể ạ
n
v
ϕ
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 vứ ố n. T p ậ
−
Γ
(A) đ c g i là m t thi tượ ọ ộ ế
di n c a m ng v n t i G.ệ ủ ạ ậ ả
Đ i l ng m(ạ ượ
−
Γ
(A))=
∑
−
Γ∈ )(
)(
Ae
em
đ 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 vậ ấ ằ ỗ ơ ị ượ ể ừ 0
đ n vến í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 vế ỗ ườ ừ 0 đ n vến đ 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 vừ ố 0 đ n l i ra vế ố n không ch a cung bão hoà. Khi đóứ
ta nâng lu ng ồϕ thành ϕ’ nh sau:ư
∉
∈+
=.)(
,1)(
)('
αϕ
αϕ
ϕ
ekhie
ekhie
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 vố0 đ c đánhượ
d u b ng 0.ấ ằ
1) N u đ nh vế ỉ i đã đ 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à (vấ ọ ỉ ư ượ ấ i,y)∈E
và cung này ch a bão hoà (ưϕ(vi,y)<m(vi,y)).
2) N u đ nh vế ỉ i đã đ c đánh d u thì ta dùng ch s ượ ấ ỉ ố −i để
đánh d u cho m i đ nh z ch a đ c đánh d u mà (z,vấ ọ ỉ ư ượ ấ i)∈E
và lu ng c a cung này d ng (ồ ủ ươ ϕ(z,vi)>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 vồ ạ ữ 0 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 vừo đ n vến,
ϕ’(e) = ϕ(e)−1, n u eế∈α đ c đ nh h ng ng c v i chi uượ ị ướ ượ ớ ề
c a xích ủα đi t vừo đ n vến.
0
e
+i y vj
z
vn
vi
v0
-j
5