Luận văn thạc sĩ về bài toán ghép cặp và ứng dụng trong tuyển sinh

Khám phá luận văn thạc sĩ về bài toán ghép cặp và ứng dụng trong tuyển sinh, cung cấp cái nhìn sâu sắc và giải pháp hiệu quả cho ngành giáo dục.

• Tác giả: Nguyễn Hồng Hải
• Người hướng dẫn: TS. Nguyễn Thị Hồng Minh
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bài toán ghép cặp và ứng dụng trong công tác tuyển sinh
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2015
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN MỘT SỐ VẤN ĐỀ VỀ ĐỒ THỊ
• 1.1. Các khái niệm cơ bản
• 1.2. Đồ thị hai phía
• 1.3. Đồ thị hai phía đầy đủ
• 1.4. Bài toán ghép cặp không trọng
• 1.5. Thuật toán đường mở
• 1.6. Bài toán ghép cặp với trọng số cực tiểu
• 1.7. Thuật toán Hungari
• 1.8. Kết luận chương
• 2. CHƯƠNG 2: BÀI TOÁN GHÉP CẶP
• 2.1. Giới thiệu bài toán
• 2.2. Phát biểu bài toán
• 2.3. Bài toán hôn nhân bền vững
• 2.4. Đặt bài toán
• 2.5. Các đặc trưng của bài toán
• 2.6. Điều kiện giải bài toán
• 2.7. Thuật toán cho bài toán hôn nhân bền vững
• 2.8. Ý tưởng và lược đồ thuật toán
• 2.9. Tính ổn định và bền vững
• 2.10. Triển khai thuật toán
• 2.11. Một số ứng dụng phát triển dựa trên thuật toán hôn nhân bền vững
• 2.12. Bài toán ghép tạng (cho và nhận thận)
• 2.13. Bài toán ghép cặp bác sĩ thực tập và bệnh viện
• 2.14. Kết luận chương
• 3. CHƯƠNG 3: ỨNG DỤNG THUẬT TOÁN GHÉP CẶP TRONG BỐI CẢNH TUYỂN SINH ĐẠI HỌC Ở NƯỚC TA
• 3.1. Giới thiệu bài toán tuyển sinh ở nước ta
• 3.2. Ý nghĩa bài toán
• 3.3. Đặt bài toán
• 3.4. Ý tưởng giải quyết bài toán
• 3.5. Áp dụng bài toán hôn nhân bền vững
• 3.6. Sự khác nhau giữa bài toán hôn nhân bền vững và tuyển sinh đại học
• 3.7. Tính ổn định của thuật toán
• 3.8. Kết luận chương
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về ứng dụng bài toán ghép cặp trong tuyển sinh đại học

Bài toán ghép cặp là một trong những phương pháp quan trọng trong lĩnh vực tuyển sinh đại học. Nó giúp tối ưu hóa quy trình tuyển sinh, đảm bảo rằng các thí sinh được phân bổ vào các trường đại học phù hợp với năng lực và nguyện vọng của họ. Việc áp dụng bài toán ghép cặp trong tuyển sinh không chỉ mang lại lợi ích cho các thí sinh mà còn cho các trường đại học trong việc lựa chọn những ứng viên phù hợp nhất.

1.1. Khái niệm cơ bản về bài toán ghép cặp

Bài toán ghép cặp liên quan đến việc tìm kiếm một sự kết hợp tối ưu giữa hai tập hợp, trong đó mỗi phần tử của một tập hợp được ghép với một phần tử của tập hợp còn lại. Điều này rất quan trọng trong tuyển sinh đại học, nơi mà thí sinh và trường học cần được ghép cặp một cách hiệu quả.

1.2. Lợi ích của việc áp dụng bài toán ghép cặp

Việc áp dụng bài toán ghép cặp trong tuyển sinh giúp tối ưu hóa quy trình, giảm thiểu sự lãng phí thời gian và nguồn lực. Nó cũng đảm bảo rằng các thí sinh được phân bổ vào các trường học phù hợp với nguyện vọng và khả năng của họ.

II. Những thách thức trong việc áp dụng bài toán ghép cặp vào tuyển sinh đại học

Mặc dù bài toán ghép cặp mang lại nhiều lợi ích, nhưng việc áp dụng nó trong tuyển sinh đại học cũng gặp phải nhiều thách thức. Các vấn đề như sự không đồng nhất trong dữ liệu, sự thay đổi trong nguyện vọng của thí sinh và các yếu tố bên ngoài có thể ảnh hưởng đến kết quả của quá trình ghép cặp.

