Đề thi Toán rời rạc

Họ và tên:...................................................... MSSV:.................. TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . MSSV: . . . . . . . . . . . . . . . . . . . . . Học phần: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mã HP: . . . . . . . . . . . . . . . . . . . . Bài thi [X] giữa kỳ [ ] cuối kỳ . . . . . . . . . . . . Ngày thi: . . . . . . . . . . . . . . . . . Số thứ tự Điểm của bài thi Chữ ký của (các) cán bộ chấm thi Chữ ký của cán bộ coi thi Tờ .../ ... Đề thi giữa kỳ môn Toán Rời Rạc Thời gian: 90 phút. Không sử dụng tài liệu. Làm bài luôn vào đề thi. 1. Xét M là ghép cặp ký hiệu bởi các đường nét đậm trong đồ thị sau. A B C D E a b c d e (a) Tìm một đường mở cho M bắt đầu tại đỉnh b. (b) Dùng đường mở vừa tìm được để xây dựng ghép cặp M ′ kích thước 4. (c) Kiểm tra xem liệu còn đường mở nào cho M ′ không. Giải thích ngắn gọn. (d) Liệu M ′ có phải ghép cặp cực đại. 1 22. Ngày mai, Viện CNTT&TT sẽ có 10 cuộc họp. Các cuộc họp có thời gian như sau: Cuộc họp 1: 11h – 12h29 2: 15h – 16h29 3: 9h – 10h29 4: 11h – 12h29 5: 13h – 14h29 6: 9h – 12h29 7: 14h – 16h29 8: 9h – 10h29 9: 13h – 14h29 10: 15h – 16h29 Do tính riêng tư, tại một thời điểm, mỗi phòng họp chỉ diễn ra nhiều nhất một cuộc họp. Hãy xếp lịch họp cho Viện dùng ít phòng nhất. Hãy giải thích ngắn gọn tại sao cách xếp của bạn lại dùng ít phòng nhất. 3. Hãy dùng thuật toán Dijkstra để tìm đường đi ngắn nhất từ đỉnh A tới tất cả các đỉnh khác của đồ thị sau. Yêu cầu: Vẽ bảng mô tả thuật toán. A B C D E F G H 1 8 4 2 6 6 1 2 1 1 1 15 34. Xác định Pru¨fer code của cây sau: 2 3 0 45 1 6 5. Xây dựng cây với Pru¨fer code là (1,1,0,4, 2,0, 1,4). 6. Thực hiện thuật toán DFS trên đồ thị G sau. Vẽ rừng DFS với các thông tin post và pre trên mỗi đỉnh. Nếu cần quyết định thứ tự các đỉnh thăm, bạn hãy sử dụng thứ tự từ điển. Hãy liệt kê các cạnh ngược (back edge). A B C D E F G H I 7. Hãy tìm các thành phần liên thông mạnh của đồ thị trong bài tập 6. Gợi ý: Tính toán trên đồ thị GR và sử dụng thông tin post từ bài tập trước. 48. Có bốn sinh viên a, b, c, d muốn thực tập tại bốn công ty A,B,C ,D. 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 thích Công ty a A B C D b D C B A c A B C D d C D A B Công ty thích Sinh viên A a b c d B b a c d C a d c b D d c a b Hãy dùng thuật toán kén chồng để tìm một cặp ghép ổn định. Cặp ghép ổn định này có phải là duy nhất không? Tại sao? 9. Hãy mô tả một thuật toán nhận đầu vào là đồ thị có hướng G = (V, E), và xác định xem liệu có hay không một đỉnh s ∈ V thỏa mãn: từ s ta có thể tới được mọi đỉnh của G. Phân tích thời gian chạy của thuật toán và giải thích tại sao nó chạy đúng.