[Đề 122] - Đề Toán rời rạc chương Đồ thị · 13 câu
Phần I. Trắc nghiệm 4 phương án(10 câu)
Thí sinh trả lời từ câu 1 đến câu 10. Mỗi câu hỏi thí sinh chỉ chọn một phương án.
Câu 1.Hỏi đồ thị $K_{58}$ với $n = 58$ có chu trình Hamilton (đi qua mỗi đỉnh đúng 1 lần) không?
Câu 2.Hỏi đồ thị $K_{11}$ với $n = 11$ có chu trình Hamilton (đi qua mỗi đỉnh đúng 1 lần) không?
Câu 3.Đồ thị đầy đủ $K_{53}$ (n = $53$) có chu trình Hamilton hay không?
Câu 4.Một cây (tree) có $n = 84$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 5.Hỏi đồ thị $K_{18}$ với $n = 18$ có chu trình Hamilton (đi qua mỗi đỉnh đúng 1 lần) không?
Câu 6.Đồ thị $K_{20}$ (n = $20$) có tồn tại chu trình Euler đi qua mọi cạnh đúng 1 lần?
Câu 7.Đồ thị $K_{20}$ (n = $20$) có tồn tại chu trình Euler đi qua mọi cạnh đúng 1 lần?
Câu 8.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
Câu 9.Đồ thị $K_{20}$ (n = $20$) có tồn tại chu trình Euler đi qua mọi cạnh đúng 1 lần?
Câu 10.Đồ thị $K_{20}$ (n = $20$) có tồn tại chu trình Euler đi qua mọi cạnh đúng 1 lần?
Phần III. Tự luận(3 câu)
Thí sinh trả lời từ câu 11 đến câu 13. Thí sinh điền đáp án (số) vào ô trống.
Câu 11.Cho đồ thị đầy đủ $K_{86}$ với $n = 86$ (chẵn). Cần thêm ít nhất bao nhiêu cạnh để đồ thị có chu trình Euler?
Câu 12.Cho đồ thị vô hướng có $25$ cạnh. Hỏi tổng bậc của mọi đỉnh trong đồ thị?
Câu 13.Một cây nhị phân đầy đủ chiều cao $9$ (mỗi nút trong có $2$ con). Tính tổng số nút.