Tóm tắt luận án Bài toán ghép cặp và ứng dụng

Nội dung text: Tóm tắt luận án Bài toán ghép cặp và ứng dụng

1. 1 B GIÁO D C VÀ ĐÀO T O ĐI H C ĐÀ N NG NGUY N TH ÁNH ĐÀO BÀI TỐN GHÉP C P VÀ NG D NG Chuyên ngành : PH ƯƠ NG PHÁP TỐN S Ơ C P Mã s : 60.46.40 TĨM T T LU N V ĂN TH C S Ĩ KHOA H C Đà N ng - N ăm 2011
2. 2 Cơng trình đưc hồn thành t i ĐI H C ĐÀ N NG Ng ưi h ưng d n khoa h c: PGS.TSKH. Tr n Qu c Chi n Ph n bi n 1: TS Cao V ăn Nuơi Ph n bi n 2: GS.TSKH Nguy n V ăn M u Lu n v ăn đưc b o v t i H i đng ch m lu n v ăn t t nghi p Th c sĩ khoa h c hp t i Đi h c Đà N ng vào ngày 22 tháng 10 năm 2011. * Cĩ th tìm hi u lu n v ăn t i: - Trung tâm Thơng tin - H c li u, Đi h c Đà N ng - Th ư vi n tr ưng Đi h c S ư ph m, Đi h c Đà N ng
3. 3 M ĐU 1. ĐT V N Đ CHUNG V Đ TÀI NGHIÊN C U Đ tài “ Bài tốn ghép c p và ng d ng ” đã đưc Th y giáo PGS.TSKH Tr n Qu c Chi n g i ý, b n thân th y phù h p v i kh n ăng ca mình và ph c v t t cho cơng vi c gi ng d y ph thơng nên tơi ch n đ nghiên c u. Điu ki n đm b o cho vi c hồn thành đ tài: Đưc Th y giáo hưng d n cung c p tài li u và t n tình giúp đ, b n thân s ưu t p các ngu n tài li u khác đ đ đm b o hồn thành đ tài. Đ tài phù h p v i s thích c a b n thân vì đây là m t trong nhng ni dung phát tri n t ư duy c a h c sinh r t t t. 2. LÝ DO CH N Đ TÀI Năm 2001, B Giáo D c và Đào T o cĩ qui đnh các chuyên đ b i dưng h c sinh gi i th ng nh t trong tồn qu c trong đĩ cĩ chuyên đ Lý Thuy t Đ Th . Nh ư v y, vi c h c chuyên đ Lý Thuy t Đ Th đi v i hc sinh khá và gi i đang là nhu c u th c t trong d y h c tốn ph thơng. Tuy nhiên, vi c d y h c chuyên đ này cịn t n t i m t s khĩ kh ăn vì m t s lý do khác nhau. M t trong các lý do đĩ là s m i m , đc đáo và khĩ c a ch đ ki n th c này. H ơn n a, s l ưng bài t p ph thơng ng dng chuyên đ này đ gi i là khơng nhi u. Chuyên đ Lý Thuy t Đ Th cĩ m t đc đim n i b c là vi c gi i các d ng tốn trong “ lịng đ th ” khơng c n nhi u đn ki n th c mà h c sinh khơng hi u đưc mà c n đn s sáng t o trong cách nhìn nh n bài tốn và l p lu n cách gi i d ưi con m t c a Lý Thuy t Đ Th . H ơn n a, n i dung các bài tốn gi i b ng ph ươ ng pháp đ th r t g n v i th c t , lý lu n đ gi i các bài tốn này h p d n, lý thú và đy b t ng . Điu này thu hút s quan tâm ngày càng nhi u c a các h c sinh khá và gi i tốn. Vì v y,
4. 4 chuyên đ này ch a đng nhi u ti m n ăng l n cĩ th khai thác đ b i dưng cho h c sinh khá và gi i. Các bài tốn dùng Lý Thuy t Đ Th đ gi i ngày càng xu t hi n nhi u trong các cu c thi ch n h c sinh gi i và các cu c thi tốn qu c t . Điu này phù h p v i xu h ưng đư a tốn h c v áp d ng vào trong th c t cu c s ng. Mt trong nh ng bài tốn n i ti ng và vi c nghiên c u nĩ đã đĩng gĩp r t nhi u k t qu cho Lý Thuy t Đ Th đĩ là M ng và các ng d ng ca M ng. Tuy nhiên, M ng và các ng d ng c a M ng đã đưc các nhà khoa h c nghiên c u và đ c p khá nhi u. Do v y, tơi ch xin đ c p đn mt ng d ng khác c a m ng là “ Bài tốn ghép c p và ng d ng ”. Chính vì nh ng lý do trên đây mà tơi l a ch n đ tài : “ Bài tốn ghép c p và ng d ng ” đ nghiên c u. 3. M C ĐÍCH NGHIÊN C U Đ tài s c ng c các ki n th c v Lý Thuy t Đ Th , nghiên c u sâu v bài tốn ghép c p và các ng d ng c a nĩ. 4. ĐI T ƯNG VÀ PH M VI NGHIÊNC U 4.1. Đi t ưng nghiên c u Lu n v ăn s nghiên c u sâu v bài tốn ghép c p 4.2. Ph m vi nghiên c u Ly Lý Thuy t Đ Th làm c ơ s nghiên c u bài tốn ghép c p và đư a ra ph ươ ng pháp gi i c a bài tốn này. 5. PH ƯƠ NG PHÁP NGHIÊN C U Cơ b n s d ng ph ươ ng pháp nghiên c u tài li u liên quan đn lu n văn đ thu th p thơng tin nh m phân tích, h th ng, thi t l p các d ng tốn ph c v cho yêu c u c a đ tài. 6. C U TRÚC C A LU N V ĂN Lu n v ăn g m cĩ 3 ch ươ ng:
5. 5 Ch ươ ng 1- ĐI C ƯƠ NG V Đ TH Trình bày nh ng ki n th c c ơ b n v Lý Thuy t Đ Th . Ch ươ ng 2- BÀI TỐN GHÉP C P Gi i thi u bài tốn ghép c p, bài tốn lu ng c c đi và các đnh lý, thu t tốn liên quan đn bài tốn này. Ch ươ ng 3- NG D NG C A BÀI TỐN GHÉP C P Trình bày các ng d ng c a bài tốn ghép c p, bài tốn lu ng c c đi trong các v n đ th c t và ng d ng c a bài tốn này .
6. 6 CH ƯƠ NG 1 ĐI C ƯƠ NG V Đ TH 1.1 CÁC KHÁI NI M C Ơ B N 1.1.1 Đ th , đnh, c nh, cung Đnh ngh ĩa 1.1. Đ th vơ h ưng G = (V, E) g m t p V các đnh và t p E các c nh. M i c nh e∈ E đưc liên k t v i m t c p đnh v, w (khơng k th t ). Đnh ngh ĩa 1.2. Đ th cĩ h ưng G = (V, E) g m t p V các đnh và tp E các c nh cĩ h ưng g i là cung. M i cung e∈ E đưc liên k t v i mt c p đnh (v, w) cĩ th t . Đnh ngh ĩa 1.3 . N u thay m i cung c a đ th cĩ h ưng G b ng mt c nh, thì đ th vơ h ưng nh n đưc là đ th lĩt c a G. 1.1.2 Các khái ni m c ơ b n khác • Hai c nh k nhau là hai c nh cùng liên thu c m t đnh. • Hai đnh k nhau là hai đnh cùng liên thu c m t c nh. • Hai c nh g i là song song n u chúng liên k t v i cùng m t c p đnh. • Khuyên là c nh cĩ hai đnh liên k t trùng nhau. • Đnh cơ l p là đnh khơng liên k t v i b t k ỳ đnh nào khác. • Đnh treo là đnh ch liên k t v i m t đnh duy nh t. • S đnh c a đ th g i là b c c a đ th , ký hi u d(G). • S c nh c a đ th g i là c c a đ th , ký hi u card(G). 1.2 CÁC LO I Đ TH 1.2.1 Đ th h u h n Đnh ngh ĩa 1.4. Đ th h u h n là đ th cĩ b c và c h u h n. 1.2.2 Đơ n đ th , đa đ th Đnh ngh ĩa 1.5. Đ th đơ n là đ th khơng cĩ khuyên và c nh song song, ng ưc l i là đa đ th . 1.2.3 Đ th đ
7. 7 Đnh ngh ĩa 1.6. a) Đ th vơ h ưng đ là đ th mà m i c p đnh đu k nhau. b) Đ th cĩ h ưng đ là đ th cĩ đ th lĩt đ c) Đ th K n là đ th đơ n, vơ h ưng đ n đnh (m i c p đnh đu cĩ duy nh t m t c nh liên k t) 1.2.4 Đ th l ưng phân Đnh ngh ĩa 1.7. Đ th l ưng phân G = (V, E) là đ th mà t p các đnh đưc phân thành hai t p r i nhau V1 và V2 sao cho m i c nh c a nĩ liên k t v i m t đnh thu c V1 và m t đnh thu c V2 . = { } Ký hi u G( VV1 , 2 ,) E . 1.2.5 Đ th thu n nh t Đnh ngh ĩa 1.8. Đ th G g i là đ th thu n nh t b c h (h là m t s nguyên khơng âm) n u m i đnh đu cĩ b c h. 1.2.6. Đ th con, đ th đng c u a) Đ th con Đnh ngh ĩa 1.9. Cho đ th G= ( V , E ) . Đ th G'= ( V ', E ') gi là đ th con c a G n u V'⊂ V & E ' ⊂ E . Nu V’=V thì G’ g i là đ th con ph c a G. b) Đ th đng c u = = Đnh ngh ĩa 1.10. Hai đ th G1( V 1 , E 1 ) và G2( V 2 , E 2 ) → đưc g i là đng c u nhau n u t n t i song ánh f: V1 V 2 và → ∀∈ = ⇔ g: E1 E 2 th a mãn e Ee1 : ( v ,w) g(e)=(f(v),f(w)) . Cp hàm f và g g i là m t đng c u t G1 đn G2 . = = Đnh lý 1.1 Hai đơ n đ th G1( V 1 , E 1 ) và G2( V 2 , E 2 ) đng → ∀ ∈ cu v i nhau n u t n t i song ánh f: V1 V 2 th a mãn u, v V 1 : u k v ⇔ f(u) k f(v). = = Đnh lý 1.2 Cho G1( V 1 , E 1 ) và G2( V 2 , E 2 ) là hai đ th đng c u. Khi đĩ: (i) G1 và G2 cĩ s c nh và s đnh b ng nhau.
8. 8 (ii) V i m i s t nhiên k, s đnh b c k c a G1 và G2 bng nhau, s chu trình s ơ c p chi u dài k c a G1 và G2 b ng nhau. (iii) Các c p đ th con t ươ ng ng c ũng đng c u. 1.2.7 Đ th bù, đ th đưng a) Đ th bù Đnh ngh ĩa 1.11. Xét đơ n đ th G= ( V , E ). Đ th bù c a G là đơ n đ th G= ( V , E ) v i t p các c nh đưc đnh ngh ĩa nh ư sau: E = {( u, v) | u, v ∈ V & (u, v) ∉ E } Nh ư v y n u G là đ th bù c a G thì G c ũng là đ th bù c a G . b) Đ th đưng Đnh ngh ĩa 1.12. Cho đ th G= ( V , E ). Đ th đưng c a G, ký hi u L(G) là đ th cĩ các đnh t ươ ng ng v i các c nh c a G và hai đnh k nhau trong L(G) n u các c nh t ươ ng ng trong G k nhau. Đnh lý 1.3 . Hai đơ n đ th đng c u nhau khi và ch khi các đ th bù c a chúng đng c u nhau. Đnh lý 1.4. N u hai đơ n đ th đng c u nhau, thì các đ th đưng ca chúng c ũng đng c u nhau. 1.2.8. Đ th ph ng Đnh ngh ĩa 1.13 Mt đ th g i là đ th hình h c ph ng n u nĩ đưc bi u di n trên m t ph ng sao cho các c nh khơng c t nhau. 1.2.9. Đ th đi ng u Đnh ngh ĩa 1.14. Mi b n đ trên m t ph ng cĩ th bi u di n b ng mt đ th . Đ l p s t ươ ng ng đĩ, m i mi n c a b n đ đưc bi u di n thành 1 đnh. Hai đnh k nhau n u các mi n t ươ ng ng cĩ biên gi i chung. Hai mi n chung nhau 1 đim khơng đưc coi là k nhau. Đ th nh n đưc bng cách nh ư v y g i là đ th đi ng u c a b n đ. Nh ư v y m i b n đ trên m t ph ng đu cĩ đ th đi ng u ph ng. 1.3 . BC, N A B C VÀO, N A B C RA 1.3.1 Đnh ngh ĩa b c, n a b c vào, n a b c ra:
9. 9 • Bc: Cho đ th G = (V, E). B c c a đnh v∈ V là t ng s c nh liên thu c v i nĩ và ký hi u là d(v). Nu đnh cĩ khuyên thì khuyên đưc tính là 2 khi tính b c, nh ư vy: d(v) = s c nh liên thu c đnh v + 2* s khuyên. Nh ư v y đnh cơ l p trong đ th đơ n là đnh cĩ b c b ng 0. Đnh treo là đnh cĩ b c b ng 1. Bc l n nh t c a các đnh trong đ th G ký ki u là ∆(G ) và b c nh nh t c a các đnh trong G ký hi u là δ (G ) . • Na b c: Cho đ th cĩ h ưng G = (V,E), v∈ V . Na b c ra c a đnh v, kí hi u d 0(v) là s cung đi ra t đnh v (v là đnh đu). Na b c vào c a đnh v, kí hi u d I(v) là s cung đi t i đnh v (v là đnh cu i). 1.3.2. Các đnh lý v b c Đnh lý 1.5 Cho đơ n đ th G cĩ s đnh l n h ơn 1. Khi đĩ G cĩ ít nh t hai đnh cĩ cùng b c Đnh lý 1.6 Cho đ th G = (V,E). Khi đĩ t ng b c các đnh c a đ th là s ch n và ∑d( v )= 2. c ard(E) . v∈ V H qu 1.1 S đnh b c l c a đ th vơ h ưng là s ch n. Mnh đ 1.1 M i đnh c a đ th Kn cĩ b c là n-1 và Kn n( n − 1) cĩ c nh. 2 = { } Mnh đ 1.2 Cho đ th l ưng phân đ Km, n ( VVE 1, 2 , ) . Khi đĩ m i đnh trong t p V1 cĩ b c là n, m i đnh trong t p V2 cĩ b c là m và Km, n cĩ m.n c nh. 1.4 . ĐƯNG ĐI, CHU TRÌNH, TÍNH LIÊN THƠNG 1.4.1. Các đnh ngh ĩa Đnh ngh ĩa 1.15. Cho đ th G= ( V , E ) .
10. 10 Dãy µ t đnh v đn đnh w là dãy các đnh và c nh n i ti p nhau bt đu t đnh v và k t thúc t i đnh w. S c nh trên dãy µ g i là đ dài c a dãy µ . Dãy µ t đnh v đn đnh w cĩ đ dài n đưc bi u di n nh ư sau: µ = ( ) vevev,1122 , , , , , vn− 1 , e n ,w = − = trong đĩ vi , i 1, n 1 là các đnh trên dãy và ei , i 1, n là các c nh trên dãy liên thu c đnh k tr ưc và k sau nĩ. Các đnh và c nh trên dãy cĩ th l p l i. Đnh ngh ĩa 1.16 Đưng đi t đnh v đn đnh w là dãy t đnh v đn đnh w trong đĩ các c nh khơng l p l i. Đnh ngh ĩa 1.17 Đưng đi s ơ c p là đưng đi khơng qua m t đnh quá m t l n. Đnh ngh ĩa 1.18 Vịng là dãy cĩ đnh đu và đnh cu i trùng nhau. Đnh ngh ĩa 1.19 Chu trình là đưng đi cĩ đnh đu và đnh cu i trùng nhau. Đnh ngh ĩa 1.20 Chu trình s ơ c p là chu trình khơng đi qua m t đnh quá m t l n. Đnh ngh ĩa 1.21 Đ th vơ h ưng đưc g i là liên thơng n u m i cp đnh c a nĩ đu cĩ đưng đi n i chúng v i nhau. 1.4.2. Các đnh lý Đnh lý 1.7 . Đ th G l ưng phân khi và ch khi G khơng ch a chu trình cĩ đ dài l . Đnh lý 1.8 Cho đơ n đ th G= ( V , E ) v i n đnh và k thành ph n liên thơng. Khi đĩ s c nh m c a đ th th a b t đng th c: (n− k )( n − k + 1) n− k ≤ m ≤ 2 H qu 1.2 M i đơ n đ th n đnh v i s c nh l n h ơn (n− 1)( n − 2) là liên thơng. 2
11. 11 Đnh lý 1.9 M i chu trình đ th ph ng cĩ đ dài ch n khi và ch khi m i m t c a đ th cĩ b c ch n. Đnh lý 1.10 (Cơng th c Euler) Cho G là đ th liên thơng ph ng cĩ e c nh, v đnh và f m t. Khi đĩ ta cĩ cơng th c: f=e-v+2. Đnh lý 1.11 Cho G là đơ n đ th liên thơng ph ng cĩ e c nh, v g đnh và đai g, khơng cĩ đnh treo. Khi đĩ ta cĩ e≤( v − 2) g − 2 ( g ≥ 3) . H qu 1.3 Cho G là đơ n đ th ph ng liên thơng v i e c nh và v đnh ( v ≥ 3), khơng cĩ đnh treo Khi đĩ ta cĩ: e≤3 v − 6. H qu 1.4 Cho G là đơ n đ th ph ng liên thơng v i e c nh và v đnh ( v ≥ 3), khơng cĩ đnh treo và khơng cĩ chu trình đ dài 3. Khi đĩ ta cĩ: e≤2 v − 4.
12. 12 CH ƯƠ NG 2 BÀI TỐN GHÉP C P 2.1. M NG • M ng Mng là đơ n đ th cĩ h ưng G = (V, E, c) th a mãn (i) Cĩ duy nh t 1 đnh, g i là ngu n, khơng liên thu c cung vào (ii) Cĩ duy nh t 1 đnh, g i là đích, khơng liên thu c cung ra (iii) Tr ng s c ij c a cung (i, j) là các s khơng âm và g i là kh năng thơng qua c a cung (iv) th liên thơng y u Đ ∈ • Lu ng Cho m ng G v i kh n ăng thơng qua c ij , ( i, j) G. T p các giá tr ∈ { f ij │( i, j) G } gi là lu ng trên m ng G n u th a mãn (i) 0 ≤ f ij ≤ c ij ∀ (i, j) ∈ G ∈ (ii) ∑ f ik = ∑ f kj ∀ k V \ { a; z} (,)i k∈ G (,)k j∈ G • Giá tr lu ng Cho lu ng f trên m ng G. Giá tr c a lu ng f là đi lưng v(f) = ∑ f ai = ∑ f iz (,)a i∈ G (,)i z∈ G 2.2. BÀI TỐN LU NG C C ĐI TRONG M NG 2.2.1. Phát bi u bài tốn lu ng c c đi • T rong th c t ta th ưng g p bài tốn g i là bài tốn tìm lu ng c c đi nh ư sau: Cho m ng G v i ngu n a, đích z và kh n ăng thơng qua c ij, (i, j) ∈ G. Trong s các lu ng trên m ng G tìm lu ng cĩ giá tr l n nh t. Bài tốn lu ng c c đi cĩ th bi u di n nh ư bài tốn quy ho ch tuy n tính v(f) = ∑ f ai = ∑ f iz → max (,)a i∈ G (,)i z∈ G
13. 13 vi điu ki n 0 ≤ f ij ≤ c ij ∀ (i, j) ∈ G ∈ ∑ f ik = ∑ f kj ∀ k V \ { a; z} (,)i k∈ G (,)k j∈ G 2.2.2. Lu ng c c đi và lát c t c c ti u Đnh ngh ĩa 2.1 Cho m ng G = (V,E,c) v i ngu n a và đích z. V i m i S, T ⊂ V, ký hi u t p các cung đi t S vào T là (S,T), t c (S,T) = { (i,j) ∈ E | i ∈ S & j ∈ T } N u S, T ⊂ V là phân ho ch c a V (S ∪ T = V & S ∩ T = Ø) và a∈ S, z ∈ T thì c p (S, T) g i là lát c t (ngu n-đnh). Kh n ăng thơng qua c a lát c t (S,T) là giá tr Cho lu ng f và lát c t (S,T) trên m ng G. V i m i S, T ⊂ V, ký hi u f(S,T) = ∑ fij (,)(,)i j∈ S T Đnh lý 2.1 Cho m ng G = (V,E,c) v i ngu n a và đích z, f = {f ij | (i, j) ∈G} là lu ng trên m ng G, (S,T) là lát c t c a G. Khi đĩ v(f) = f(S,T) – f(T,S) Đnh lý 2.2 ∈ Cho m ng G = (V,E,c) v i ngu n a và đích z, f = { f ij │( i, j) G } là lu ng trên m ng G, (S,T) là lát c t c a G. Khi đĩ, kh n ăng thơng qua c a lát c t (S,T) khơng nh h ơn giá tr c a lu ng f, t c là C(S, T) ≥ v(f) Đnh lý 2.3 ∈ Cho m ng G v i ngu n a và đích z, f = { f ij │( i, j) G } là lu ng trên m ng G, (S, T) là lát c t c a G. Khi đĩ,
14. 14 a. Nu C(S,T) = v(f), thì lu ng f đt giá tr c c đi và lát c t (S,T) đt kh n ăng thơng qua c c ti u. b. Đng th c C(S,T) = v(f) x y ra khi và ch khi (i) f = c ∀ ( i, j) ∈ ( S, T) và ij ij ∈ (ii) fij = 0 ∀ ( i, j) (T, S) 2.3. THU T TỐN TÌM LU NG C C ĐI TRONG M NG Đnh lý 2.4 (tính đúng c a thu t tốn Ford – Fullkerson) ∈ Cho m ng G = (V, E, c) v i ngu n a và đích z, f = { f ij | ( i, j) G} là lu ng nh n đưc khi k t thúc thu t tốn tìm lu ng c c đi. Khi đĩ, f là lu ng c c đi. 2.4 BÀI TỐN GHÉP C P 2.4.1 Phát bi u bài tốn Ta xét bài tốn sau. Cho t p X và Y. M i ph n t c a X cĩ th ghép v i m t s ph n t c a Y. V n đ đt ra là tìm cách ghép m i ph n t c a X v i m t s ph n t c a Y sao cho s c p ghép là l n nh t. 2.4.2 Mt s đnh ngh ĩa Cho đ th G. M t b ghép (matching) c a đ th G là m t t p h p các c nh (cung) c a G, đơi m t khơng k nhau. Bài tốn ghép c p (Matching problem) c a G là tìm b ghép cĩ s cnh (cung) l n nh t c a G. B ghép c c đi là b ghép cĩ s c nh (cung) l n nh t. L c l ưng ca b ghép c c đi kí hi u là α1(G). Cho G = (X,Y,E) là đơ n đ th l ưng phân B ghép đy đ t X vào Y là b ghép c c đi cĩ l c l ưng b ng lc l ưng c a X. B ghép hồn h o là b ghép đy đ t X vào Y và t Y vào X (suy ra card(X) = card(Y)). • Đư a bài tốn ghép c p v m ng chu n
15. 15 Xét đơ n đ th l ưng phân G = (X, Y, E). Ta s đư a bài tốn ghép c p cu đ th G v bài tốn lu ng c c đi nh ư sau. T đ th G ta xây d ng m ng G’ g m t p các đnh V’ = {s} ∪ X ∪ Y ∪ {t } Tp các cung E’ = {(s,x) │x ∈ X } ∪ E ∪ {(y,t) │y∈Y} và kh n ăng thơng qua ∈ Csx = 1 ∀ x X C = 1 ∀ y ∈ Y yt ∈ ∈ ∈ Cxy = + ∞ ∀ x X, y Y, (x,y) E. 2.4.3 Các đnh lý Đnh lý 2.5. Xét bài tốn ghép c p c a G = (X, Y, E) và bài tốn lu ng c c đi trên m ng G’. Khi đĩ (i) Mi lu ng f = {f xy } c a G’ sinh b i thu t tốn tìm lu ng cc đi xác đnh m t b ghép c a G. (ii) Mi lu ng c c đi f = {f xy } c a G’ sinh b i thu t tốn tìm lu ng c c đi xác đnh m t b ghép c c đi c a G. (iii) M i lu ng c c đi f = {f xy } c a G’ sinh b i thu t tốn tìm lu ng c c đi cĩ giá tr │X│xác đnh m t b ghép đy đ c a G. Đnh lý k t hơn Hall Sau đây ta nghiên c u điu ki n t n t i b ghép đy đ c a G = (X → Y, E). Nhà tốn h c ng ưi Anh Philip Hall đã phát bi u bài tốn d ưi d ng sau: Gi s X là t p nam, Y là t p n . Cung (x,y) ∈ E bi u di n quan h tươ ng h p c a x và y. Hãy tìm điu ki n đ m i nam cĩ th k t hơn v i mt n t ươ ng h p. Cho t p con S ⊂ X. Ký hi u R(S) = {y ∈ Y │ ∃ x∈ S: (x,y) ∈ E } Sau đây là k t qu c a Hall Đnh lý 2.6 ( đnh lý k t hơn Hall )
16. 16 Cho đ th đnh h ưng l ưng phân G = (X →Y,E). Khi đĩ t n t i b ghép đy đ khi và ch khi │S│≤│ R(S) │ ∀ S ⊂ X. E1 = {(a,x) │ x ∉ P x } Đnh lý 2.7 ( Đnh lí k t hơn Konig). Nu đ th l ưng phân đơ n G=(X, Y, E) là k- b c (các đnh đu cĩ b c là k>0), thì t n t i b ghép hồn h o. 2.4.4 Thu t tốn gi i bài tốn ghép c p Đnh ngh ĩa 2.2 Xét m t b ghép M c a G Các đnh trong M g i là các đnh đã ghép. Các c nh thu c M g i là c nh ghép. Các c nh khơng thu c M g i là c nh t do. Ý t ưng c a gi i thu t : Chúng ta b t đu v i 1 b ghép M b t kì. N u M ch a m i đnh trong X thì nĩ là 1 b ghép c c đi. N u khơng, ta ch n 1 đnh u ch ưa ghép thu c X và tìm ki m 1 cách h th ng cho 1 đưng m M vi g c u. Đ tìm b ghép t i đi c a m t đ th l ưng phân G, ta dùng gi i thu t đưng m sau: Gi i thu t đưng m (Augmenting path/ Hungarian Algorithm) Xây d ng b ghép M nh ư sau: Bưc 1: M i đnh thu c X là ch ưa ki m tra. Đt M = Ø Bưc 2: N u m i đnh thu c X ch a ghép đu đã ki m tra thì d ng. B ghép nh n đưc là c c đi. Bưc 3: N u khơng, ch n m t đnh u thu c X ch ưa ghép và ch ưa ki m tra đ xây d ng 1 cây pha g c u. Bưc 4: N u cây pha này là cây m thì qua b ưc 5, n u khơng, đánh d u u là đã ki m tra r i quay v b ưc 2. Bưc 5: Th c hi n th t c m r ng M b ng cây m nh ư sau: Trên đưng m , lo i b các cnh trong M và thêm vào các c nh ngồi M đ nh n đưc b ghép m i.
17. 17 Đánh d u m i đnh thu c X là ch ưa ki m tra. Quay v b ưc 2. Đnh lí 2.8 B ghép nh n đưc khi áp d ng gi i thu t đưng m vào đ th lưng phân G là c c đi. 2.4.5 Bài tốn ghép c p t i ưu Đnh ngh ĩa Cho tr ng đ l ưng phân G = (X,Y,E) v i tr ng s w(e) nguyên d ươ ng vi m i e ∈ E. Tìm b ghép c c đi M cĩ t ng tr ng s c a các c nh thu c M, kí hi u w(M), là nh nh t. Khơng m t tính t ng quát, ta gi thi t G = K n,n ( n u c n, cĩ th thêm các đnh gi và c nh gi v i tr ng s + ∞ ) v i X=Y={1,2, ,n }. Ký hi u A= [aij ] là ma tr n tr ng s , trong đĩ a ij là tr ng s c nh (i,j). Nh ư v y l i gi i c a bài tốn ghép c p t i ưu là tìm n ph n t ca ma tr n A th a (i) khơng cĩ hai ph n t n m trên m t hàng ho c m t c t (ii) tng các ph n t là nh nh t. Mt b n ph n t th a (i) và (ii), xác đnh b ghép c c đi t i ưu, g i là ghép c p t i ưu Vi m i hàng c a A ta tr đi ph n t nh nh t sao cho m i hàng cĩ ít nh t m t ph n t b ng 0. Sau đĩ v i m i c t c a A ta tr đi ph n t nh nh t sao cho m i c t cĩ ít nh t m t ph n t b ng 0. Ch n n ph n t 0 th a tính ch t (i)
18. 18 CH ƯƠ NG 3 NG D NG C A BÀI TỐN GHÉP C P 3.1 BÀI TỐN PHÂN CƠNG CƠNG VI C 3.1.1 Phát bi u bài tốn Trong 1 cơng ty, cĩ n ng ưi cơng nhân x 1, x 2, , x n và n cơng vi c y1, y2, ,y n. M i ng ưi cơng nhân là cĩ th làm đưc 1 ho c nhi u h ơn m t vi c. Tìm điu ki n đ t t c cơng nhân đu cĩ vi c phù h p. 3.1.2 Cách gi i Dng 1 đ th l ưng phân G = (X, Y, E) v i X = {x 1,x 2, , x n} bi u th n ng ưi cơng nhân, Y = { y 1, y2, ,y n} bi u th n cơng vi c và x i là kt h p v i y j n u và ch n u ng ưi cơng nhân x i là làm đưc cơng vi c y j. Bài tốn tr thành xác đnh cĩ hay khơng m t b ghép hồn h o trong đ th G. Áp d ng thu t tốn gi i bài tốn ghép c p đã trình bày trong ch ươ ng 2 3.2 BÀI TỐN X P TH I KHĨA BI U TR ƯNG H C 3.2.1 Phát bi u bài tốn Cho danh sách m t s giáo viên và danh sách các l p h c đưc d y bi các giáo viên này. Gi s r ng cĩ đ phịng h c đ cho các giáo viên th c hi n các ti t gi ng c a mình t i các l p nh ưng t i m t th i đim thì mt giáo viên ch cĩ th d y t i m t l p và cùng m t lúc t i m t l p khơng th cĩ nhi u h ơn m t giáo viên d y. Hãy b trí cho các giáo viên th c hi n các ti t gi ng c a mình t i các l p, sao cho s l ưng giáo viên tham gia là nhi u nh t. 3.2.2 Cách gi i Xây d ng đ th l ưng phân G = (X, Y, E). V i X là t p các giáo viên, Y là t p các l p h c. M t đnh x trong t p X đưc n i v i m t đnh y trong tp Y n u và ch n u giáo viên x cĩ ti t gi ng l p y.
19. 19 Vy vi c b trí cho các giáo viên th c hi n các ti t gi ng c a mình ti các l p, sao cho s l ưng giáo viên tham gia là nhi u nh t, tr thành xác đnh m t b ghép c c đi c a đ th G. 3.3 BÀI TỐN DCH V HƠN NHÂN 3.3.1 Phát bi u bài tốn Trong 1 cơng ty mơi gi i hơn nhân, cĩ m chàng trai đn đă ng kí tìm v . Đi v i m i chàng trai ta bi t các cơ gái mà anh ta v a ý. H i khi nào thì t ch c đám c ưi trong đĩ chàng trai nào c ũng sánh duyên v i cơ gái mà mình v a ý. 3.3.2 Cách gi i Ta xây d ng đ th v i các đnh bi u th các chàng trai và các cơ gái, cịn các cung bi u th s v a ý c a các chàng trai đi v i các cơ gái. Khi đĩ ta thu đưc m t đ th hai phía. 3.4. M NG V I NHI U ĐIM PHÁT VÀ NHI U ĐIM THU 3.4.1. Phát bi u bài tốn Cho n kho c n chuy n hàng s1,s 2, s n và m kho nh n hàng t1,t 2, ,t m. Hãy tìm m t ph ươ ng án chuy n hàng sao cho l ưng hàng đưc chuy n là ln nh t, cho bi t tr ưc s l ưng hàng c n chuy n c ũng nh ư kh n ăng ch a hàng m i kho và s hàng cĩ th chuy n t s i đn t j là c(i,j). 3.4.2. Cách gi i Bài tốn này cĩ th đư a v bài tốn m ng v i nhi u đim phát và đim thu. Ta coi các kho si là các đim phát, các kho nh n tj là các đim thu. Đng th i đư a vào m t đim phát gi s n i vi t t c các đim phát và mt đim thu gi t đưc n i v i các đim thu. 3.5. BÀI TỐN V I KH N ĂNG THƠNG QUA C A CÁC CUNG VÀ CÁC ĐNH 3.5.1. Phát bi u bài tốn Hãy tìm m t ph ươ ng án v n chuy n d u t m t b ch a s t i b nh n t thơng qua h th ng đưng ng d n d u, sao cho l ưng d u chuy n
20. 20 đưc là nhi u nh t. Cho bi t tr ưc l ưng d u l n nh t cĩ th b ơm qua m i đưng ng và qua m i đim n i gi a các ng. 3.5.2 Cách gi i Xây d ng đ th G = (V,E) , v i V là t p các đnh c a đ th g m s, t và t p các đim n i, cịn E là t p các cung c a đ th g m các đưng ng dn d u. Trong G, v i m i đnh v thu c V thì t ng lu ng đi vào đnh v khơng đưc v ưt quá kh n ăng thơng qua d(v) c a nĩ, t c là ∑ f (,)w v ≤ d(v) w∈ V Cn ph i tìm lu ng c c đi gi a s và t trong m ng nh ư v y. Xây d ng m t m ng G′ sao cho: m i đnh v ca G t ươ ng ng v i hai đnh v+ và v - trong G′, m i cung (u,v ) trong G t ươ ng ng v i cung ( u - ,v +) trong G′, m i cung (v, w) trong G ng v i cung ( v -, w +) trong G’. Ngồi ra, m i cung ( v+ , v -) trong G’ cĩ kh n ăng thơng qua là d(v), t c là bng kh n ăng thơng qua c a đnh v trong G. Do lu ng đi vào đnh v+ ph i đi qua cung ( v+ , v -) v i kh n ăng thơng qua d(v), nên lu ng c c đi trong G’ s b ng lu ng c c đi trong G vi kh n ăng thơng qua c a các cung và các đnh. 3.6. BÀI TỐN V N T I 3.6.1 Phát bi u bài tốn Ng ưi ta c n v n chuy n hàng hĩa t các đim cung ng đn các đim tiêu th . Cho bi t kh n ăng cung ng, yêu c u tiêu th và đơ n giá v n chuy n. Tìm ph ươ ng án v n chuy n đm b o yêu c u tiêu th v i chi phí th p nh t. Gi s cĩ m đim cung ng và n đim tiêu th . Kí hi u Ai là l ưng hàng hĩa cĩ đim cung ng i, i = 1, , m Bj là l ưng hàng hĩa yêu c u đim tiêu th j, j = 1, , n th a mãn m n ∑ Ai = ∑ Bj i=1 j=1
21. 21 cij là đơ n giá v n chuy n t đim cung ng i đn đim tiêu th j, i =1, ,m và j = 1, , n xij là l ưng hàng v n chuy n t đim cung ng i đn đim tiêu th j, i =1, ,m và j = 1, , n Bài tốn v n t i cĩ d ng sau m n ∑ ∑ cij xij → min i=1 j=1 n ∑ xij = A i , i = 1, , m (TP) j=1 m ∑ xij = B j , j =1, , n i=1 3.6.2 Cách gi i Đư a bài tốn v n t i v m ng chu n Ta xây d ng m ng N(V, E) nh ư sau: Tp các đnh V= { s 0, s 1, ,s m, t 0, t 1, ,t n} v i đnh ngu n s 0 và đnh đích t0. T p các cung và kh n ăng thơng qua cùng chi phí bao g m (s 0, s i) v i kh n ăng thơng qua A i và chi phí là 0, i =1, ,m (t j, t 0) v i kh n ăng thơng qua B j và chi phí là 0, j = 1, , n (s i, t j) v i kh n ăng thơng qua + ∞ và chi phí là c ij , i =1, ,m và j = 1, , n 3.7 V M T BÀI TỐN T I ƯU R I R C Trong m c này ta s trình bày thu t tốn đưc xây d ng d a trên thu t tốn tìm lu ng c c đi đ gi i m t bài tốn t i ưu r i r c là mơ hình tốn h c cho m t s bài tốn t i ưu t ng h p. Xét bài tốn t i ưu r i r c. n f (x , x , , x ) = x min (3.1) 1 2 n max ∑ ij → 1≤i ≤ m j=1 vi điu ki n
22. 22 n = = ∑ aijx ij pi ,i 1,2, m, (3.2) j=1 = xij 0 ho c 1, j = 1,2, , n (3.3) ∈{ } = = trong đĩ aij ,1,0 i 2,1 , , m; j 2,1 , , n, pi -nguyên d ươ ng, i = 1,2, , m Bài tốn (3.1) - (3.3) là mơ hình tốn h c cho nhi u bài tốn t i ưu t h p th c t . D ưi đây ta d n ra m t vài ví d đin hình. Bài tốn phân nhĩm sinh ho t Cĩ m sinh viên và n nhĩm sinh ho t chuyên đ. V i m i sinh viên i, bi t aij = 1, n u sinh viên i cĩ nguy n v ng tham gia vào nhĩm chuyên đ j, aij = 0, n u ng ưc l i. Cho dãy pi là s l ưng nhĩm chuyên đ mà h cĩ nguy n v ng tham gia và b o đm m i sinh viên i ph i tham gia đúng pi nhĩm. Hãy tìm cách b trí sinh viên h c đ các chuyên đ phù h p v i nguy n v ng c a h đng th i các chuyên đ cĩ s l ưng sinh viên theo h c chênh l ch nhau càng ít càng t t. Bài tốn l p l ch cho h i ngh Mt h i ngh cĩ m ti u ban, m i ti u ban c n sinh ho t trong m t ngày t i phịng h p phù h p v i nĩ. Cĩ n phịng h p dành cho vi c sinh ho t c a các ti u ban. Bi t aij = 1, n u phịng h p i là thích h p v i ti u ban j, aij = 0, n u ng ưc l i, i = 1,2, ,m, j = 1,2, ,n. Hãy b trí các phịng h p cho các ti u ban sao cho hi ngh k t thúc sau ít ngày làm vi c nh t. B đ 1. Bài tốn (3.1)-(3.3) cĩ ph ươ ng án t i ưu khi và ch khi n ≥ = ∑ aij pi ,i 1,2, m, (3.4) j=1
23. 23 B đ sau đây cho th y m i liên h gi a lu ng c c đi trong m ng G (k) và ph ươ ng án c a bài tốn (3.1)-(3.3). B đ 2. Gi s đi v i s nguyên d ươ ng k nào đĩ, lu ng c c đi nguyên ξ * * trong m ng G (k) cĩ giá tr là σ . Khi đĩ X = (x ij )mxn vi các thành ph n đưc xác đnh theo cơng th c * = ξ * = = x ij (ui, w j ), i 2,1 , , m; j 2,1 , , n là ph ươ ng án c a bài tốn (3.1)-(3.3) * * B đ 3. Gi s X = (x ij ) là ph ươ ng án t i ưu và k* là giá tr t i ưu c a bài tốn (3.1) – (3.3). Khi đĩ lu ng c c đi trong m ng G (k) cĩ giá tr σ . B đ 4. N u k = m thì lu ng c c đi trong m ng G (m) cĩ giá tr là σ .
24. 24 KT LU N Lu n v ăn này đưc vi t v i mong mu n nghiên c u sâu nh ng ng dng c a bài tốn ghép c p và bài tốn lu ng c c đi . Quá trình nghiên c u lu n v ăn đã đt đưc nh ng k t qu sau: - V i b n thân đã h th ng đưc m t s ki n th c v Lý Thuy t Đ Th và hi u sâu h ơn v bài tốn ghép c p, bài tốn lu ng c c đi - Xây d ng đưc m t s ng d ng các bài tốn gi i đưc b ng cách vn d ng nh ng k t qu c a bài tốn ghép c p và bài tốn lu ng c c đi . - H th ng bài tốn xây d ng d a trên các ng d ng c a bài tốn ghép c p và bài tốn lu ng c c đi ch ưa th t s đa d ng nên đây là h ưng phát tri n c a lu n v ăn.