Bài giảng Lý thuyết về đồ 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=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