Đề thi kết thúc môn Toán rời rạc

Đề thi kết thúc môn Toán rời rạc Thời gian 90 phút. Không sử dụng tài liệu. 1. Thầy giáo muốn phát 25 cái bút chì cho An, Bình, Chi, và Dương sao cho An và Dương mỗi người có ít nhất một chiếc, Chi được không quá năm chiếc, và Bình được ít nhất bốn chiếc. Có bao nhiêu cách chia? 2. Cho dãy số a0, a1, a2, . . . thỏa mãn a0 = 2, a1 = 1 và an+2 − 5an+1 + 6an = 0 cho mọi n≥ 0. (a) Hãy xác định hàm sinh cho dãy số này; (b) Tìm công thức tính an qua n. 3. Chứng minh hoặc bác bỏ (bằng phản ví dụ) mệnh đề: “Mọi cây có đỉnh bậc k đều có ít nhất k đỉnh bậc 1.” 4. Hãy tìm cách tô màu đồ thị sau dùng ít màu nhất có thể. Tại sao số màu bạn dùng lại là ít nhất? 5. Liệu ta có thể ghép cặp đầy đủ cho đồ thị hai phần dưới đây không? Nếu có hãy chỉ ra một ghép cặp như vậy. Nếu không hãy chứng minh. A B C D E F a b c d e f 6. 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. a b c d e f g h 1 8 4 2 6 6 1 2 1 1 1 15 7. Hãy dùng thuật toán Prim và Kruskal để tìm hai cây bao trùm cho đồ thị của bài tập 6. 1 28. Hãy chạy thuật toán tìm các thành phần liên thông mạnh của đồ thị có hướng G sau đây. Khi chạy DFS trên GR: nếu cần chọn đỉnh để thăm, luôn chọn đỉnh theo thứ tự alphabet. g cba fed 9. Ta có ba bình thể tích 10 lít, 7 lít, và 4 lít. Ban đầu, bình 7 lít và 4 lít chứa đầy nước, còn bình 10 lít rỗng. Ta chỉ được phép sử dụng thao tác sau: Đổ hết lượng nước còn lại từ một bình sang một bình khác, chỉ dừng khi bình rỗng hoặc bình kia đầy. Bài toán đổ nước: Liệu với một dãy các thao tác này, ta có thể để lại đúng 2 lít nước trong bình 4 lít hoặc 2 lít nước trong bình 7 lít không? Để giải bài toán này, ta xây dựng đồ thị có hướng G = (V, E) trong đó: • Tập đỉnh V là các bộ ba số nguyên không âm (x , y, z) trong đó x , y và z tương ứng là lượng nước trong ba bình 10 lít, 7 lít và 4 lít. Ví dụ, đỉnh (0,7, 4) thể hiện: bình 10 lít rỗng, còn bình 7 lít và 4 lít chứa đầy nước. • Có cung nối từ đỉnh (x , y, z) tới đỉnh (x ′, y ′, z′) nếu từ (x , y, z) có thể sử dụng thao tác đổ nước như ở trên để thu được (x ′, y ′, z′). Ví dụ, (0,7,4)→ (4,7,0)→ (10,1,0) có nghĩa rằng ta đổ hết nước từ bình 4 lít sang bình 10 lít, và đổ đầy bình 10 lít từ bình 7 lít. Hãy chạy thuật toán DFS trên đồ thị G này bắt đầu từ đỉnh (0,7, 4) để tìm lời giải cho bài toán đổ nước. Yêu cầu: Vẽ cây DFS (không cần các cung nét đứt) bắt đầu từ đỉnh (0,7,4) 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 một thứ tự mà theo bạn là tự nhiên. 10. Giả sử mỗi đỉnh của một đồ thị có gắn một bóng đèn và một nút bấm. Khởi đầu, mọi bóng đèn đều sáng. Ấn một nút sẽ làm thay đổi trạng thái của bóng đèn tại đỉnh đó và mọi hàng xóm của nó. Chứng minh rằng người ta có thể ấn một vài nút sao cho mọi bóng đèn đều tắt.