›
›

Bài tập Toán rời rạc - Phần: Hôn nhân bền vững

Download
Toán rời rạc: Hôn nhân bền vững  
Bài tập 8  
1. Có bốn sinh viên muốn thực tập tại bốn công ty. Sau đây là danh sách yêu thích của các  
sinh viên và của các công ty:  
Sinh viên  
Albert  
Nick  
Oshani  
Ali  
Công ty  
Công ty  
AT&T  
Sinh viên  
Ali, Albert, Oshani, Nick  
HP, Bellcore, AT&T, Draper  
AT&T, Bellcore, Draper, HP  
HP, Draper, AT&T, Bellcore  
Draper, AT&T, Bellcore, HP  
Bellcore Oshani, Nick, Albert, Ali  
HP Ali, Oshani, Albert, Nick  
Draper Nick, Ali, Oshani, Albert  
(a) Hãy sử dụng thủ tục kén chồng (hoặc vợ) để tìm hai cặp ghép ổn định.  
(b) Mô tả một thuật toán đơn giản để xác định xem liệu bài toán hôn nhân bền vững  
cho trước có nghiệm duy nhất không, có nghĩa rằng chỉ có duy nhất một cách ghép  
cặp ổn định.  
2. Xét bài toán hôn nhân bền vững với 4 nam và 4 nữ với một phần thông tin về danh sách  
yêu thích của họ được cho dưới đây:  
B1: G1 G2  
B2: G2 G1  
–
–
–
–
B3:  
B4:  
–
–
–
–
G4 G3  
G3 G4  
G1: B2 B1  
G2: B1 B2  
–
–
–
–
G3:  
G4:  
–
–
–
–
B3 B4  
B4 B3  
(a) Chứng minh rằng  
(B1, G1), (B2, G2), (B3, G3), (B4, G4)  
là ghép cặp ổn định với mọi cách gán giá trị còn lại trong danh sách yêu thích.  
(b) Giải thích xem tại sao ghép cặp không phải là tốt nhất cho nam cũng không phải là  
tồi nhất cho nữ, và vì vậy nó không thể là kết quả của của Thủ tục kén chồng.  
(c) Mô tả cách định nghĩa danh sách yêu thích cho n nam và n nữ để có ít nhất 2n/2  
ghép cặp ổn định.  
3. Giả sử có nhiều nam hơn nữ.  
(a) Định nghĩa cặp ghép ổn định trong trường hợp này.  
(b) Giải thích tại sao áp dụng Thủ tục kén chồng trong trường hợp này sẽ mang lại một  
cặp ghép ổn định trong đó mọi cô gái đều được kết hôn.  
1
4. Hãy đưa ra một ví dụ cặp ghép ổn định giữa 3 nam và 3 nữ trong đó không ai lấy được  
người mình thích nhất. Giải thích tóm tắt tại sao cặp ghép của bạn là ổn định.  
5. Trong một cặp ghép ổn định giữa n chàng trai và n cô gái dùng Thủ tục kén chồng, ta gọi  
một người là may mắn nếu họ được ghép cặp với một trong dn/2e người họ thích nhất.  
Hãy chứng minh định lý sau  
Định lý. Với thủ tục kén chồng, luôn có ít nhất một người may mắn.  
2
pdf 2 trang Thùy Anh 19100 Free
Download
Bạn đang xem tài liệu "Bài tập Toán rời rạc - Phần: Hôn nhân bền vững", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_tap_toan_roi_rac_phan_hon_nhan_ben_vung.pdf