Toán rời rạc - Chương V: Một số bài toán tối ưu trên đồ thị

Chia sẻ: Nguyen Thanh Huu | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

213
lượt xem 100
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong đời sống, chúng ta t hường gặp những tình huống nư sau: để đi từ điểm A đến điểm B trong thành phố, có nhiều đượng đi, nhiều cách đi; có lúc 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í) ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Toán rời rạc - Chương V: Một số bài toán tối ưu trên đồ thị

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 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
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