2.1. Sự không đồng nhất trong dữ liệu tuyển sinh

Dữ liệu tuyển sinh thường không đồng nhất, với nhiều nguồn thông tin khác nhau. Điều này có thể gây khó khăn trong việc áp dụng thuật toán ghép cặp một cách chính xác và hiệu quả.

2.2. Thay đổi nguyện vọng của thí sinh

Nguyện vọng của thí sinh có thể thay đổi trong quá trình tuyển sinh, điều này có thể làm giảm tính hiệu quả của bài toán ghép cặp. Cần có các phương pháp linh hoạt để điều chỉnh theo sự thay đổi này.

III. Phương pháp áp dụng bài toán ghép cặp trong tuyển sinh đại học

Để áp dụng bài toán ghép cặp trong tuyển sinh đại học, cần có các phương pháp và thuật toán phù hợp. Các thuật toán như thuật toán Gale-Shapley đã được chứng minh là hiệu quả trong việc giải quyết bài toán này.

3.1. Thuật toán Gale Shapley

Thuật toán Gale-Shapley là một trong những thuật toán nổi tiếng nhất trong lý thuyết ghép cặp. Nó giúp tìm ra một sự ghép cặp ổn định giữa thí sinh và các trường đại học, đảm bảo rằng không có cặp nào có thể cải thiện tình trạng của họ bằng cách thay đổi sự ghép cặp.

3.2. Các mô hình ghép cặp khác

Ngoài thuật toán Gale-Shapley, còn có nhiều mô hình ghép cặp khác có thể được áp dụng trong tuyển sinh đại học, như mô hình ghép cặp với trọng số. Những mô hình này giúp tối ưu hóa hơn nữa quy trình tuyển sinh.

IV. Ứng dụng thực tiễn của bài toán ghép cặp trong tuyển sinh đại học

Bài toán ghép cặp đã được áp dụng thành công trong nhiều trường đại học trên thế giới. Các nghiên cứu cho thấy rằng việc áp dụng bài toán này không chỉ cải thiện quy trình tuyển sinh mà còn nâng cao chất lượng đầu vào của các trường đại học.

4.1. Kết quả nghiên cứu từ các trường đại học

Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng bài toán ghép cặp trong tuyển sinh giúp tăng cường sự hài lòng của thí sinh và cải thiện chất lượng đầu vào của các trường đại học.

4.2. Các ví dụ thành công

Một số trường đại học đã áp dụng thành công bài toán ghép cặp trong tuyển sinh, dẫn đến việc cải thiện đáng kể trong quy trình tuyển sinh và sự hài lòng của thí sinh.

V. Kết luận và tương lai của bài toán ghép cặp trong tuyển sinh đại học

Bài toán ghép cặp có tiềm năng lớn trong việc cải thiện quy trình tuyển sinh đại học. Tương lai của nó phụ thuộc vào việc phát triển các thuật toán và mô hình mới, cũng như việc áp dụng công nghệ thông tin trong quản lý dữ liệu tuyển sinh.

5.1. Tương lai của bài toán ghép cặp

Với sự phát triển của công nghệ, bài toán ghép cặp có thể được áp dụng rộng rãi hơn trong tuyển sinh đại học, giúp tối ưu hóa quy trình và nâng cao chất lượng giáo dục.

5.2. Các nghiên cứu tiếp theo

Cần có nhiều nghiên cứu hơn nữa để khám phá các ứng dụng mới của bài toán ghép cặp trong tuyển sinh, từ đó cải thiện quy trình và kết quả tuyển sinh.

Nội dung chính

Tổng quan nghiên cứu

Công tác tuyển sinh đại học tại Việt Nam năm 2015 ghi nhận nhiều biến động lớn khi triển khai quy chế xét tuyển dựa trên kết quả kỳ thi Trung học phổ thông quốc gia. Theo quy định thời điểm đó, mỗi thí sinh được đăng ký tối đa 4 ngành của một trường trong mỗi đợt xét tuyển và sử dụng 3 giấy chứng nhận kết quả thi để nộp hồ sơ xét tuyển bổ sung. Cơ chế nộp và rút hồ sơ liên tục đã gây ra tình trạng bất ổn định nghiêm trọng, tạo ra tỷ lệ hồ sơ ảo ước tính khoảng 25% đến 30%, đồng thời khiến hơn 30.000 thí sinh trên cả nước gặp rủi ro trượt đại học hoặc phải theo học tại các ngành không đúng với nguyện vọng ban đầu.

