ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH ĐỀ THI CUỐI KỲ MÔN CTRR
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN Học kỳ I, năm học 2019-2020
BỘ MÔN TOÁN – LÝ Ngày thi: /01/2020
Thời gian làm bài: 90 phút
Không được sử dụng tài liệu
Câu 1. (4 điểm) Cho hàm Boole 4 biến
( , , , )f x y z t
, biết
1
(1) {1010, 0110,1111, 0111,1101,1000,1100}
f.
a) Hãy tìm dạng nối rời chính tắc của hàm f.
b) Hãy tìm các công thức đa thức tối tiểu của hàm f.
c) Hãy vẽ sơ đồ mạch cho một công thức đa thức tối tiểu của hàm f vừa tìm được.
Câu 2. (1 điểm) Có thể có một nhóm gồm 9 người trong đó mỗi người đều chỉ quen biết đúng 5
người khác trong nhóm hay không?
Câu 3. (5 điểm)
Cho đồ thị vô hướng, liên thông, có trọng số như sau:
a) Đồ thị có chu trình (đường đi) Euler không? Tại sao? Nếu có hãy chỉ ra một chu trình
(đường đi) Euler của đồ thị.
b) Hãy chỉ ra một chu trình (đường đi) Hamilton của đồ thị nếu có.
c) Hãy tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh còn lại của đồ thị (chỉ rõ thuật
toán).
b) Hãy tìm cây khung có trọng số lớn nhất T của đồ thị (chỉ rõ thuật toán) và tính trọng số
của T.
------------------------------------
Hết
Cán bộ coi thi không giải thích gì thêm
Trưởng BM Toán - Lý
CAO THANH TÌNH
