ĐỀ THI TOÁN RỜI RẠC Kỳ II 2006 - 2007

Phát biểu + Chứng minh công thức Euler về mối quan hệsố miền, số đỉnh, số cạnh trong 1 biểu diễn phẳng của 1 đơn đồthị phẳng , liên thông.
Nội dung trích xuất từ tài liệu:
ĐỀ THI TOÁN RỜI RẠC Kỳ II 2006 - 2007 ĐỀ THI TOÁN RỜI RẠC Kỳ II 2006 - 2007Câ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. ̉ ̉ ́ ́ ̉ ́ ́ ̉ ̉