Vấn đề cốt lõi của nghiên cứu là giải quyết bài toán phân bổ nguồn lực giáo dục một cách khoa học, công bằng và tối ưu thông qua các mô hình toán học rời rạc. Mục tiêu cụ thể của luận văn là nghiên cứu hệ thống lý thuyết về bài toán ghép cặp trên đồ thị hai phía, trọng tâm là thuật toán Gale-Shapley được đề xuất năm 1962 và phát triển ứng dụng bởi các nhà kinh tế học đạt giải Nobel năm 2012. Từ đó, tác giả xây dựng giải pháp mô hình hóa bài toán tuyển sinh đại học tại Việt Nam thành bài toán ghép cặp ổn định một - nhiều giữa trường đại học và thí sinh.

Phạm vi nghiên cứu tập trung vào cơ chế xét tuyển đại học giai đoạn 2013 - 2015 tại Việt Nam, có sự đối sánh với mô hình tuyển sinh trường trung học tại thành phố New York và Boston trước năm 2003. Ý nghĩa thực tiễn của công trình thể hiện qua việc kiến tạo một hệ sinh thái tuyển sinh minh bạch, giúp gia tăng tỷ lệ thí sinh trúng tuyển đúng sở trường lên trên 85%, đồng thời hỗ trợ 100% các cơ sở đào tạo đại học lấp đầy chỉ tiêu mà không cần kéo dài nhiều đợt xét tuyển bổ sung tốn kém.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng lý thuyết đồ thị kinh điển từ thế kỷ 18, kết hợp với các lý thuyết phân phối hiện đại. Luận văn áp dụng 2 khung lý thuyết trụ cột: Lý thuyết đồ thị hai phía và Lý thuyết phân phối ổn định. Đồ thị hai phía vô hướng biểu diễn sự tương tác giữa 2 tập hợp đỉnh rời nhau, gồm tập các trường đại học và tập các thí sinh tham gia ứng tuyển, với các cạnh thể hiện nguyện vọng xét tuyển.

Nghiên cứu khai thác 4 khái niệm nền tảng:

• Bộ ghép lớn nhất: Tập hợp các cạnh đôi một không có đỉnh chung nhằm tối đa hóa số lượng liên kết.
• Đường mở và đường pha: Công cụ tìm kiếm đường đi xen kẽ trên đồ thị định hướng để mở rộng kích thước bộ ghép.
• Tính ổn định bền vững: Trạng thái ghép cặp mà không tồn tại bất kỳ cặp thí sinh và trường học nào cùng mong muốn lựa chọn nhau hơn đối tượng đã được phân bổ.
• Chiến lược trung thực: Cơ chế đảm bảo mọi bên tham gia đều đạt lợi ích tối đa khi khai báo chính xác thứ tự ưu tiên thực sự của mình.

Bên cạnh đó, tác giả phân tích thuật toán Hungari thiết lập năm 1955 nhằm giải quyết bài toán ghép cặp có trọng số cực đại trên ma trận chi phí, làm cơ sở đối sánh toàn diện với thuật toán Gale-Shapley trong bài toán phân bổ ổn định.

Phương pháp nghiên cứu

Nghiên cứu kết hợp phương pháp mô hình hóa toán học với thực nghiệm mô phỏng thuật toán trên máy tính. Cỡ mẫu nghiên cứu thực nghiệm được thiết kế qua 5 tập dữ liệu mẫu chuẩn hóa: từ mô hình cơ bản gồm 3 trường đại học và 4 thí sinh, đến mô hình mở rộng gồm 5 trường đại học và 5 thí sinh với ma trận sở thích đa chiều từ cấp độ 1 đến cấp độ 5. Phương pháp chọn mẫu là chọn mẫu có chủ đích, bao phủ đầy đủ các trường hợp: đồ thị hai phía cân bằng, đồ thị không cân bằng, và trường hợp mở rộng khi mỗi trường đại học tiếp nhận chỉ tiêu từ 2 thí sinh trở lên.

Lý do lựa chọn phương pháp phân tích thuật toán Gale-Shapley là khả năng bảo đảm tìm ra lời giải ổn định với độ phức tạp thời gian đa thức, loại bỏ hoàn toàn nguy cơ bế tắc hoặc chạy lặp vô tận của các giải thuật vét cạn. Quá trình thu thập dữ liệu lý thuyết, xây dựng mô hình toán và thử nghiệm chương trình mô phỏng trên môi trường hệ điều hành Windows 7, chip xử lý Intel Core i3-2310M và bộ nhớ 2GB RAM được thực hiện xuyên suốt timeline 2 năm học thuật từ năm 2013 đến tháng 5 năm 2015.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, nghiên cứu chứng minh rằng việc chuyển đổi bài toán tuyển sinh đại học một - nhiều về bài toán hôn nhân bền vững bằng phương pháp nhân bản mỗi trường đại học thành các bản sao tương ứng với chỉ tiêu tuyển sinh hoàn toàn giữ nguyên tính ổn định toán học đạt tỷ lệ 100%.

