[Đề 124] - Đề 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_{11}$ với $n = 11$ có chu trình Hamilton (đi qua mỗi đỉnh đúng 1 lần) không?
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.Trong $K_{18}$ (đồ thị đầy đủ $18$ đỉnh), có tồn tại chu trình Hamilton hay không?
Câu 4.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
Câu 5.Đồ thị đầy đủ $K_{44}$ (n = $44$) có chu trình Euler hay không?
Câu 6.Một cây (tree) có $n = 35$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 7.Đồ thị đầy đủ $K_{23}$ (n = $23$) có chu trình Hamilton hay không?
Câu 8.Trong $K_{42}$ (đồ thị đầy đủ $42$ đỉnh), có tồn tại chu trình Hamilton hay không?
Câu 9.Đồ thị đầy đủ $K_{23}$ (n = $23$) có chu trình Hamilton hay không?
Câu 10.Trong $K_{18}$ (đồ thị đầy đủ $18$ đỉnh), có tồn tại chu trình Hamilton 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.Một cây nhị phân đầy đủ với chiều cao $h = 9$ có bao nhiêu nút ở mức $h$ (tức số lá)?
Câu 12.Một đồ thị vô hướng $G$ có $|E| = 87$. Tính tổng $\sum_{v \in V} \deg(v)$.
Câu 13.Đồ thị $K_{18}$ (n = $18$, $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?