›
›

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

Download
Đề thi giữa kỳ Toán rời rạc  
Thời gian 90 phút  
Đề 2  
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
1
0
4
5
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:  
1
2
3
6
5
1
3
7
7
9
1
6
4
5
3
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
2
5. 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.  
 
3
7. Đồ 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.  
4
9. 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  
Công ty  
Sinh viên  
V
W
X
Y
Z
A B C D E  
B C D A E  
A
B
C
D
E
W
X
Y
Z
V
X
Y
Z
V
W
Y
Z
V
W
X
Z
V
W
X
V
W
X
Y
Z
C
D A B E  
D A B C  
A B C D E  
E
Y
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.  
pdf 4 trang Thùy Anh 26/04/2022 9080
Download
Bạn đang xem tài liệu "Đề thi Giữa kì môn Toán rời rạc", để 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:

  • pdfde_thi_giua_ki_mon_toan_roi_rac.pdf