Thứ hai, qua các vòng thử nghiệm trên tập dữ liệu mô phỏng, thuật toán Gale-Shapley chứng minh tốc độ hội tụ nhanh chóng, tìm ra bộ ghép tối ưu chỉ sau khoảng 7 đến 10 bước lặp, ngay cả trong điều kiện số lượng ứng viên vượt quá chỉ tiêu đào tạo của các cơ sở giáo dục.

Thứ ba, thực nghiệm so sánh chỉ ra sự bất đối xứng quan trọng về quyền ưu tiên đề xuất: khi thí sinh giữ vai trò chủ động nộp đơn đề xuất, tỷ lệ ứng viên trúng tuyển vào nguyện vọng 1 và nguyện vọng 2 đạt mức xấp xỉ 80%, cao hơn khoảng 25% so với kịch bản các trường đại học giữ quyền chủ động gửi lời mời nhập học.

Thứ tư, thuật toán giúp triệt tiêu hoàn toàn 100% tình trạng hồ sơ ảo, bởi vì cơ chế ghép cặp trung tâm tự động khóa duy nhất 1 suất học tập cho mỗi thí sinh trúng tuyển hợp lệ, ngăn chặn tuyệt đối hiện tượng một thí sinh chiếm giữ chỉ tiêu tại nhiều trường cùng lúc.

Thảo luận kết quả

Nguyên nhân chính giúp thuật toán ghép cặp ổn định vận hành vượt trội là nhờ nguyên lý chấp nhận có trì hoãn. Trường đại học không đưa ra quyết định từ chối vĩnh viễn ngay từ đầu mà chỉ giữ lại các ứng viên có điểm số cao nhất tạm thời, sau đó liên tục so sánh với các ứng viên mới nộp vào ở các vòng tiếp theo cho đến khi trạng thái cân bằng được thiết lập.

Dữ liệu phân bổ sở thích và kết quả ghép cặp có thể được trực quan hóa rõ nét thông qua ma trận vuông hai chiều biểu diễn mức độ ưu tiên giữa thí sinh và nhà trường, kết hợp với các biểu đồ cột minh họa xác suất trúng tuyển theo từng nhóm điểm. So với quy trình tuyển sinh truyền thống năm 2015 tại Việt Nam – vốn khiến thí sinh và phụ huynh phải theo dõi biến động điểm chuẩn từng giờ và trực tiếp rút nộp hồ sơ tại trường – mô hình thuật toán trung tâm giúp tiết kiệm ước tính 95% thời gian và chi phí xã hội. Kết quả này hoàn toàn tương thích với báo cáo thực tế của hệ thống tuyển sinh trường công lập thành phố New York năm 2003, khi ứng dụng thuật toán Gale-Shapley đã giúp giảm đến 90% số lượng học sinh bị phân bổ vào các trường nằm ngoài danh sách nguyện vọng ưa thích.

Đề xuất và khuyến nghị

Nhằm hiện thực hóa các đóng góp học thuật vào công tác tuyển sinh quốc gia, nghiên cứu đề xuất 4 nhóm giải pháp cụ thể:

• Xây dựng hệ thống xét tuyển trực tuyến tập trung cấp quốc gia: Bộ Giáo dục và Đào tạo chủ trì tích hợp thuật toán Gale-Shapley vào cổng thông tin tuyển sinh chung, hướng tới mục tiêu xử lý tự động dữ liệu xét tuyển của hơn 1.000.000 thí sinh trong thời gian dưới 60 phút, triển khai thử nghiệm diện rộng trong thời gian 6 tháng.
• Thiết lập quy chế khuyến khích đăng ký nguyện vọng trung thực: Ban hành cơ chế cho phép thí sinh tự do đăng ký danh sách thứ tự ưu tiên không giới hạn mà không bị trừ điểm hay phạt cơ hội trúng tuyển ở các nguyện vọng phía sau, đặt mục tiêu giảm 95% tỷ lệ thí sinh ảo trên toàn hệ thống trong vòng 12 tháng.
• Chuẩn hóa và minh bạch hóa cơ sở dữ liệu chỉ tiêu: Các trường đại học trên cả nước có trách nhiệm công bố 100% chỉ tiêu theo ngành và tiêu chí phụ trước kỳ tuyển sinh ít nhất 90 ngày, phối hợp cùng các chuyên gia công nghệ để tích hợp cấu trúc dữ liệu xét tuyển tương thích với hệ thống phần mềm trung tâm.
• Nâng cấp hạ tầng công nghệ thông tin và đào tạo cán bộ: Cục Công nghệ thông tin phối hợp với các cơ sở đào tạo tổ chức tập huấn kỹ thuật cho khoảng 400 trường đại học và cao đẳng, hoàn thiện hệ thống máy chủ và giải pháp an toàn thông tin trong lộ trình 1 năm trước kỳ thi tuyển sinh kế tiếp.

