Bài giảng Lý thuyết đồ thị - Bài 9: Bài toán ghép cặp

Bài 9Bài toán ghép cặpGiới thiệuBài toán ghép cặp có thể chia thành 2 loạiXé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ý HallBà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, V1V2=, V1 , 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 B3Đặ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ĩaCho S là một tập hợp hữu hạn và đa tập hợp A={A1, 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ó |Ai1  Ai2  Aik| >=kMột hệ đại diện riêng biệt hay 1 SDR (Systems of Distinct Representatives) của A là một bộ (a1, a2, , am) gồm m phần tử khác nhau của S sao cho ai  Ai; mỗi một ai gọi là 1 đại diện của Ai. 6Ví dụCho A ={A1, A2, A3, A4} với A1={1, 2}, A2={2, 3, 4}, A3={1}, A4={2} thì vì |A1  A2  A3 | = 2 nên A không thỏa điều kiện Hall. 7Định lí Hall và ứng dụngĐịnh lí HallCho đồ thị lưỡng phân X, Y. Với mỗi tập con A thuộc X, gọi G(A) là tập các đỉnh thuộc Y kề với một đỉnh nào đó thuộc A. Khi đó điều kiện cần và đủ để tồn tại một đơn ánh f: X → Y sao cho x kề f(x) là |G(A)| ≥ |A| với mọi A khác rỗng thuộc X.Cho S là một tập hợp hữu hạn và đa tập hợp {A1, A2, Am} là một họ các tập con của S, A có 1 SDR nếu và chỉ nếu A thỏa điều kiện Hall. 8Định lí Hall (tt)Chứng minhĐiều kiện cần là hiển nhiên: Nếu tồn tại đơn ánh f thì với mỗi thuộc X, ta có  chứa các phần tử phân biệt , do đó .Ta chứng minh điều kiện đủ bằng quy nạp theo |X|. Khi , khẳng định là hiển nhiên. Giả sử định lý đã đúng với các tập X với . Giả sử bây giờ . Ta xét hai trường hợp:9Định lí Hall (tt)Chứng minh (tt)1) Giả sử với mọi , ta có . Chọn một phần tử bất kỳ thuộc X, theo điều kiện , do đó tồn tại  thuộc Y kề với X. Ta đặt . Bây giờ xét  và , và G’(A) là tập các đỉnh thuộc Y’ kề với A. Khi đó . Vì  nên theo giả thiết quy nạp, tồn tại đơn ánh sao cho  kề x với mọi x thuộc x’. Bổ sung thêm ta được đơn ánh  thỏa mãn yêu cầu định lý.10Định lí Hall (tt)Chứng minh (tt)2) Trong trường hợp ngược lại, tồn tại  sao cho . Khi đó, do  nên tồn tại đơn ánh . Xét , . Xét B thuộc X’ và  là tập các đỉnh thuộc Y’ kề với B. Nếu  thì ta có mâu thuẫn với điều kiện định lý. Như vậy ta có  với mọi B thuộc X’. Theo giả thiết quy nạp, tồn tại đơn ánh  sao cho g(x) kề với x. Như vậy, ta có thể xây dựng được đơn ánh  sao cho h(x) kề với x: cụ thể h(x) = f(x) nếu x thuộc A và h(x) = g(x) nếu x thuộc .11Thuật toán tìm SDR Cho một phần tử a1 tùy ý của A1 làm đại diện cho A1. Với i>=2 và Ai – {a1, a2, , ai-1}  ta chọn 1 phần tử bất kỳ của Ai – {a1, a2, , ai-1}Nếu chọn được a1, a2, , am thì tập hợp này sẽ tạo thành 1 SDR của A.Ngược lại, trong trường hợp có k sao cho Ak – {a1, a2, , ak-1} =  hay Ak {a1, a2, , ak-1} (có nghĩa là mỗi phần tử Ak đã là đại diện. Gọi S(b) là phần tử của A có đại diện là b.12Thuật toán tìm SDR (tt) Đặt B1 = Ak và sắp các phần tử của B1 thành 1 dãy U1 = b1b2bh. Nếu S(b1) – B1 =  thì đặt U2 = U1; nếu S(b1) – B1 = {bh+1 bp}, ta lập dãy U2 = U1 bh+1 bp= b1b2 bpGiả sử có Ui và Bi là tập hợp các phần tử xuất hiện trong Ui. Nếu S(bi) – Bi=  thì đặt Ui+1 = Ui; nếu ngược lại S(bi) – Bi = {bi1, bit}, thì ta lập dãy Ui+1 = Ui bi1, bit13Thuật toán tìm SDR (tt) Nếu cuối cùng có dãy Uq với các phần tử b1, br đều đã là đại diện của S(bi), i=1, , r thì |Ak  S(b1)   S(br)| = r J1, C -> J2, B->J3, D->J526