Bài giảng Lý thuyết về đồ thị - 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.
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết về đồ thị - Bài 9: Bài toán ghép cặp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Lý thuyết về đồ thị - Bài 9: Bài toán ghép cặp
![Bài giảng Lý thuyết về đồ thị - Bài 9: Bài toán ghép cặp Bài giảng Lý thuyết về đồ thị - Bài 9: Bài toán ghép cặp](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2021/12/03/bai-giang-ly-thuyet-ve-do-thi-bai-9-bai-toan-ghep-cap_9wsIz08SXB.jpg)
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=V 1 V 2 , V 1 V 2 = , V 1 , V 2 và mỗi cạnh của G được nối một đỉnh trong V 1 và một đỉnh trong V 2 đượ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 S i 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ó S 1 = {A, B, C}, S 2 = {D, E}, S 3 = {D}, S 4 = {E}, S 5 = {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 B 1 , B 2 , B 3 , B 4 và 5 cô gái G 1 , G 2 , G 3 , G 4 , G 5 ; mỗi chàng có 1 danh sách các cô gái thích hợp như sau: B1: {G 1 , G 4 , G 5 } B2: {G 1 } B3: {G 2 , G 3 , G 4 } B4: {G 2 , G 4 } 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: (B 1 , G 4 ), (B 2 , G 1 ), (B 3 , G 3 ), (B 4 , G 2 ) 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 , A 2 , A m } 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ỳ A i1 , A ik A, ta có | A i1 A i2 A ik | >=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 , a 2 , , a m ) gồm m phần tử khác nhau của S sao cho a i A i ; mỗi một ai gọi là 1 đại diện của A i . 6 Ví dụ Cho A ={A 1 , A 2 , A 3 , A 4 } với A 1 ={1, 2}, A 2 ={2, 3, 4}, A 3 ={1 }, A 4 ={2} thì vì |A 1 A 2 A 3 | = 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 {A 1 , A 2 , A m } 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ử a 1 tùy ý của A 1 làm đại diện cho A 1 . Với i>=2 và A i – {a 1 , a 2, , a i-1 } ta chọn 1 phần tử bất kỳ của A i – {a 1 , a 2, , a i-1 } Nếu chọn được a 1 , a 2 , , a m 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 – {a 1 , a 2, , a k-1 } = hay A k {a 1 , a 2, , a k-1 } (có nghĩa là mỗi phần tử A k đã 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 B 1 = A k và sắp các phần tử của B 1 thành 1 dãy U 1 = b 1 b 2 b h . Nếu S(b 1 ) – B 1 = thì đặt U 2 = U 1 ; nếu S(b 1 ) – B 1 = {b h+1 b p }, ta lập dãy U 2 = U 1 b h+1 b p = b 1 b 2 b p Giả sử có U i và B i là tập hợp các phần tử xuất hiện trong U i . Nếu S(b i ) – B i = thì đặt U i+1 = U i ; nếu ngược lại S(b i ) – B i = {b i1 , b it }, thì ta lập dãy U i+1 = U i b i1 , b it 13 Thuật toán tìm SDR (tt) Nếu cuối cùng có dãy U q với các phần tử b 1 , b r đều đã là đại diện của S(b i ), i=1, , r thì |A k S(b 1 ) S(b r )| = 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ử b s chưa là đại diện. Theo định nghĩa của U 1 thì b s không có trong U 1 và có s 1 < s sao cho b s S(b s2 ), b s2 S(b s2 ), , b t-1 S(b st ), b st A k 14 Thuật toán tìm SDR (tt) Ta chọn b s làm đại diện cho S(b s1 ), b s1 làm đại diện cho S(b s2 ), , và b t-1 làm đại diện cho S(b st ), cuối cùng b st làm đại diện cho A k 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. 16 J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23 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<n thì đến Bước 4. Nếu k=n thì đến Bước 5 17 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 A i ={j: A ij = 0}. Dùng thuật toán Hall để tìm ra SDR của A = {A 1 , A n }, 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 phân công công việc (tt) Bước 2 J1 J2 J3 J4 W1 13 14 0 8 W2 40 0 12 40 W3 6 64 0 66 W4 0 1 90 0 (-0) (-0) (-0) (-15) 19 J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23 Bước 1 J1 J2 J3 J4 W1 13 14 0 23 (-69) W2 40 0 12 55 (-37) W3 6 64 0 81 (-5) W4 0 1 90 15 (-8) Bước 3 J1 J2 J3 J4 W1 13 14 0 8 W2 40 0 12 40 x W3 6 64 0 66 W4 0 1 90 0 x x Số lượng dòng (bao phủ tất cả 0 trong ma trận) là 3 < n=4 của ma trận nên chuyển sang bước 4. Số nhỏ nhất trong ma trận hiện tại là 6 . Bước 4 J1 J2 J3 J4 W1 7 8 0 2 W2 40 0 18 40 W3 0 58 0 60 (-6) W4 0 1 96 0 (+6) Bước 3’ J1 J2 J3 J4 W1 7 8 0 2 x W2 40 0 18 40 x W3 0 58 0 60 x W4 0 1 96 0 x Số lượng dòng (bao phủ tất cả 0 trong ma trận) là 4 = n=4 của ma trận nên chuyển sang bước 5. Bài toán phân công công việc (tt) 20 J1 J2 J3 J4 W1 82 83 69 92 W2 77 37 49 92 W3 11 69 5 86 W4 8 9 98 23 Bước 5 J1 J2 J3 J4 W1 7 8 0 2 W2 40 0 18 40 W3 0 58 0 60 W4 0 1 96 0 Tổng chi phí của phân công công việc tối ưu là 69 + 37 + 11 + 23 = 140. Bài toán giao việc của Gale Loại bài toán giao việc khác đó là xét tầm quan trọng của công việc. Việc nào quan trọng hơn sẽ được ưu tiên nhận người. Quy ước: J 1 <J 2 nếu công việc J 1 quan trọng hay ưu tiên hơn công việc J 2 21 Bài toán giao việc của Gale (tt) Định nghĩa Cho A = {a 1 , a 2 , . a n } là tập hợp các công việc a 1 < a 2 . < a n . Ta nói rằng A phân công được nếu có thể phân công những người khác nhau phụ trách tất cả nhưng công việc khác nhau trong A. Cho A = {a 1 , a 2 , . a n } phân công được. A được gọi là tập hơn phân công được tối ưu hay OAS (order acceptance and scheduling) nếu với mọi tập hợp phân công được B = {b 1 , b 2 , b n } ta có m<=n và a i <=b i , trong đó i=1, , m 22 Bài toán giao việc của Gale (tt) Cho J 1 < J 2 < J 3 < J 4 < J 5 và danh sách các ứng viên cho các công việc này như sau Có thể kiểm chứng các tập hợp {J 2 , J 3 , J 4 } , {J 1 , J 4 , J 5 }, {J 1 , J 2 , J 3 , J 5 } là phân công được, trong đó {J 1 , J 2 , J 3 , J 5 } là tối ưu. 23 Công việc Ứng viên J 1 A, B J 2 B, C J 3 B J 4 A, C J 5 B, C, D Bài toán giao việc của Gale (tt) Thuật toán tìm tập hợp phân công được tối ưu Thuận toán này chính là thuật toán tìm một hệ đại diện riêng biệt cho A= {J 1 , J s } với J 1 < < J s . Chọn đại diện theo thứ tự ưu tiên. Nếu đến J r mà không tìm được đại diện cho J r sau khi đã đổi việc thì bỏ qua công việc này (chưa có người phụ trách) để xét đến J r+1. 24 Bài toán giao việc của Gale (tt) Ví dụ : Tìm tập hợp phân công tối ưu OAS cho các công việc theo bảng Chọn A J 1 , B J 2 , thì không thể chọn đại diện cho J 3 ={B}. Đặt U 1 =B, ta có S(B)=J 2 ={b, C} nên U 2 =BC và C chưa là đại diện. Vì C S(B), B U 1 nên ta thay đổi đại diện như sau: C là đại diện cho J 2 và B là đại diện cho J 3 25 Công việc Ứng viên J 1 A, B J 2 B, C J 3 B J 4 A, C J 5 B, C, D Bài toán giao việc của Gale (tt) Ví dụ : (tt) Đặt U 1 =AC ta có S(A) = J 1 = {A, B} nên U 2 = ACB, S(C) = J 2 ={B, C} U 3 =ACB, S(B) = J 3 ={B} U 4 =ACB Không có đại diện nào cho J 4 nên ta xét đến J 5 (loại J 4 ra khỏi A) và chọn D làm đại diện cho J 5 . Vậy ta có OAS là là {J 1 , J 2 , J 3 , J 5 } với các phân công sau A -> J 1 , C -> J 2 , B->J 3 , D->J 5 26
File đính kèm:
bai_giang_ly_thuyet_ve_do_thi_bai_9_bai_toan_ghep_cap.ppt