Đối tượng nên tham khảo luận văn

• Cán bộ quản lý và hội đồng tuyển sinh các trường đại học: Tiếp cận phương pháp luận khoa học để tối ưu hóa 100% chỉ tiêu tuyển sinh, hạn chế sai số dự báo thí sinh nhập học và nâng cao chất lượng đầu vào của từng chuyên ngành đào tạo.
• Cơ quan quản lý nhà nước và chuyên gia hoạch định chính sách giáo dục: Tham khảo cơ sở lý thuyết thị trường phân phối ổn định để xây dựng quy chế tuyển sinh quốc gia hiện đại, công bằng, giảm thiểu chi phí xã hội và loại bỏ triệt để các tiêu cực trong khâu xét tuyển.
• Kỹ sư phát triển phần mềm và các công ty công nghệ giáo dục: Kế thừa mã nguồn, cấu trúc thuật toán đường mở, giải thuật Hungari và Gale-Shapley để lập trình các nền tảng lọc ảo, phân bổ tài nguyên và ghép cặp tự động quy mô lớn.
• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Toán ứng dụng: Sử dụng luận văn làm tài liệu tham khảo chuyên sâu về lý thuyết đồ thị hai phía, lý thuyết trò chơi và các bài toán tối ưu hóa tổ hợp có tính ứng dụng thực tiễn cao.

Câu hỏi thường gặp

Thuật toán Gale-Shapley loại bỏ hoàn toàn vấn đề thí sinh ảo trong tuyển sinh như thế nào? Thuật toán vận hành thông qua một cổng lọc ảo trung tâm duy nhất, nơi dữ liệu nguyện vọng của thí sinh và chỉ tiêu của nhà trường được xử lý đồng thời. Mỗi thí sinh chỉ có thể được gán vào duy nhất một trường thỏa mãn điều kiện điểm số cao nhất trong danh sách ưu tiên cá nhân, triệt tiêu 100% hiện tượng một người chiếm nhiều chỗ xét tuyển cùng lúc.

Vì sao phương án thí sinh chủ động đề xuất lại tối ưu hơn nhà trường chủ động đề xuất? Theo định lý toán học về tính ổn định, phía chủ động gửi lời đề nghị sẽ luôn nhận được kết quả tốt nhất có thể trong tập hợp các phương án ghép cặp bền vững. Khi thí sinh chủ động chọn trường, tỷ lệ trúng tuyển đúng nguyện vọng 1 và nguyện vọng 2 đạt trên 80%, bảo đảm tối đa hóa quyền lợi của người học.

Sự khác biệt cốt lõi giữa bài toán hôn nhân bền vững và bài toán tuyển sinh đại học là gì? Bài toán hôn nhân bền vững là mô hình ghép cặp một - một đối xứng giữa hai tập hợp có kích thước bằng nhau. Trong khi đó, bài toán tuyển sinh đại học là mô hình ghép cặp một - nhiều không đối xứng, trong đó một trường đại học có thể tiếp nhận hàng trăm chỉ tiêu sinh viên thông qua cơ chế nhân bản số lượng vị trí tuyển sinh.

Thuật toán Hungari có vai trò gì trong cấu trúc nghiên cứu của luận văn? Thuật toán Hungari được sử dụng để giải quyết bài toán ghép cặp có trọng số cực đại trên đồ thị hai phía, giúp tìm kiếm phương án ghép đôi có tổng điểm số hoặc độ thỏa dụng cao nhất. Đây là nền tảng lý thuyết quan trọng giúp tác giả so sánh hiệu năng và tính ổn định với thuật toán Gale-Shapley.

Hạ tầng máy tính thông thường có đủ khả năng vận hành thuật toán ghép cặp cho hàng triệu thí sinh không? Thuật toán Gale-Shapley có độ phức tạp tính toán đa thức tỷ lệ thuận với tích số giữa lượng thí sinh và số nguyện vọng đăng ký. Với cấu hình máy chủ hiện đại, hệ thống có thể xử lý hoàn tất dữ liệu của hơn 1.000.000 hồ sơ chỉ trong vài phút, vượt trội hoàn toàn so với máy tính cá nhân 2GB RAM dùng trong thử nghiệm mô phỏng.

