Tóm tắt luận văn thạc sĩ khoa học: Bài toán ghép căp và ứng dụng

Chia sẻ: Lang Nguyen | Ngày: | Loại File: PDF | Số trang:24

Thêm vào BST

Báo xấu

261
lượt xem 33
download

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

Tóm tắt luận văn thạc sĩ khoa học: Bài toán ghép cặp và ứng dụng nhằm trình bày về những kiến thức cơ bản về lý thuyết đồ thị, giới thiệu bài toán cặp, bài toán luồng cực đại và các định lý, thuật toán liên quan đến những bài toán này, ứng dụng của bài toán cặp.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt luận văn thạc sĩ khoa học: Bài toán ghép căp và ứng dụng

1 B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG NGUY N TH ÁNH ĐÀO BÀI TOÁN GHÉP C P VÀ NG D NG Chuyên ngành : PHƯƠNG PHÁP TOÁ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 Công trình ñư c hoà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 h p 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 M Đ U 1. Đ T V N Đ CHUNG V Đ TÀI NGHIÊN C U Đ tài “Bài toá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 c a 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. Đi u ki n ñ m b o cho vi c hoà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 hoà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 nh ng n i 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 toà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 h c sinh khá và gi i ñang là nhu c u th c t trong d y h c toá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 d ng chuyên ñ này ñ gi i là không nhi u. Chuyên ñ Lý Thuy t Đ Th có m t ñ c ñi m n i b c là vi c gi i các d ng toá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 toá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 toá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 toán này h p d n, lý thú và ñ y b t ng . Đi u 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 toán. Vì v y,
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 toá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 toán qu c t . Đi u này phù h p v i xu hư ng ñưa toán h c v áp d ng vào trong th c t cu c s ng. M t trong nh ng bài toá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 c a 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 m t ng d ng khác c a m ng là “ Bài toá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 toá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 toá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 toán ghép c p 4.2. Ph m vi nghiên c u L y Lý Thuy t Đ Th làm cơ s nghiên c u bài toán ghép c p và ñưa ra phương pháp gi i c a bài toá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 toá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 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 TOÁN GHÉP C P Gi i thi u bài toán ghép c p, bài toán lu ng c c ñ i và các ñ nh lý, thu t toán liên quan ñ n bài toán này. Chương 3- NG D NG C A BÀI TOÁN GHÉP C P Trình bày các ng d ng c a bài toán ghép c p, bài toán lu ng c c ñ i trong các v n ñ th c t và ng d ng c a bài toán này .
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à t p E các c nh có hư ng g i là cung. M i cung e ∈ E ñư c liên k t v i m t 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 m t 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 Đ 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 Kn 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 = ({V1 ,V2 } , 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 ') g i là ñ th con c a G n u V '⊂V & E'⊂ E . N u 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 = (V1 , E1 ) G2 = (V2 , E2 ) và ñư c g i là ñ ng c u nhau n u t n t i song ánh f : V1 → V2 và g : E1 → E2 th a mãn ∀e ∈ E1 : e = (v, w) ⇔ g(e)=(f(v),f(w)) . C p 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 = (V1 , E1 ) và G2 = (V2 , E2 ) ñ ng c u v i nhau n u t n t i song ánh f : V1 → V2 th a mãn ∀u , v ∈ V1 : u k v ⇔ f(u) k f(v). Đ nh lý 1.2 Cho G1 = (V1 , E1 ) và G2 = (V2 , E2 ) là hai ñ th ñ ng c u. Khi ñó: (i) G1 và G2 có s c nh và s ñ nh b ng nhau.
8 (ii) V i m i s t nhiên k, s ñ nh b c k c a G1 và G2 b ng 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 c a chúng cũng ñ ng c u nhau. 1.2.8. Đ th ph ng Đ nh nghĩa 1.13 M t ñ 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. M i b n ñ trên m t ph ng có th bi u di n b ng m t ñ 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 ñi m không ñư c coi là k nhau. Đ th nh n ñư c b ng 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. B C, 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 • B c: 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). N u ñ nh có khuyên thì khuyên ñư c tính là 2 khi tính b c, như v y: 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. B c 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 ) . • N a b c: Cho ñ th có hư ng G = (V,E), v ∈V . N a b c ra c a ñ nh v, kí hi u d0(v) là s cung ñi ra t ñ nh v (v là ñ nh ñ u). N a b c vào c a ñ nh v, kí hi u dI(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.card(E) . v∈V H qu 1.1 S ñ nh b c l c a ñ th vô hư ng là s ch n. M nh ñ 1.1 M i ñ nh c a ñ th Kn có b c là n-1 và Kn n(n − 1) có c nh. 2 M nh ñ 1.2 Cho ñ th lư ng phân ñ K m ,n = ({V1 ,V2 } , E ) . 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à K m ,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 Dãy µ t ñ nh v ñ n ñ nh w là dãy các ñ nh và c nh n i ti p nhau b t ñ 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: µ = ( v, e1 , v1 , e2 , v2 ,..., vn−1 , en , 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 c p ñ 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 Đ 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 ≤ 3v − 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 ≤ 2v − 4.
12 CHƯƠNG 2 BÀI TOÁN GHÉP C P 2.1. M NG • M ng M ng 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 cij 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 cij, ( i, j) ∈ G. T p các giá tr { fij│( i, j) ∈G } g i là lu ng trên m ng G n u th a mãn (i) 0 ≤ fij ≤ cij ∀ (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 TOÁN LU NG C C Đ I TRONG M NG 2.2.1. Phát bi u bài toán lu ng c c ñ i • Trong th c t ta thư ng g p bài toán g i là bài toá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 cij, (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 toán lu ng c c ñ i có th bi u di n như bài toán quy ho ch tuy n tính v(f) = ∑ ( a ,i )∈G f ai = ∑ ( i , z )∈G f iz → max
13 v i ñi u ki n 0 ≤ fij ≤ cij ∀ (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) = ∑ ( i , j )∈( S ,T ) fij Đ nh lý 2.1 Cho m ng G = (V,E,c) v i ngu n a và ñích z, f = {fij | (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 = { fij│( 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 = { fij│( i, j) ∈ G } là lu ng trên m ng G, (S, T) là lát c t c a G. Khi ñó,
14 a. N u 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) fij = cij ∀ ( i, j) ∈( S, T) và (ii) fij = 0 ∀ ( i, j) ∈(T, S) 2.3. THU T TOÁN TÌM LU NG C C Đ I TRONG M NG Đ nh lý 2.4 (tính ñúng c a thu t toán Ford – Fullkerson) Cho m ng G = (V, E, c) v i ngu n a và ñích z, f = { fij | ( i, j) ∈G} là lu ng nh n ñư c khi k t thúc thu t toán tìm lu ng c c ñ i. Khi ñó, f là lu ng c c ñ i. 2.4 BÀI TOÁN GHÉP C P 2.4.1 Phát bi u bài toán Ta xét bài toá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 M t 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 toán ghép c p (Matching problem) c a G là tìm b ghép có s c nh (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 c a 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 l c lư ng c a X. B ghép hoà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 toán ghép c p v m ng chu n
15 Xét ñơn ñ th lư ng phân G = (X, Y, E). Ta s ñưa bài toán ghép c p cu ñ th G v bài toá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 } T p các cung E’ = {(s,x)│x ∈X } ∪ E ∪ {(y,t)│y ∈ Y} và kh năng thông qua Csx = 1 ∀ x ∈X Cyt = 1 ∀ y ∈Y Cxy = +∞ ∀ x ∈X, y∈Y, (x,y) ∈E. 2.4.3 Các ñ nh lý Đ nh lý 2.5. Xét bài toán ghép c p c a G = (X, Y, E) và bài toán lu ng c c ñ i trên m ng G’. Khi ñó (i) M i lu ng f = {fxy} c a G’ sinh b i thu t toán tìm lu ng c c ñ i xác ñ nh m t b ghép c a G. (ii) M i lu ng c c ñ i f = {fxy} c a G’ sinh b i thu t toá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 = {fxy} c a G’ sinh b i thu t toá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 ñi u ki n t n t i b ghép ñ y ñ c a G = (X→ Y, E). Nhà toán h c ngư i Anh Philip Hall ñã phát bi u bài toá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 ñi u ki n ñ m i nam có th k t hôn v i m t 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 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 ∉ Px } Đ nh lý 2.7 (Đ nh lí k t hôn Konig). N u ñ 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 hoàn h o. 2.4.4 Thu t toán gi i bài toá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 v i 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 c nh trong M và thêm vào các c nh ngoài M ñ nh n ñư c b ghép m i.
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 toá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 v i 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 = Kn,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 ñó aij là tr ng s c nh (i,j). Như v y l i gi i c a bài toán ghép c p t i ưu là tìm n ph n t c a 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) t ng các ph n t là nh nh t. M t 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 V i 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 CHƯƠNG 3 NG D NG C A BÀI TOÁN GHÉP C P 3.1 BÀI TOÁN PHÂN CÔNG CÔNG VI C 3.1.1 Phát bi u bài toán Trong 1 công ty, có n ngư i công nhân x1, x2, …, xn và n công vi c y1, y2,…,yn. 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 ñi u ki n ñ t t c công nhân ñ u có vi c phù h p. 3.1.2 Cách gi i D ng 1 ñ th lư ng phân G = (X, Y, E) v i X = {x1,x2, …, xn} bi u th n ngư i công nhân, Y = { y1,y2,…,yn} bi u th n công vi c và xi là k t h p v i yj n u và ch n u ngư i công nhân xi là làm ñư c công vi c yj. Bài toán tr thành xác ñ nh có hay không m t b ghép hoàn h o trong ñ th G. Áp d ng thu t toán gi i bài toán ghép c p ñã trình bày trong chương 2 3.2 BÀI TOÁN X P TH I KHÓA BI U TRƯ NG H C 3.2.1 Phát bi u bài toá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 b i 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 ñi m thì m t 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 t p Y n u và ch n u giáo viên x có ti t gi ng l p y.
19 V y 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 t i 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 TOÁN D CH V HÔN NHÂN 3.3.1 Phát bi u bài toá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 ĐI M PHÁT VÀ NHI U ĐI M THU 3.4.1. Phát bi u bài toán Cho n kho c n chuy n hàng s1,s2,.. sn và m kho nh n hàng t1,t2,.. ,tm. Hãy tìm m t phương án chuy n hàng sao cho lư ng hàng ñư c chuy n là l n 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 si ñ n tj là c(i,j). 3.4.2. Cách gi i Bài toán này có th ñưa v bài toán m ng v i nhi u ñi m phát và ñi m thu. Ta coi các kho si là các ñi m phát, các kho nh n tj là các ñi m thu. Đ ng th i ñưa vào m t ñi m phát gi s n i v i t t c các ñi m phát và m t ñi m thu gi t ñư c n i v i các ñi m thu. 3.5. BÀI TOÁ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 toá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 ñư 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 ñi m 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 ñi m n i, còn E là t p các cung c a ñ th g m các ñư ng ng d n 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 C n 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 c a 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’. Ngoài ra, m i cung (v+ , v -) trong G’ có kh năng thông qua là d(v), t c là b ng 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 v i kh năng thông qua c a các cung và các ñ nh. 3.6. BÀI TOÁN V N T I 3.6.1 Phát bi u bài toán Ngư i ta c n v n chuy n hàng hóa t các ñi m cung ng ñ n các ñi m 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 ñi m cung ng và n ñi m tiêu th . Kí hi u Ai là lư ng hàng hóa có ñi m cung ng i, i = 1,…, m Bj là lư ng hàng hóa yêu c u ñi m tiêu th j, j = 1,…, n th a mãn m n ∑i =1 Ai = ∑ j =1 Bj