Bài tập Toán rời rạc - Bài 8

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 Công ty Albert HP, Bellcore, AT&T, Draper Nick AT&T, Bellcore, Draper, HP Oshani HP, Draper, AT&T, Bellcore Ali Draper, AT&T, Bellcore, HP Công ty Sinh viên AT&T Ali, Albert, Oshani, Nick 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: – – G4 G3 B4: – – G3 G4 G1: B2 B1 – – G2: B1 B2 – – G3: – – B3 B4 G4: – – 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