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 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 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 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 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 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 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 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 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 học 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 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 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ờ. Đ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 tố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 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ế. Điều 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. Một 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 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 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 Lấy 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 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 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 1V và 2V sao cho mỗi cạnh của nĩ liên kết với một đỉnh thuộc 1V và một đỉnh thuộc 2V . Ký hiệu { }1 2( , , )G V V 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ị 1 1 1( , )G V E= và 2 2 2( , )G V E= được gọi là đẳng cấu nhau nếu tồn tại song ánh 1 2:f V V→ và 1 2:g E E→ thỏa mãn 1 : ( ,w) g(e)=(f(v),f(w))e E e v∀ ∈ = ⇔ . Cặp hàm f và g gọi là một đẳng cấu từ 1G đến 2G . Định lý 1.1 Hai đơn đồ thị 1 1 1( , )G V E= và 2 2 2( , )G V E= đẳng cấu với nhau nếu tồn tại song ánh 1 2:f V V→ thỏa mãn 1, :u v V∀ ∈ u kề v ⇔ f(u) kề f(v). Định lý 1.2 Cho 1 1 1( , )G V E= và 2 2 2( , )G V E= là hai đồ thị đẳng cấu. Khi đĩ: (i) 1G và 2G 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 1G và 2G bằng nhau, số chu trình sơ cấp chiều dài k của 1G và 2G 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à ( ) 2. ard(E) v V d v c ∈ =∑ . 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ị nK cĩ bậc là n-1 và nK cĩ ( 1) 2 n n − cạnh. Mệnh đề 1.2 Cho đồ thị lưỡng phân đủ { }( ) , 1 2, ,m nK V V E= . Khi đĩ mỗi đỉnh trong tập 1V cĩ bậc là n, mỗi đỉnh trong tập 2V cĩ bậc là m và ,m nK 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: ( )1 1 2 2 1, , , , ,..., , ,wn nv e v e v v eµ −= trong đĩ , 1, 1iv i n= − là các đỉnh trên dãy và , 1,ie i 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: ( )( 1) 2 n k n k n k m − − +− ≤ ≤ Hệ quả 1.2 Mọi đơn đồ thị n đỉnh với số cạnh lớn hơn ( 1)( 2) 2 n n− − là liên thơng. 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 đỉnh và đai g, khơng cĩ đỉnh treo. Khi đĩ ta cĩ ( 2) 2 g e v g ≤ − − ( 3)g ≥ . Hệ quả 1.3 Cho G là đơn đồ thị phẳng liên thơng với e cạnh và v đỉnh ( 3v ≥ ), khơng cĩ đỉnh treo Khi đĩ ta cĩ: 3 6.e v≤ − Hệ quả 1.4 Cho G là đơn đồ thị phẳng liên thơng với e cạnh và v đỉnh ( 3v ≥ ), khơng cĩ đỉnh treo và khơng cĩ chu trình độ dài 3. Khi đĩ ta cĩ: 2 4.e v≤ − 12 CHƯƠNG 2 BÀI TỐ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) ∑ ∈Gki ),( f ik = ∑ ∈Gjk ),( f kj ∀ k ∈ V \ { a; z} • 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) = ∑ ∈Gia ),( f ai = ∑ ∈Gzi ),( f iz 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 • Trong 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 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 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) = ∑ ∈Gia ),( f ai = ∑ ∈Gzi ),( f iz → max 13 với điều kiện 0 ≤ fij ≤ cij ∀ (i, j) ∈ G ∑ ∈Gki ),( f ik = ∑ ∈Gjk ),( f kj ∀ k ∈ V \ { a; z} 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) = ∑ ∈ ),(),( TSji 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 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 = { fij | ( 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 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 tố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 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 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 } 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 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) Mọi luồng f = {fxy} 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ủa G. (ii) Mọi luồng cực đại f = {fxy} 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 = {fxy} 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 điều 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 đ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 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 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 ngồ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 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 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 tố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 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 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 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 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 TỐN DỊCH 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 ĐIỂM PHÁT VÀ NHIỀU ĐIỂM THU 3.4.1. Phát biểu bài tố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 tốn này cĩ thể đưa về bài tố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 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 đượ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à ∑ ∈Vw vwf ),( ≤ d(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’. Ngồ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 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 đ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 i 1 Ai = ∑ = n j 1 Bj 21 cij là đơn giá vận chuyển từ điểm cung ứng i đến điểm tiêu thụ j, i =1,…,m và j = 1,.., n xij là lượng hàng vận chuyển từ điểm cung ứng i đến điểm tiêu thụ j, i =1,…,m và j = 1,.., n Bài tốn vận tải cĩ dạng sau ∑ = m i 1 ∑ = n j 1 cijxij → min ∑ = n j 1 xij = Ai , i = 1,…, m (TP) ∑ = m i 1 xij = Bj , j =1,.., n 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: Tập các đỉnh V= { s0, s1,…,sm, t0, t1, …,tn} với đỉnh nguồn s0 và đỉnh đích t0. Tập các cung và khả năng thơng qua cùng chi phí bao gồm (s0, si) với khả năng thơng qua Ai và chi phí là 0, i =1,…,m (tj, t0) với khả năng thơng qua Bj và chi phí là 0, j = 1,.., n (si, tj) với khả năng thơng qua +∞ và chi phí là cij, 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. =),...,,( 21 nxxxf max 1 mi≤≤ ∑ = n j 1 xij → min (3.1) với điều kiện 22 ∑ = n j 1 ,,...2,1, mipxa iijij == (3.2) 0=ijx hoặc 1, j = 1,2, ..., n (3.3) trong đĩ ija { } ipnjmi ,,...,2,1;,...,2,1,1,0 ==∈ -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ụ điển 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ị Một 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 hội 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 j 1 ,,...2,1, mipa iij =≥ (3.4) 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 với các thành phần được xác định theo cơng thức njmiwux jiij ,...,2,1;,...,2,1),( ,** === ξ 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 KẾT 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 dụng 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 vận 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.