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

Chia sẻ: Minh Nguyệt | Ngày: | Loại File: PPT | Số trang:26

Thêm vào BST

Báo xấu

79
lượt xem 6
download

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

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,... Mời các bạn cùng tham khảo.

Chủ đề:

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

Lưu

Nội dung Text: 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ó |Ai1 Ai2 … Aik| >=k  Một hệ đại diện riêng biệt hay 1 SDR (Systems of Distinct Representatives) của A là một bộ (a 1, a2, …, am) gồm m phần tử khác nhau của S sao cho a i Ai; mỗi một ai gọi là 1 đại diện của Ai. 6
Ví 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í Hall Cho đồ 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 . 11
Thuậ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 A k – {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. 12
Thuậ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 = b1b2…bh. 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 …bp  Giả 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, …bit 13
Thuậ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 < r+1, điều này trái với giả thiết A thỏa điều kiện Hall. Vậy có r mà trong U r có một phần tử bs- chưa là đại diện. Theo định nghĩa của U1 thì bs không có trong U1 và có s1 < s sao cho bs S(bs2), bs2 S(bs2), …, bt-1 S(bst), bst Ak 14
Thuật toán tìm SDR (tt) Ta chọn bs làm đại diện cho S(bs1-), bs1 làm đại diện cho S(bs2-), …, và bt-1 làm đại diện cho S(bst-), cuối cùng bst làm đại diện cho Ak Lặp lại quá trình trên ta có một SDR của A 15
Bài toán phân công công việc  Giả sử ta có 4 việc v1, v2, v3, v4 và 4 ứng viên U1, U2, U3, U4 mà ta muốn phân công mỗi người một việc. Khả năng của mỗi ứng viên tương ứng với mỗi công việc cho trong bảng sau đây, trong đó điểm càng cao khả năng càng thấp. J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23 16
Bài toán phân công công việc (tt) Thuật toán tìm phương án phân công tốt nhất Bước 1: Trừ mỗi dòng cho số nhỏ nhất của dòng đó Bước 2: Trừ mỗi cột cho số nhỏ nhất của cột đó. Bước 3: Xác định k, số đường nhỏ nhất chứa tất cả các zero của A và chỉ rõ đường k Nếu k
Bài toán phân công công việc (tt) Thuật toán tìm phương án phân công tốt nhất (tt) Bước 4: Gọi a là số nhỏ nhất không xuất hiện trong các đường xác định ở Bước 3. -Trừ a cho tất cả các số không trên đường nào -Cộng a cho tất cả các số trên 2 đường (giao điểm của dòng, cột -Giữ nguyên các số chỉ ở trên 1 đường. Trở lại Bước 3. Bước 5: Đặt Ai={j: Aij= 0}. Dùng thuật toán Hall để tìm ra SDR của A = {A1, …An}, tức là tìm n zero độc lập (Các số 0 ở trên những dòng và những cột khác nhau của ma trận A được gọi là các zero độc lập) Suy ra kết quả. Dừng. 18
Bài toán J1 J2 J3 J4 phân công công việc (tt) Bước 1 J1 J2 J3 J4 Bước 2 J1 J2 J3 J W1 82 83 69 92 W1 13 14 0 23 (-69) W1 13 14 0 W2 77 37 49 92 W2 40 0 12 55 (-37) W2 40 0 12 4 W3 11 69 5 86 W3 6 64 0 81 (-5) W3 6 64 0 6 W4 8 9 98 23 W4 0 1 90 15 (-8) W4 0 1 90 (-0) (-0) (-0) (-15 Bước 3 J1 J2 J3 J4 Số lượng dòng (bao phủ tất cả 0 W1 13 14 0 8 trong ma trận) là 3 < n=4 của ma Bước 4 J1 J2 J3 J4 W2 40 0 12 40 x trận nên chuyển W1 7 8 0 2 W3 6 64 0 66 sang bước 4. Số nhỏ nhất trong W2 40 0 18 40 W4 0 1 90 0 x ma trận hiện tại là 6. W3 0 58 0 60 (-6) x W4 0 1 96 0 Bước 3’ J1 J2 J3 J4 (+6) W1 7 8 0 2 x W2 40 0 18 40 x Số lượng dòng (bao phủ tất cả 0 trong ma W3 0 58 0 60 x trận) là 4 = n=4 của ma trận nên chuyển sang bước 5. 19 W4 0 1 96 0 x
Bài toán phân công công việc (tt) Bước 5 J1 J2 J3 J4 J1 J2 J3 J4 W1 7 8 0 2 W1 82 83 69 92 W2 40 0 18 40 W2 77 37 49 92 W3 0 58 0 60 W3 11 69 5 86 W4 0 1 96 0 W4 8 9 98 23 Tổng chi phí của phân công công việc tối ưu là 69 + 37 + 11 + 23 = 140. 20