Đề Toán rời rạc chương Đồ thị - đề 015 - 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.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
Câu 2.Trong $K_{18}$ (đồ thị đầy đủ $18$ đỉnh), có tồn tại chu trình Hamilton hay không?
Câu 3.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 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.Đồ thị đầy đủ $K_{44}$ (n = $44$) có chu trình Euler hay không?
Câu 6.Đồ thị đầy đủ $K_{76}$ (n = $76$) có chu trình Euler hay không?
Câu 7.Đồ thị vô hướng đầy đủ $K_{105}$ có bao nhiêu cạnh?
Câu 8.Một cây (tree) có $n = 22$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 9.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 10.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?
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.Cây nhị phân đầy đủ có chiều cao $h = 6$ (gốc ở mức 0). Số lá ở mức $6$ bằng bao nhiêu?
Câu 12.Đồ thị đơn vô hướng $21$ đỉnh có thể có nhiều nhất bao nhiêu cạnh?
Câu 13.Trong $K_{162}$ với $n = 162$ chẵn, mỗi đỉnh có bậc lẻ. Số cạnh tối thiểu phải thêm vào (giữa các đỉnh có sẵn) để mọi đỉnh có bậc chẵn (điều kiện chu trình Euler) là bao nhiêu?