Kết luận

• Luận văn hệ thống hóa toàn diện cơ sở lý thuyết đồ thị hai phía, thuật toán đường mở, thuật toán Hungari và bài toán hôn nhân bền vững Gale-Shapley.
• Mô hình hóa thành công bài toán tuyển sinh đại học tại Việt Nam thành bài toán ghép cặp một - nhiều ổn định, chứng minh khả năng tối ưu hóa 100% chỉ tiêu đào tạo.
• Khẳng định tính ưu việt của cơ chế chấp nhận có trì hoãn giúp loại bỏ hoàn toàn thí sinh ảo và nâng cao mức độ thỏa mãn nguyện vọng của người học lên trên 80%.
• Đóng góp giải pháp công nghệ then chốt định hướng cho việc xây dựng phần mềm lọc ảo tuyển sinh đại học toàn quốc giai đoạn sau năm 2015.
• Đề xuất lộ trình triển khai hạ tầng dữ liệu và thử nghiệm thuật toán trên Cổng thông tin tuyển sinh quốc gia trong khung thời gian 12 tháng tới.

Để tối ưu hóa quy trình xét tuyển và nâng cao chất lượng giáo dục, các cơ sở đào tạo cùng các nhà phát triển hệ thống cần chủ động nghiên cứu, thử nghiệm và tích hợp thuật toán ghép cặp ổn định vào nền tảng quản lý tuyển sinh ngay trong mùa tuyển sinh tới.

Trích đoạn nội dung tài liệu

Chương 1: TỔNG QUAN MỘT SỐ VẤN ĐỀ VỀ ĐỒ THỊ VÀ ĐỒ THỊ HAI PHÍA 1. Các khái niệm cơ bản 1. Đồ thị Đồ thị vô hướng G = (V,E) gồm[4]: - V là tập hợp khác rỗng mà các phần tử của nó gọi là đỉnh (vertex) của G. - E là đa tập hợp gồm các cặp không sắp thứ tự của hai đỉnh.

Mỗi phần tử của E được gọi là một cạnh (edge) của G. Đồ thị vô hướng không có cạnh song song và không có khuyên gọi là đồ thị đơn vô hướng. Đồ thị hai phía Một đồ thị đơn vô hướng G:=(V,E) được gọi là hai phía nếu tồn tại một phân hoạch tập đỉnh V thành hai tập con X1 và X2 độc lập, rời nhau sao cho bất kì cạnh nào của đồ thị cũng nối một đỉnh thuộc X1 với một đỉnh thuộc X2. Khi đó người ta còn kí hiệu là: G:=(X1X2,E) với các phân hoạch X1, X2 và gọi một tập (chẳng hạn X1) là tập các đỉnh trái và tập còn lại (chẳng hạn X2) là tập Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 12 các đỉnh phải của đồ thị hai phía G.

Các đỉnh thuộc X1 gọi là các X1_đỉnh, các đỉnh thuộc X2 gọi là các X2_đỉnh. Nếu |X1|=|X2| thì G được gọi là đồ thị hai phía cân bằng. Đồ thị hai phía không có chu trình Hình 3. Đồ thị hai phía có chu trình Hình 4.Đồ thị không phải đồ thị hai phía 1.

Đồ thị hai phía đầy đủ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 13 Cho G = (V,E) là một đồ thị vô hướng hai phía, một phân hoạch V thành hai tập con X1 và X2 (X1 ≠ ≠ X2 và X1  X2 = ), sao cho không có cạnh nối giữa 2 điểm trong cùng một tập con. Khi đó G được gọi là hai phía đầy đủ nếu: Với mọi cặp đỉnh (i,j) mà iX1 và j X2 thì có đúng một cạnh nối i và j, ij là một cạnh trong E. Một đồ thị hai phía đầy đủ với các phân chia kích thước |X1| = m, |X2| = n được kí hiệu là Km,n. Hai đồ thị mà có kí hiệu giống nhau thì chúng đẳng cấu.

- Đồ thị hai phía đầy đủ Km,n có: m+n đỉnh, m. - Các dạng đồ thị đầy đủ hai phía:  K1,n với đồ thị hình sao Hình 5.Đồ thị hai phía đầy đủ hình sao  K1,n với đồ thị hình vuốt cây Hình 6. Đồ thị hai phía đầy đủ hình vuốt cây Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 14  Km,n với m≠n Hình 7. Đồ thị hai phía đầy đủ m≠n  Km,n với m = n Hình 8.

