ĐỀ THI TOÁN RỜI RẠC
Kỳ II 2006 - 2007
Câu 1: Định nghia đồ thị phăng + tô mau đồ thị
̃ ̉ ̀
Câu 2: Phat biêu KQ (ko CM) cua số đương đi độ dai r nôi 2 đinh
́ ̉ ̉ ̀ ́ ̉
cua 1 đơn đồ thị và điêu kiên cân và đủ để 1 đồ thị ko phăng (dl
̉ ̀ ̣ ̀ ̉
Kuratowski)
Câu 3: Phát biểu + Chứng minh công thức Euler về môi quan hệ
́
số miên, số đinh, số canh trong 1 biểu diễn phăng cua 1 đơn đồ
̀ ̉ ̣ ̉ ̉
thị phăng , liên thông.
̉
Câu 4: Áp dụng thuât toan dijkstra tìm đương đi ngắn nhất.
̣ ́
Câu 5 là cho biêu thức hâu tố *2+3-|5yx-*+(| là dâu mui tên cua mũ
́ ̣ ́ ̃ ̉
y) a.Xac đinh bt đó b.Viêt bt dươi dang tiên tố
́ ́ ̣ ́ ̣ ̀
Câu 6: Dung ký thuât quay lui hay tim 1 tâp con A cua tâp hơp
̀ ̣ ̃ ̀ ̣ ̉ ̣
X={35;25;18;15;9;5;3} sao cho tông cac số trong tâp A đung = 42
̉ ́ ̣ ́
Câu 7: là cho ham Boole F cua 3 biên x,y,z có tinh chât sau vơi
̀ ̉ ́ ́ ́
̣
moi x,y,z F(x ngang,y,z)= F(x,y ngang,z)= F(x,y,z ngang)=
F((x,y,z)ngang) Biêt F(0,0,0 = 1) lâp bang giá trị cua F, sau đó khai
́ ̣ ̉ ̉
triên tông cac tich và khai triên tich cac tông cua F.
̉ ̉ ́ ́ ̉ ́ ́ ̉ ̉