[Đề 120] - Đề 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.Số cạnh trong đồ thị vô hướng đầy đủ $34$ đỉnh là bao nhiêu?
Câu 2.Cho đồ thị đầy đủ $K_n$ với $n = 114$. Số cạnh $|E|$ bằng bao nhiêu?
Câu 3.$K_{83}$ (đồ thị đầy đủ $83$ đỉnh) có $|E| = ?$
Câu 4.Một cây (tree) có $n = 78$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 5.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 6.Số cạnh trong đồ thị vô hướng đầy đủ $21$ đỉnh là bao nhiêu?
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.Cho đồ thị đầy đủ $K_n$ với $n = 114$. Số cạnh $|E|$ bằng bao nhiêu?
Câu 10.Hỏi đồ thị $K_{10}$ với $n = 10$ có chu trình Euler 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ị $G = (V, E)$ vô hướng với $|E| = 65$. Giá trị của $\sum_v \deg(v)$ là bao nhiêu?
Câu 13.Cho cây nhị phân đầy đủ với chiều cao $20$. Hỏi số nút trong (không phải lá) bằng bao nhiêu?