Đồ thị hai phía đầy đủ m=n 1. Bài toán ghép cặp không trọng 1. Bài toán Cho một đồ thị hai phía G = (X1X2,E) ở đây X1 là các tập đỉnh trái và X2 là tập các đỉnh phải của G. Một bộ ghép (matching) của G là một tập các cạnh của G đôi một không có đỉnh chung.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 15 Bài toán ghép cặp (matching problem) là tìm một bộ ghép lớn nhất (nghĩa là có số cạnh lớn nhất) của G. Xét một bộ ghép M của G. - Các đỉnh trong M gọi là các đỉnh đã ghép (matched vertices), các đỉnh khác là chưa ghép. - Các cạnh trong M gọi là các cạnh đã ghép, các cạnh khác là chưa ghép.

Nếu định hướng lại các cạnh của đồ thị thành cung, những cạnh chưa ghép được định hướng từ X1 sang X2, những cạnh đã ghép định hướng từ X2 về X1 .Trên đồ thị định hướng đó: Một đường đi xuất phát từ một X1_đỉnh chưa ghép gọi là đường pha (alternating path), một đường đi từ một X1_đỉnh chưa ghép tới một X2_đỉnh chưa ghép gọi là đường mở (augmenting path). Một cách dễ hiểu, có thể quan niệm như sau: - Một đường pha là một đường đi đơn trong G bắt đầu bằng một X1_đỉnh chưa ghép, đi theo một cạnh chưa ghép sang X2 , rồi đến một cạnh đã ghép về X1, rồi lại đến một cạnh chưa ghép sang X2… cứ xen kẽ nhau như vậy. - Một đường mở là một đường pha. Bắt đầu từ một X1_đỉnh chưa ghép kết thúc bằng một X2_đỉnh chưa ghép.

Ví dụ: Với đồ thị hai phía trong hình 9 và bộ ghép M ={(x1[1],x2[1]),(x1[2],x2[2])} x1[3] và x2[3] là những đỉnh chưa ghép, các đỉnh khác là đã ghép. Đường (x1[3], x2[3], x1[2], x2[1]) là đường pha. Đường (x1[3], x2[3], x1[2], x2[1], x1[1], x2[3]) là đường mở. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

Đồ thị hai phía và bộ ghép M 1. Thuật toán đường mở Thuật toán đường mở để tìm một bộ ghép lớn nhất cho bài toán ghép cặp phát biểu như sau: Bước 1: Bắt đầu từ một bộ ghép bất kỳ M (thông thường bộ ghép được khởi gán bằng bộ ghép rỗng hay được tìm bằng các thuật toán tham lam). Bước 2: Tìm một đường mở. Bước 3: Nếu bước 2 tìm được đường mở thì mở rộng bộ ghép M: Trên đường mở, loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép.

Sau đó lặp lại bước 2. Nếu bước 2 không tìm được đường mở thì thuật toán kết thúc. * Mã giả thuật toán: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 17 Input: Đồ thị hai phía G = (X1X2,E), X1={x1[1], x1[2],…, x1[m]}, X2={x2[1], x2[2],…, x2[n]}. Output: Một bộ ghép M lớn nhất của G.

Như ví dụ trên, với bộ ghép hai cạnh M ={(x1[1],x2[1]),(x1[2],x2[2])} và đường mở tìm được gồm các cạnh: (x1[3], x2[2])  M (x2[2], x1[2])  M (x1[2], x2[1])  M (x2[1], x1[1])  M (x1[1], x2[3])  M Vậy thì ta sẽ loại đi các cạnh (x2[2], x1[2]) và (x2[1], x1[1]) trong bộ ghép cũ và thêm vào đó các cạnh (x1[3], x2[2]), (x1[2], x2[1]), (x1[1], x2[3]) được bộ ghép 3 cạnh. Bài toán ghép cặp với trọng số cực tiểu 1. Bài toán Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 18 Cho một đồ thị hai phía G = (X1X2,E). Được cho bởi ma trận vuông C cỡ kk, c[i, j] = trọng số cạnh nối đỉnh x1[i] với x2[j].

Giả thiết c[i, j]0 (i, j) Bài toán ghép cặp với trọng số cực tiểu là tìm một bộ ghép đầy đủ trọng số nhỏ nhất. Hai định lý sau đây tuy rất đơn giản nhưng là những định lý quan trọng tạo cơ sở cho thuật toán sẽ trình bày. Định lý 1: Loại bỏ khỏi G những cạnh trọng số lớn hơn 0. Nếu những cạnh trọng số 0 còn lại tạo ra bộ ghép k cạnh trong G thì đây là bộ ghép cần tìm.

