Đề thi Giữa kì môn Toán rời rạc

Đề thi giữa kỳ Toán rời rạc Đề 2 Thời gian 90 phút Mỗi câu 1 điểm. Không dùng tài liệu. 1. Tính Pru¨fer code của cây sau: 2 3 0 45 1 2. Xây dựng cây có Pru¨fer code là (10,1,7, 4,3, 4,10,2,2, 8). 3. Dùng thuật toán Kruskal tìm cây bao trùm lớn nhất của đồ thị sau: 2 3 6 45 1 1 1 3 3 5 6 7 7 9 4. Một cây có n2 đỉnh bậc 2, n3 đỉnh bậc 3, · · · , nk đỉnh bậc k. Các đỉnh còn lại đều có bậc 1. Hỏi cây đó có bao nhiêu đỉnh bậc 1. Hãy giải thích. 1 25. Xét đồ thị dưới đây: (a) Hãy tìm cách gán thứ tự cho các đỉnh của đồ thị để thuật toán tham lam tô màu đồ thị này dùng ít màu nhất có thể. (b) Bạn hãy tô màu đồ thị này bằng thuật toán tham lam với thứ tự các đỉnh vừa làm ở câu (a). Giải thích xem tại sao thuật toán tham lam không thể tô đồ thị này bằng ít màu hơn. 6. Đồ thị Peterson trong bài 5 có phẳng không? Hãy giải thích. 37. Đồ thị sau đây có chu trình Hamilton không? Hãy giải thích. 8. Lấy một bộ bài gồm 52 quân. Mỗi quân bài có một chất và một gía trị. Có bốn chất: Rô, Cơ, Bích, Nhép; và có 13 giá trị: A, 2, 3, · · · , 10, J ,Q,K . Hãy đề nghị một người bạn xếp bài trên một lưới gồm 4 hàng và 13 cột. Chị ta có thể để các quân bài theo cách bất kỳ. Trong bài tập này, bạn sẽ chứng minh rằng bạn luôn có thể lấy 13 quân bài, mỗi quân từ một cột trên lưới, sao cho có đủ 13 giá trị. (a) Hãy mô hình bài toán này bằng cặp ghép trên đồ thị hai phần giữa 13 cột và 13 giá trị. (b) Chỉ ra rằng mọi nhóm gồm n cột phải chứa ít nhất n giá trị khác nhau và chứng minh rằng tồn tại cặp ghép. 49. Có năm sinh viên V,W,X ,Y, Z muốn thực tập tại năm công ty A,B,C ,D, E. Sau đây là danh sách xếp hạng mức độ ưa thích của các sinh viên và của các công ty (trái nhất là thích nhất): Sinh viên Công ty V A B C D E W B C D A E X C D A B E Y D A B C E Z A B C D E Công ty Sinh viên A W X Y Z V B X Y Z V W C Y Z V W X D Z V W X Y E V W X Y Z Hãy dùng thuật toán kén chồng để tìm một cặp ghép ổn định. 10. Chứng minh rằng trong 14 người luôn có 3 người đôi một quen nhau hoặc 5 người đôi một lạ nhau.