TAILIEUCHUNG - Bài giảng Lý thuyết đồ thị - Bài 9: Bài toán ghép cặp
Bài giảng "Lý thuyết đồ thị - Bài 9: Bài toán ghép cặp" cung cấp cho người học các kiến thức: Đồ thị lưỡng phân, định lí Hall và ứng dụng, thuật toán tìm SDR, bài toán phân công công việc, bài toán giao việc của Gale,. . | Bài giảng Lý thuyết đồ thị - Bài 9: Bài toán ghép cặp Bài 9 Bài toán ghép cặp Giới thiệu Bài toán ghép cặp có thể chia thành 2 loại Xét việc ghép mỗi phần tử của tập hợp này với 1 phần tử của tập hợp khác như phân công n việc khác nhau cho n người, mỗi người 1 việc, đó chính là bài toán hôn nhân. Xét việc chia 2k phần tử của 1 tập hợp thành k cặp, ví dụ như sắp xếp 2k sinh viên vào k phòng trong ký túc xá (mỗi phòng có 2 sinh viên) Định lý Hall Bài toán hôn nhân do Phillip Hall giải quyết năm 1935 có rất nhiều ứng dụng và được phát biểu dưới nhiều dạng khác nhau. 2 Đồ thị lưỡng phân Định nghĩa: Đơn đồ thị G=(V,E) sao cho V=V1 V2, V 1 V 2= , V 1 , V2 và mỗi cạnh của G được nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị 2 đầu (lưỡng phân). Cho đồ thị lưỡng phân G=(A,B,E). Một ghép cặp là một tập hợp các cạnh sao cho không có cạnh nào có chung 1 đầu mút. Một ghép cặp từ A đến B được gọi là hoàn hảo khi nó có thể nối tất cả các đỉnh của A đến B 3 Đặt vấn đề Có 5 việc cần tuyển người đảm nhiệm, mỗi người 1 việc. Gọi Si là tập hợp các ứng viên thích hợp cho việc thứ i và giả sử rằng ta có S1 = {A, B, C}, S2 = {D, E}, S3 = {D}, S4 = {E}, S5 = {A, E} Có thể tuyển đủ 5 người thích hợp cho 5 việc nói trên hay không? ? 4 Đặt vấn đề Có 4 chàng trai B1, B2, B3, B4 và 5 cô gái G1, G2, G3, G4, G5; mỗi chàng có 1 danh sách các cô gái thích hợp như sau: B1: {G1, G4, G5} B2: {G1} B3: {G2, G3, G4} B4: {G2, G4} Một chàng trai có thể kết hợp với 1 cô gái thích hợp hay không? Dễ dàng ta thấy lời giải cho bài toán này là các cặp sau: (B1, G4), (B2, G1), (B3, G3), (B4, G2) 5 Định nghĩa Cho S là một tập hợp hữu hạn và đa tập hợp A={A 1, A2, Am} là một họ các tập con của S. Ta bảo A thỏa điều kiện Hall nếu với mọi k {1, , m} và k phần tử bất kỳ Ai1, Aik A, ta có
đang nạp các trang xem trước
