Xem mẫu
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
CHƯƠNG V
M TS BÀI TOÁN T I ƯU TRÊN ð TH
5.1. ð TH CÓ TR NG S VÀ BÀI TOÁN ðƯ NG ðI NG N NH T.
5.1.1. M ñ u:
Trong ñ i s ng, chúng ta thư ng g p nh ng tình hu ng như sau: ñ ñi t ñ a
ñi m A ñ n ñ a ñi m B trong thành ph , có nhi u ñư ng ñi, nhi u cách ñi; có lúc ta
ch n ñư ng ñi ng n nh t (theo nghĩa c ly), có lúc l i c n ch n ñư ng ñi nhanh nh t
(theo nghĩa th i gian) và có lúc ph i cân nh c ñ ch n ñư ng ñi r ti n nh t (theo nghĩa
chi phí), v.v...
Có th coi sơ ñ c a ñư ng ñi t A ñ n B trong thành ph là m t ñ th , v i ñ nh
là các giao l (A và B coi như giao l ), c nh là ño n ñư ng n i hai giao l . Trên m i
c nh c a ñ th này, ta gán m t s dương, ng v i chi u dài c a ño n ñư ng, th i gian
ñi ño n ñư ng ho c cư c phí v n chuy n trên ño n ñư ng ñó, ...
ð th có tr ng s là ñ th G=(V,E) mà m i c nh (ho c cung) e∈E ñư c gán b i
m t s th c m(e), g i là tr ng s c a c nh (ho c cung) e.
Trong ph n này, tr ng s c a m i c nh ñư c xét là m t s dương và còn g i là
chi u dài c a c nh ñó. M i ñư ng ñi t ñ nh u ñ n ñ nh v, có chi u dài là m(u,v), b ng
t ng chi u dài các c nh mà nó ñi qua. Kho ng cách d(u,v) gi a hai ñ nh u và v là chi u
dài ñư ng ñi ng n nh t (theo nghĩa m(u,v) nh nh t) trong các ñư ng ñi t u ñ n v.
Có th xem m t ñ th G b t kỳ là m t ñ th có tr ng s mà m i c nh ñ u có
chi u dài 1. Khi ñó, kho ng cách d(u,v) gi a hai ñ nh u và v là chi u dài c a ñư ng ñi t
u ñ n v ng n nh t, t c là ñư ng ñi qua ít c nh nh t.
5.1.2. Bài toán tìm ñư ng ñi ng n nh t:
Cho ñơn ñ th liên thông, có tr ng s G=(V,E). Tìm kho ng cách d(u0,v) t m t
ñ nh u0 cho trư c ñ n m t ñ nh v b t kỳ c a G và tìm ñư ng ñi ng n nh t t u0 ñ n v.
Có m t s thu t toán tìm ñư ng ñi ng n nh t; ñây, ta có thu t toán do E.
Dijkstra, nhà toán h c ngư i Hà Lan, ñ xu t năm 1959. Trong phiên b n mà ta s trình
bày, ngư i ta gi s ñ th là vô hư ng, các tr ng s là dương. Ch c n thay ñ i ñôi chút
là có th gi i ñư c bài toán tìm ñư ng ñi ng n nh t trong ñ th có hư ng.
Phương pháp c a thu t toán Dijkstra là: xác ñ nh tu n t ñ nh có kho ng cách
ñ n u0 t nh ñ n l n.
Trư c tiên, ñ nh có kho ng cách ñ n a nh nh t chính là a, v i d(u0,u0)=0. Trong
các ñ nh v ≠ u0, tìm ñ nh có kho ng cách k1 ñ n u0 là nh nh t. ð nh này ph i là m t
trong các ñ nh k v i u0. Gi s ñó là u1. Ta có:
d(u0,u1) = k1.
67
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Trong các ñ nh v ≠ u0 và v ≠ u1, tìm ñ nh có kho ng cách k2 ñ n u0 là nh nh t. ð nh
này ph i là m t trong các ñ nh k v i u0 ho c v i u1. Gi s ñó là u2. Ta có:
d(u0,u2) = k2.
Ti p t c như trên, cho ñ n bao gi tìm ñư c kho ng cách t u0 ñ n m i ñ nh v c a G.
N u V={u0, u1, ..., un} thì:
0 = d(u0,u0) < d(u0,u1) < d(u0,u2) < ... < d(u0,un).
5.1.3. Thu t toán Dijkstra:
procedure Dijkstra (G=(V,E) là ñơn ñ th liên thông, có tr ng s v i tr ng s dương)
{G có các ñ nh a=u0, u1, ..., un=z và tr ng s m(ui,uj), v i m(ui,uj) =
∞ n u (ui,uj) không là m t c nh trong G}
for i := 1 to n
L(ui) := ∞
L(a) := 0
S := V \ {a}
u := a
while S ≠ ∅
begin
for t t c các ñ nh v thu c S
if L(u) +m(u,v) < L(v) then L(v) := L(u)+m(u,v)
u := ñ nh thu c S có nhãn L(u) nh nh t
{L(u): ñ dài ñư ng ñi ng n nh t t a ñ n u}
S := S \ {u}
end
Thí d 1: Tìm kho ng cách d(a,v) t a ñ n m i ñ nh v và tìm ñư ng ñi ng n nh t t a
ñ n v cho trong ñ th G sau.
b 4 c 6 d
1 1 2 2 2 2
3 4 3
a e g h 3
2 3 5 5 1
n m k
6 3
68
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
L(a) L(b) L(c) L(d) L(e) L(g) L(h) L(k) L(m) L(n)
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
− 1 ∞ ∞ 3 ∞ ∞ ∞ 3 2
− − 5 ∞ 2 ∞ ∞ ∞ 3 2
− − 5 ∞ 2 ∞ ∞ ∞ 3 −
− − 4 ∞ − 6 ∞ ∞ 3 −
− − 4 ∞ − 6 ∞ 6 − −
− − − 10 − 6 ∞ 6 − −
− − − 8 − − 9 6 − −
− − − 8 − − 7 − − −
− − − 8 − − − − − −
5.1.4. ð nh lý: Thu t toán Dijkstra tìm ñư c ñư ng ñi ng n nh t t m t ñ nh cho trư c
ñ n m t ñ nh tuỳ ý trong ñơn ñ th vô hư ng liên thông có tr ng s .
Ch ng minh: ð nh lý ñư c ch ng minh b ng quy n p. T i bư c k ta có gi thi t quy
n p là:
(i) Nhãn c a ñ nh v không thu c S là ñ dài c a ñư ng ñi ng n nh t t ñ nh a t i ñ nh
này;
(ii) Nhãn c a ñ nh v trong S là ñ dài c a ñư ng ñi ng n nh t t ñ nh a t i ñ nh này và
ñư ng ñi này ch ch a các ñ nh (ngoài chính ñ nh này) không thu c S.
Khi k=0, t c là khi chưa có bư c l p nào ñư c th c hi n, S=V \ {a}, vì th ñ dài
c a ñư ng ñi ng n nh t t a t i các ñ nh khác a là ∞ và ñ dài c a ñư ng ñi ng n nh t t
a t i chính nó b ng 0 ( ñây, chúng ta cho phép ñư ng ñi không có c nh). Do ñó bư c
cơ s là ñúng.
Gi s gi thi t quy n p là ñúng v i bư c k. G i v là ñ nh l y ra kh i S bư c
l p k+1, vì v y v là ñ nh thu c S cu i bư c k có nhãn nh nh t (n u có nhi u ñ nh có
nhãn nh nh t thì có th ch n m t ñ nh nào ñó làm v). T gi thi t quy n p ta th y r ng
69
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
trư c khi vào vòng l p th k+1, các ñ nh không thu c S ñã ñư c gán nhãn b ng ñ dài
c a ñư ng ñi ng n nh t t a. ð nh v cũng v y ph i ñư c gán nhãn b ng ñ dài c a
ñư ng ñi ng n nh t t a. N u ñi u này không x y ra thì cu i bư c l p th k s có
ñư ng ñi v i ñ dài nh hơn Lk(v) ch a c ñ nh thu c S (vì Lk(v) là ñ dài c a ñư ng ñi
ng n nh t t a t i v ch a ch các ñ nh không thu c S sau bư c l p th k). G i u là ñ nh
ñ u tiên c a ñư ng ñi này thu c S. ðó là ñư ng ñi v i ñ dài nh hơn Lk(v) t a t i u
ch a ch các ñ nh không thu c S. ði u này trái v i cách ch n v. Do ñó (i) v n còn ñúng
cu i bư c l p k+1.
G i u là ñ nh thu c S sau bư c k+1. ðư ng ñi ng n nh t t a t i u ch a ch các
ñ nh không thu c S s ho c là ch a v ho c là không. N u nó không ch a v thì theo gi
thi t quy n p ñ dài c a nó là Lk(v). N u nó ch a v thì nó s t o thành ñư ng ñi t a t i
v v i ñ dài có th ng n nh t và ch a ch các ñ nh không thu c S khác v, k t thúc b ng
c nh t v t i u. Khi ñó ñ dài c a nó s là Lk(v)+m(v,u). ði u ñó ch ng t (ii) là ñúng vì
Lk+1(u)=min(Lk(u), Lk(v)+m(v,u)).
5.1.5. M nh ñ : Thu t toán Dijkstra tìm ñư ng ñi ng n nh t t m t ñ nh cho trư c ñ n
m t ñ nh tuỳ ý trong ñơn ñ th vô hư ng liên thông có tr ng s có ñ ph c t p là O(n2).
Ch ng minh: Thu t toán dùng không quá n−1 bư c l p. Trong m i bư c l p, dùng
không hơn 2(n−1) phép c ng và phép so sánh ñ s a ñ i nhãn c a các ñ nh. Ngoài ra,
m t ñ nh thu c Sk có nhãn nh nh t nh không quá n−1 phép so sánh. Do ñó thu t toán
có ñ ph c t p O(n2).
5.1.6. Thu t toán Floyd:
Cho G=(V,E) là m t ñ th có hư ng, có tr ng s . ð tìm ñư ng ñi ng n nh t
gi a m i c p ñ nh c a G, ta có th áp d ng thu t toán Dijkstra nhi u l n ho c áp d ng
thu t toán Floyd ñư c trình bày dư i ñây.
Gi s V={v1, v2, ..., vn} và có ma tr n tr ng s là W ≡ W0. Thu t toán Floyd xây
d ng dãy các ma tr n vuông c p n là Wk (0 ≤ k ≤ n) như sau:
procedure Xác ñ nh Wn
for i := 1 to n
for j := 1 to n
W[i,j] := m(vi,vj) {W[i,j] là ph n t dòng i c t j c a ma tr n W0}
for k := 1 to n
if W[i,k] +W[k,j] < W[i,j] then W[i,j] := W[i,k] +W[k,j]
{W[i,j] là ph n t dòng i c t j c a ma tr n Wk}
5.1.7. ð nh lý: Thu t toán Floyd cho ta ma tr n W*=Wn là ma tr n kho ng cách nh
nh t c a ñ th G.
70
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
Ch ng minh: Ta ch ng minh b ng quy n p theo k m nh ñ sau:
Wk[i,j] là chi u dài ñư ng ñi ng n nh t trong nh ng ñư ng ñi n i ñ nh vi v i ñ nh
vj ñi qua các ñ nh trung gian trong {v1, v2, ..., vk}.
Trư c h t m nh ñ hi n nhiên ñúng v i k=0.
Gi s m nh ñ ñúng v i k-1.
Xét Wk[i,j]. Có hai trư ng h p:
1) Trong các ñư ng ñi chi u dài ng n nh t n i vi v i vj và ñi qua các ñ nh trung gian
trong {v1, v2, ..., vk}, có m t ñư ng ñi γ sao cho vk ∉ γ. Khi ñó γ cũng là ñư ng ñi ng n
nh t n i vi v i vj ñi qua các ñ nh trung gian trong {v1, v2, ..., vk-1}, nên theo gi thi t quy
n p,
Wk-1[i,j] = chi u dài γ ≤ Wk-1[i,k]+Wk-1[k,j].
Do ñó theo ñ nh nghĩa c a Wk thì Wk[i,j]=Wk-1[i,j].
2) M i ñư ng ñi chi u dài ng n nh t n i vi v i vj và ñi qua các ñ nh trung gian trong
{v1, v2, ..., vk}, ñ u ch a vk. G i γ = vi ... vk ... vj là m t ñư ng ñi ng n nh t như th thì
v1 ... vk và vk ... vj cũng là nh ng ñư ng ñi ng n nh t ñi qua các ñ nh trung gian trong
{v1, v2, ..., vk-1} và
Wk-1[i,k]+Wk-1[k,j] = chi u dài(v1 ... vk) + chi u dài(vk ... vj)
= chi u dài γ < Wk-1[i,j].
Do ñó theo ñ nh nghĩa c a Wk thì ta có:
Wk[i,j] = Wk-1[i,k]+Wk-1[k,j] .
Thí d 2: Xét ñ th G sau:
7 4
v1 v2 v3
2 1
2 1 3
4 2
v4 v5 v6
Áp d ng thu t toán Floyd, ta tìm ñư c (các ô tr ng là ∞)
7 2
4 1
3
W = W0 =
4
2 2
1
71
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
7 2 7 11 2 8
4 1 4 1
3 3
W1 = , W2 =
4 4 8 5
2 9 2 4 2 9 2 4 10
1 1 5 2
7 11 2 8 14 6 10 2 7 13
4 1 7 4 1 7
3 3
W3 = , W4 =
4 8 5 11 4 8 5 11
2 9 2 4 10 5 2 8 2 4 9 5
2 8 2 8
1 5 1 5
9 6 9 2 7 12 9 6 9 2 7 12
3 9 3 5 1 6 3 7 3 5 1 6
3 7 4 7 9 5 3
W5 = , W* = W6 = .
7 4 7 9 5 10 7 4 7 9 5 10
2 8 2 4 9 5 2 6 2 4 7 5
4 1 4 6 2 7 4 1 4 6 2 7
Thu t toán Floyd có th áp d ng cho ñ th vô hư ng cũng như ñ th có hư ng.
Ta ch c n thay m i c nh vô hư ng (u,v) b ng m t c p c nh có hư ng (u,v) và (v,u) v i
m(u,v)=m(v,u). Tuy nhiên, trong trư ng h p này, các ph n t trên ñư ng chéo c a ma
tr n W c n ñ t b ng 0.
ð th có hư ng G là liên thông m nh khi và ch khi m i ph n t n m trên ñư ng
chéo trong ma tr n tr ng s ng n nh t W* ñ u h u h n.
5.2. BÀI TOÁN LU NG C C ð I.
5.2.1. Lu ng v n t i:
5.2.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={v0, 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.
72
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
5.2.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.
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) ∑ ϕ (e) = ∑ ϕ (e) , ∀v ∈V, v≠v0, v≠vn. ñây, Γ − (v)={e∈E | e có ñ nh cu i là v},
e∈Γ − ( v ) e∈Γ + ( 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:
4) ∑ ϕ (e) = ∑ ϕ (e) =: ϕ vn .
e∈Γ + (v0 ) e∈Γ − ( vn )
ð 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.
5.2.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) ñư c g i là lu ng c a t p
e∈M
cung M.
T ñi u ki n 2) d dàng suy ra h qu sau.
5.2.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)).
5.2.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.
5.2.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.
ð i lư ng m( Γ − (A))= ∑ m( e)
−
ñư c g i là kh năng thông qua c a thi t di n
e∈Γ ( A)
Γ − (A).
73
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
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.
5.2.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 ph i dùng thu t toán Ford-Fulkerson ñ tìm giá tr c c ñ i
c a lu ng.
5.2.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).
74
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
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
vi z
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.
5.2.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 5.2.1.4, ta có:
ϕ (Γ − ( A1 )) = ϕ (Γ + ( A1 )) (1).
ð t C1={(a,vn)∈E | a∉A}. Khi ñó Γ − ( A) = Γ − ( A1 ) ∪ C1 và Γ − ( A1 ) ∩ C1 = ∅, nên
ϕ (Γ − ( 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).
75
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
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)) .
5.2.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à
max ϕ vn = min m(Γ − ( A)) .
ϕ 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 ñ 5.2.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).
Do ñó, ϕ 0 (Γ − ( B)) = ∑ ϕ 0 (e) = ∑ m(e) = m(Γ − ( B))
− −
(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.
Do ñó, ϕ 0 (Γ + ( B )) = ∑ ϕ 0 (e) = 0
+
(3).
e∈Γ ( B )
T (1), (2) và (3) ta suy ra:
ϕ v = m(Γ − ( B )) .
0
n
Vì v y, 0
ϕv là giá tr l n nh t c a lu ng ñ t ñư c, còn m( Γ − (B)) là giá tr nh
n
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.
76
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
4 3
v1 v5
4 4 6
3 6
7 4
8 4
v2 2
5 5
12 11
v0 5 5 3 v6 v8
4
8 v3
6 4 2 6
2 9
4
4 4
v4 v7
ϕ
4 3
v1 v5
4 4 6
3 6
7 4
8 4
v2 2
5 5
12 12
v0 5 5 3 v6 v8
−6 4
0 +4 +7
8 v3
7 4 2 6
3 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.
+4 −6
3−1
v6 v3 2+1
+0 3+1 +3
v4 v7
7+1 6+1
0 v0 xích α v8 +7
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.
77
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
+0 4 3 +1
v1 v5
4 4 6
3 6
7 −5 4
8 4
v2 2
5 5
+2 12 12
v0 5 5 2 v6 v8
−6 4
0 +7
8 v3
8 4 3 7
4 9
4
4 4
v4 v7
ϕ 2
+3
−5 2+1 +2
+1 3−1 v2 v6 2−1 −6
v5
3+1 v3 3+1
+0
v1 +3
7+1 v7
7+1
0 v0 xích β v8 +7
4 4
v1 v5
4 4 6
2 6
8 4
8 4
v2 3
5 5
12 12
v0 5 5 1 v6 v8
v0 4
8 v3
8 4 4 8
4 9
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
−
M t khác, thi t di n nh nh t Γ (B) v i B={v1, v2, ..., v8} là
Γ − (B)={(v0,v1), (v0,v2), (v0,v3), (v0,v4)}.
78
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
5.3. BÀI TOÁN DU L CH.
5.3.1. Gi i thi u bài toán:
M t ngư i xu t phát t m t thành ph nào ñó mu n t i thăm n−1 thành ph
khác, m i thành ph ñúng m t l n, r i quay v thành ph ban ñ u. H i nên ñi theo trình
t nào ñ ñ dài t ng c ng các ño n ñư ng ñi qua là ng n nh t (kho ng cách gi a hai
thành ph có th hi u là c ly thông thư ng ho c th i gian c n ñi ho c chi phí c a hành
trình, ... và xem như cho trư c).
Xét ñ th ñ y ñ G=(V,E), v i V={1, 2, ..., n}, có tr ng s v i tr ng s mij=
m(i,j) có th khác mji = m(j,i). Như v y, ta có th xem G như là m t ñ th có hư ng ñ y
ñ “m nh” theo nghĩa v i m i i, j=1, 2, ..., n, i≠j, luôn có (i,j), (j,i)∈E. Bài toán tr
thành tìm chu trình Hamilton có ñ dài ng n nh t trong G.
Bài toán n i ti ng này ñã có l i gi i b ng cách s d ng phương pháp “nhánh và
c n”.
5.3.2. Phương pháp nhánh và c n: Gi s trong m t t p h u h n các phương án c a
bài toán, ta ph i ch n ra ñư c m t phương án t i ưu theo m t tiêu chu n nào ñó (thí d
làm cho hàm m c tiêu ñ t giá tr nh nh t). Ta s tìm cách phân chia t p phương án
ñang xét thành hai t p con không giao nhau. V i m i t p này, ta s tính “c n dư i”
(ch n dư i ñ t t) c a các giá tr hàm m c tiêu ng v i các phương án trong ñó. Mang
so sánh hai c n dư i v a tính ñư c, ta có th phán ñoán xem t p con nào có nhi u tri n
v ng ch a phương án t i ưu và ti p t c phân chia t p con ñó thành hai t p con khác
không giao nhau, l i tính các c n dư i tương ng ... L p l i quá trình này thì sau m t s
h u h n bư c, cu i cùng s ñư c m t phương án t t, nói chung là t i ưu. N u không thì
l p l i quá trình phân chia ñ ki m tra và sau m t vài bư c, ta s ñư c phương án t i ưu.
Ngư i ta thư ng mô t quá trình phân chia ñó b ng m t “cây có g c” mà g c s
tư ng trưng cho t p toàn b các phương án, còn các ñ nh phía dư i l n lư t tư ng
trưng cho các t p con trong quá trình “phân nhánh nh phân”. Vì v y, phương pháp này
mang tên nhánh và c n.
5.3.3. Cơ s lý lu n c a phép toán: N u không xác ñ nh thành ph xu t phát thì có
n! hành trình, m i hành trình ng v i m t hoán v nào ñó c a t p {1, 2, ..., n}. Còn n u
cho trư c thành ph xu t phát thì có t t c là (n−1)! hành trình.
Gi s h=(π(1), π(2), ..., π(n), π(1)) (π là m t hoán v ) là m t hành trình qua các
thành ph π(1), ..., π(n) theo th t ñó r i quay v π(1) thì hàm m c tiêu
f(h) = mπ (1)π ( 2) + L + mπ ( n −1)π ( n ) + mπ ( n )π (1) = ∑ mij ,
(i , j )∈h
s bi u th t ng ñ dài ñã ñi theo hành trình h, trong ñó (i,j) ký hi u m t ch ng ñư ng
c a hành trình, t c là m t c p thành ph k nhau theo hành trình h.
79
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
5.3.4. Ma tr n rút g n: Quá trình tính toán s ñư c th c hi n trên các ma tr n suy t
ma tr n tr ng s M=(mij) ban ñ u b ng nh ng phép bi n ñ i rút g n ñ các s li u ñư c
ñơn gi n.
Phép tr ph n t nh nh t c a m i dòng (t.ư. c t) vào t t c các ph n t c a dòng
(t.ư. c t) ñó ñư c g i là phép rút g n dòng (t.ư. c t). Ph n t nh nh t ñó ñư c g i là
h ng s rút g n dòng (t.ư. c t) ñang xét. Ma tr n v i các ph n t không âm và có ít nh t
m t ph n t b ng 0 trên m i dòng và m i c t ñư c g i là ma tr n rút g n c a ma tr n
ban ñ u.
Thí d 4:
4 3 5 3 1 0 2 0 0 2
M = 6 2 7 2 → 4 0 5 → M’ = 3 0 5 ,
9 10 5 5 4 5 0 3 5 0
1 0 0
t t nhiên có th rút g n cách khác
4 3 5 0 0 1 0
M = 6 2 7 0 → M’’ = 2 0 2 .
9 10 5 0 5 8 0
4 2 5
5.3.5. M nh ñ : Phương án t i ưu xét trên ma tr n tr ng s ban ñ u cũng là phương án
t i ưu c a bài toán xét trên ma tr n rút g n và ñ o l i.
Ch ng minh: Có th xem vi c ñi tìm chu trình Hamilton c a ngư i du l ch như là m t
bài toán v n t i ñ c bi t dư i d ng b ng. Như v y thì trong b ng (ma tr n tr ng s ho c
ma tr n rút g n) ta ph i có ñúng n ô ch n, m i ô ch n tư ng trưng cho m t c p thành
ph trên hành trình c n tìm, trên m i dòng và m i c t có ñúng m t ô ch n. M i hành
trình h s tương ng m t−m t v i m t t p n ô ch n xác ñ nh. f(h) chính là t ng các
tr ng s ban ñ u ghi trong n ô ch n ñang xét.
V i m i hành trình h b t kỳ, n u ký hi u f′(h)= ∑ m'ij là giá tr c a hàm m c
(i , j )∈h
tiêu ng v i ma tr n rút g n M’ và s là t ng các h ng s rút g n thì ta có:
f(h) = f′(h)+s.
G i X là t p toàn b các phương án ñang xét m t giai ño n nào ñó, h0 là
phương án t i ưu c a bài toán xét trên ma tr n tr ng s ban ñ u M, ta có:
f(h0) ≤ f(h), ∀h∈X
hay f(h0)−s ≤ f(h)−s, ∀h∈X hay f′(h0) ≤ f′(h), ∀h∈X hay h0 là phương án t i ưu c a bài
toán xét trên ma tr n rút g n M’.
80
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
5.3.6. Phân nhánh: S phân ho ch t p h p t t c các hành trình m t giai ño n nào
ñó thành hai t p con r i nhau ñư c bi u di n b ng s phân nhánh c a m t cây. Trên
cây, m i ñ nh ñư c bi u di n thành m t vòng tròn và s tư ng trưng cho môt t p hành
trình nào ñó. ð nh X ñ u tiên là t p toàn b các hành trình. ð nh (i,j) bi u di n t p các
hành trình có ch a c p (i,j) k nhau. ð nh (i, j ) bi u di n t p các hành trình không ch a
c p (i,j) k nhau. T i ñ nh (i,j) l i có s phân nhánh: ñ nh (k,l) bi u di n t p các hành
trình có ch a c p (i,j) và c p (k,l), ñ nh (k , l ) bi u di n t p các hành trình có ch a c p
(i,j) nhưng không ch a c p (k,l) ...
N u quá trình di n ra ñ l n thì cu i cùng s có nh ng ñ nh ch bi u di n m t
hành trình duy nh t.
V n ñ ñ t ra là nên ch n c p thành ph nào ñ ti n hành phân nhánh xu t phát
t m t ñ nh cho trư c trên cây? M t cách t nhiên ta nên ch n c p thành ph nào g n
nhau nh t ñ phân nhánh trư c, trên ma tr n rút g n thì nh ng c p thành ph (i,j) như
v y ñ u có m'ij =0 và nh ng hành trình nào ch a c p (i,j) ñ u có tri n v ng là t t.
Trên ma tr n rút g n thư ng có nhi u c p thành ph tho mãn ñi u ki n ñó
( m'ij =0). ð quy t ñ nh ta ph i tìm cách so sánh. Vì thành ph i nh t thi t ph i n i li n
v i m t thành ph nào ñó nên các hành trình h không ch a (i,j) t c là h∈ (i, j ) ph i ng
v i nh ng ñ dài hành trình ít ra có ch a ph n t nh nh t trong dòng i không k m'ij =0
và ph n t nh nh t trong c t j không k m'ij =0 vì thành ph j nh t thi t ph i n i li n
v i m t thành ph nào ñó trư c nó trên hành trình. Ký hi u t ng c a hai ph n t nh
nh t ñó là θij thì ta có f′(h) ≥ θij, ∀h∈ (i, j ) .
Vì lý do trên, s θij có th dùng làm tiêu chu n so sánh gi a các c p thành ph
(i,j) cùng có m'ij =0. M t cách t ng quát, m i giai ño n ta s ch n c p thành ph (i,j)
có m'ij =0 trong ma tr n rút g n và có θij l n nh t ñ ti n hành phân nhánh t m t ñ nh
trên cây.
5.3.7. Tính c n: V i m i ñ nh c a cây phân nhánh, ta ph i tính c n dư i c a các giá tr
hàm m c tiêu ng v i t p phương án mà ñ nh ñó bi u di n. C n dư i tính ñư c s ghi
bên dư i ñ nh ñang xét.
Theo công th c f(h)=f′(h)+s và do f′(h) ≥ 0 nên f(h) ≥ s, ∀h∈X. Vì v y t ng các
h ng s rút g n c a ma tr n ban ñ u có th l y làm c n dư i c a ñ nh X ñ u tiên trên
cây. M t khác, ta l i có f′(h) ≥ θij, ∀h∈ (i, j ) , do ñó f(h)=f′(h)+s ≥ θij+s, ∀h∈ (i, j ) . Vì
v y t ng θij+s có th l y làm c n dư i cho ñ nh (i, j ) . Sau khi ch n (i,j) ñ phân nhánh
xu t phát t ñ nh X thì trên b ng có th xoá dòng i và c t j vì trên ñó ô ch n (i,j) là duy
nh t. Sau khi b dòng i và c t j thì ma tr n M’ l i có th rút g n thành ma tr n M’’ v i
s’ là t ng các h ng s rút g n, f″(h) là giá tr c a hàm m c tiêu xét trên M’’. Khi ñó ta
có f′(h)=f″(h)+s’, ∀h∈(i,j), do ñó f(h)=f′(h)+s=f″(h)+s+s’, ∀h∈(i,j). Do f″(h) ≥ 0 nên
81
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
f(h) ≥ s+s’, ∀h∈(i,j), nghĩa là t ng s+s’ có th l y làm c n dư i cho ñ nh (i,j) trong cây
phân nhánh.
N u ti p t c phân nhánh thì c n dư i c a các ñ nh ti p sau ñư c tính toán tương
t , vì ñây là m t quá trình l p. Ta ch c n xem ñ nh xu t phát c a các nhánh gi ng như
ñ nh X ban ñ u.. ð ti t ki m kh i lư ng tính toán, ngư i ta thư ng ch n ñ nh có c n
dư i nh nh t ñ phân nhánh ti p t c.
5.3.8. Th t c ngăn ch n hành trình con: M t ñư ng ñi ho c chu trình Hamilton
không th ch a chu trình con v i s c nh t o thành nh hơn n. Vì v y ta s ñ t mii=∞
(i=1, ..., n) ñ tránh các khuyên.
V i i≠j và n u (i,j) là ô ch n thì ph i ñ t ngay m’ji=∞ trong ma tr n rút g n.
N u ñã ch n (i,j) và (j,k) và n>3 thì ph i ñ t ngay m’ji=m’kj=m’ki=∞.
Chú ý r ng vi c ñ t m’ij=∞ tương ñương v i vi c xoá ô (i,j) trong b ng ho c xem
(i,j) là ô c m, nghĩa là hai thành ph i và j không ñư c k nhau trong hành trình ñ nh
ki n thi t. m i giai ño n c a quá trình ñ u ph i ti n hành th t c ngăn ch n này trư c
khi ti p t c rút g n ma tr n.
5.3.9. Tính ch t t i ưu: Quá trình phân nhánh, tính c n, ngăn ch n hành trình con, rút
g n ma tr n ph i th c hi n cho ñ n khi nào có ñ n ô ch n ñ ki n thi t m t hành trình
Hamilton, nói cách khác là cho ñ n khi trên cây phân nhánh ñã xu t hi n m t ñ nh ch
bi u di n m t hành trình duy nh t và ñã xoá h t ñư c m i dòng m i c t trong b ng. C n
dư i c a ñ nh cu i cùng này chính là ñ dài c a hành trình v a ki n thi t.
a) N u c n dư i c a ñ nh này không l n hơn các c n dư i c a m i ñ nh treo trên cây
phân nhánh thì hành trình ñó là t i ưu.
b) N u trái l i thì ph i xu t phát t ñ nh treo nào có c n dư i nh hơn ñ phân nhánh
ti p t c và ki m tra xem ñi u ki n a) có tho mãn không.
Thí d 5: Xét bài toán v i 6 thành ph , các s li u cho theo b ng sau:
∞ 27 43 16 30 26 16
7 ∞ 14 1 30 25 1
20 13 ∞ 35 5 0 0
M=
21 16 25 ∞ 18 18 16
12 46 27 48 ∞ 5 5
23 5 5 9 5 ∞ 5
5 0 0 0 0 0
T ng các h ng s rút g n bư c ñ u là s=48. Trong ma tr n rút g n ta có:
m’14=m’24=m’36=m’41=m’42=m’56=m’62=m’63=m’65=0
82
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
và θ14=10, θ24=1, θ36=5, θ41=1, θ42=0, θ56=2, θ62=0, θ63=9, θ65=2. Sau khi so sánh ta
th y θ14=10 là l n nh t nên ta ch n ô (1,4) ñ phân nhánh. C n dư i c a ñ nh (1,4) là
s+θ14=58. Xoá dòng 1 c t 4 r i ñ t m’41=∞.
1 2 3
4 5 6
1 ∞ 0 14 10
11 27
2 1∞ 13 0 29 24
3 13 ∞ 35 5 0
15
M’ = .
4 0 0 9 ∞ 2 2
5 241 22 43 ∞ 0
6 130 0 4 0 ∞
1 2 3 5 6 1 2 3 5 6
21 ∞ 13 29 24 2 0 ∞ 12 28 23
3 15 13 ∞ 5 0 3 15 13 ∞ 5 0
4 ∞ 0 9 2 2 M’’ = 4 ∞ 0 9
→ 2 2 .
5 2 41 22 ∞ 0 5 2 41 22 ∞ 0
0 0 0 ∞ 0 ∞
6 13 6 13 0 0
T ng h ng s rút g n là s’=1. V y c n dư i c a ñ nh (1,4) là s+s’=49. Vì 49
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
phân nhánh. C n dư i c a ñ nh (6,3) là 58+9=67. ð t m’36=∞. Rút g n ma tr n v i t ng
h ng s rút g n là 15. C n dư i c a ñ nh (6,3) là 58+15=73.
X
48
(1,4) (1,4)
X
58 (6,3) 49
(6,3) (2,1) (2,1)
67 63 65 51
(5,6) (5,6)
73 X
56
(3,5) (3,5)
X
64 63
(6,2) (6,2)
X
63
(4,3)
X
BÀI T P CHƯƠNG V:
1. Dùng thu t toán Dijkstra tìm ñư ng ñi ng n nh t t ñ nh a ñ n các ñ nh khác trong ñ
th sau:
c 2
4
2 d
b 3 7
k 12 e
4 1 5 3 4
h 5
2 7
a 11 g
2. Dùng thu t toán Dijkstra tìm ñư ng ñi ng n nh t t ñ nh a ñ n các ñ nh khác trong ñ
th sau: 4
b f
1
1 10 2 5
4
10 c g 2
1
a 6 4 5 8 k
3
3 d h
5
2 6 3
8
e i
84
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
3. Cho ñ th có tr ng s như hình dư i ñây. Hãy tìm ñư ng ñi ng n nh t t ñ nh A ñ n
ñ nh N.
7 3 8 3
A B C D E
4 2 2 6 2 2 5
3
1 F 4 G 2 H 2 I 3
3 5 4 2
2 4 3 3
J K L M N
2 9 5 7
4. Tìm ñư ng ñi ng n nh t t B ñ n các ñ nh khác c a ñ th có ma tr n tr ng s là (các
ô tr ng là ∞):
A B C D E F G
A
3 6
B 3 2 4
C 6 2 1 4 2
D 4 1 2 4
E
4 2 2 1
F 2 2 4
G 4 1 4
5. Tìm W* b ng cách áp d ng thu t toán Floyd vào ñ th sau:
8
B C
3 2 5 6
20 13
A F D
3 4
1
8
E
6. Gi i bài toán m ng v n t i sau b ng thu t toán Ford-Fulkerson v i lu ng v n t i kh i
ñ u b ng 0.
6
v1 v5
2 4
4
8
2 4 2
v0 v3 v4 v7
4 3
4 8
v2 v6
6
85
- http://ebook.here.vn T i mi n phí ð thi, eBook, Tài li u h c t p
7. Gi i bài toán m ng v n t i sau b ng thu t toán Ford-Fulkerson v i lu ng v n t i kh i
ñ u ñư c cho kèm theo.
6 6
v1 v2 10
10
8 8 15 0 6
2
8 8 20 16
v0 v3 v4
28 10
4 16 6 0 3 25
2 6 3 30
15 10
5 0 v6 v7
v5 0 7
0 0
10 8 0 7
15 6
1
2 2 2
v8 2 v10 v11
4
12 2
v9 20 0
8. Hãy gi i bài toán ngư i du l ch v i 6 thành ph , có s li u cho trong ma tr n tr ng s
sau:
∞ 25 45 14 32 24
9 ∞ 16 2 34 23
22 11 ∞ 33 7 0
.
23 14 27 ∞ 20 21
14 44 29 46 ∞ 3
25 3 4 7 8 ∞
86
nguon tai.lieu . vn