Xem mẫu

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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 21 ∞ 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
  18. 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
  19. 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
  20. 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