[Đề 121] - Đề 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.Một cây (tree) có $n = 78$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 2.Một cây (tree) có $n = 22$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 3.Một cây (tree) có $n = 84$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 4.Số cạnh trong đồ thị vô hướng đầy đủ $34$ đỉnh là bao nhiêu?
Câu 5.Đồ thị đầy đủ $K_{53}$ (n = $53$) có chu trình Hamilton hay không?
Câu 6.Một cây (tree) có $n = 46$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 7.Một cây (tree) có $n = 12$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 8.Một cây (tree) có $n = 12$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 9.Một cây (tree) có $n = 12$ đỉnh. Số cạnh của cây bằng bao nhiêu?
Câu 10.Đồ thị đầy đủ $K_{82}$ (n = $82$) 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.Một đồ thị vô hướng có $|V| = 12$ đỉnh và $|E| = 11$ cạnh. Tính bậc trung bình $\bar d$ của đồ thị (giữ dạng phân số tối giản nếu cần).
Câu 12.Một đồ thị đơn vô hướng có $n = 77$ đỉnh. Hỏi đồ thị này có tối đa bao nhiêu cạnh?
Câu 13.Cho đồ thị liên thông $G$ với $|V| = 15$, $|E| = 34$. Số cạnh cần loại bỏ (giữ liên thông) để $G$ trở thành cây bằng bao nhiêu?