Chứng minh: theo giả thiết, các cạnh của G mang trọng số không âm nên bấy kỳ bộ ghép nào trong G cũng có trọng số không âm, mà bộ ghép ở trên mang trọng số 0, nên tất nhiên đó là bộ ghép đầy đủ trọng số nhỏ nhất. Định lý 2: Với đỉnh x1[i], nếu ta cộng thêm một số  (dương hay âm) vào tất cả những cạnh liên thuộc với x1[i] (tương đương với việc cộng thêm  vào tất cả các phần tử thuộc hàng i của ma trận C) thì không ảnh hưởng tới bộ ghép đầy đủ trọng số nhỏ nhất. Chứng minh: Với một bộ ghép đầy đủ bất kỳ thì có một và chỉ một cạnh ghép với x1[i]. Nên việc cộng thêm  vào tất cả các cạnh liên thuộc với x1[i] sẽ làm tăng trọng số bộ ghép đó lên .

Vì vậy nếu như ban đầu, M là bộ ghép đầy đủ trọng số nhỏ nhất thì sau thao tác trên, M vẫn là bộ ghép đầy đủ trọng số nhỏ nhất. Các khái niệm Để cho gọn, ta gọi những cạnh trọng số 0 của G là những 0_cạnh. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 19 Xét một bộ ghép M chỉ gồm những 0_cạnh. - Những đỉnh  M gọi là những đỉnh đã ghép, những đỉnh còn lại gọi là những đỉnh chưa ghép.

- Những 0_cạnh  M gọi là những 0_cạnh đã ghép, những 0_cạnh còn lại là những 0_cạnh chưa ghép. Nếu ta định hướng lại các 0_cạnh theo cách: Những 0_cạnh chưa ghép cho hướng từ tập X1 sang tập X2, những 0_cạnh đã ghép cho hướng từ tập X2 về tập X1. Khi đó: - Đường pha là một đường đi cơ bản xuất phát từ một X1_ đỉnh chưa ghép đi theo các 0_cạnh đã định hướng ở trên. Như vậy dọc trên đường pha, các 0_cạnh chưa ghép và những 0_cạnh đã ghép xen kẽ nhau.

Vì đường pha chỉ là đường đi cơ bản trên đồ thị định hướng nên việc xác định những đỉnh nào có thể đến được từ x  X1 bằng một đường pha có thể sử dụng các thuật toán tìm kiếm trên đồ thị. Những đỉnh và những cạnh được duyệt qua tạo thành một cây pha gốc x. - Một đường mở là một đường pha đi từ một X1_ đỉnh chưa ghép tới một X2_đỉnh chưa ghép. Như vậy: - Đường đi trực tiếp từ một X1_đỉnh chưa ghép tới một X2_đỉnh chưa ghép qua một 0_cạnh chưa ghép cũng là một đường mở.

- Dọc trên đường mở, số 0_cạnh chưa ghép nhiều hơn số 0_cạnh đã ghép đúng 1 cạnh. Thuật toán Hungari Bước 1: Khởi tạo Một bộ ghép M := Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 20 Bước 2: với mọi đỉnh x  X1, ta tìm cách ghép x: Bắt đầu từ đỉnh x, thử tìm đường mở bắt đầu ở x bằng thuật toán tìm kiếm trên đồ thị. Có hai khả năng có thể xảy ra: - Hoặc tìm được đường mở thì dọc theo đường mở, ta loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép, ta được một bộ ghép mới nhiều hơn bộ ghép cũ 1 cạnh và đỉnh x trở thành đã ghép. - Hoặc không tìm được đường mở thì có thể xác định được: VisitedX1= {Tập những X1_đỉnh có thể đến được từ x bằng một đường pha} VisitedX2= {Tập những X2_đỉnh có thể đến được từ x bằng một đường pha} Gọi  là trọng số nhỏ nhất của các cạnh nối giữa một đỉnh thuộc VisitedX1 với một đỉnh không thuộc VisitedX2.

Dễ thấy  >0 bởi nếu =0 thì tồn tại một 0_cạnh (x1, x2) với x1VisitedX1 và x2VisitedX2. Vì x đến được x1 bằng một đường pha và (x1, x2) là một 0_cạnh nên x cũng đến được x2 bằng một đường pha, dẫn tới x2  VisitedX2, điều này vô lý.