Đề Toán rời rạc chương Đồ thị - đề 013 - năm 2026
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.Đồ thị đầy đủ $K_{23}$ (n = $23$) có chu trình Hamilton hay không?
Câu 2.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
Câu 3.Số cạnh trong đồ thị vô hướng đầy đủ $34$ đỉnh là bao nhiêu?
Câu 4.Một cây (tree) có $n = 46$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 5.Trong $K_{42}$ (đồ thị đầy đủ $42$ đỉnh), có tồn tại chu trình Hamilton hay 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.$K_{83}$ (đồ thị đầy đủ $83$ đỉnh) có $|E| = ?$
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ị đầy đủ $K_{44}$ (n = $44$) có chu trình Euler hay không?
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.Đồ thị $K_{38}$ (n = $38$, $n$ chẵn) cần thêm tối thiểu bao nhiêu cạnh (giữa các đỉnh đã có) để có chu trình Euler?
Câu 12.Đồ thị vô hướng (đơn) có số cạnh $|E| = 65$. Theo bổ đề bắt tay, tổng bậc các đỉnh bằng bao nhiêu?
Câu 13.Cây nhị phân đầy đủ có chiều cao $h = 6$ (gốc ở mức 0). Tính số nút trong (không phải lá) của cây.