Đa đồ thị liên thông G có chu trình Hamilton nếu:

Bậc của các đỉnh trong đồ thị -2

Bậc của các đỉnh trong đồ thị -n

Bậc của các đỉnh trong đồ thị -n/2

Bậc của các đỉnh trong đồ thị -n/4

Trả lời:

Đáp án đúng: C

Câu hỏi này không đầy đủ thông tin để đưa ra đáp án chính xác. Các đáp án đều không hợp lệ vì thiếu thông tin về điều kiện cần và đủ để một đa đồ thị liên thông có chu trình Hamilton. Cụ thể, các đáp án A, B, C, D đều đề cập đến 'bậc của các đỉnh trong đồ thị' nhưng lại dùng ký hiệu '-' không rõ ràng, và không đưa ra bất kỳ điều kiện nào liên quan đến số lượng đỉnh (n) để đảm bảo có chu trình Hamilton. Ví dụ, theo định lý Ore, một đồ thị đơn G với n đỉnh (n >= 3) có chu trình Hamilton nếu bậc của mọi đỉnh đều lớn hơn hoặc bằng n/2. Các phương án đưa ra không phản ánh đúng bất kỳ định lý hoặc điều kiện nào đã được chứng minh về chu trình Hamilton.

500+ câu hỏi trắc nghiệm Toán rời rạc có đáp án kèm giải thích - Phần 6

50 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 43:

Đồ thị đầy đủ K_n có số màu bằng:

Lời giải:

Đáp án đúng: B

Trong lý thuyết đồ thị, số màu của một đồ thị là số màu tối thiểu cần thiết để tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào có cùng màu. Đồ thị đầy đủ K_n là đồ thị mà mỗi cặp đỉnh phân biệt đều được nối với nhau bằng một cạnh.

Để tô màu đồ thị đầy đủ K_n, ta cần mỗi đỉnh một màu khác nhau, vì mọi đỉnh đều kề với tất cả các đỉnh còn lại. Do đó, số màu cần thiết để tô màu K_n là n.

Vậy đáp án đúng là B. n

Câu 44:

Cho đồ thị như hình vẽ. Kết quả khi duyệt đồ thị theo thuật toán BFS(K) là:

Lời giải:

Đáp án đúng: D

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng, tức là duyệt tất cả các đỉnh kề với một đỉnh trước khi duyệt các đỉnh ở mức sâu hơn. Bắt đầu từ đỉnh K, ta có các bước như sau:

1. K: Bắt đầu từ K.
2. Các đỉnh kề với K: A, I. Ta duyệt A trước I (thứ tự ưu tiên theo bảng chữ cái).
3. Các đỉnh kề với A: B, C, E. Ta duyệt theo thứ tự B, C, E.
4. Các đỉnh kề với I: Không có đỉnh nào mới (I chỉ kề với K).
5. Các đỉnh kề với B: Không có đỉnh nào mới.
6. Các đỉnh kề với C: D.
7. Các đỉnh kề với E: F, G.
8. Các đỉnh kề với D: Không có đỉnh nào mới.
9. Các đỉnh kề với F: H.
10. Các đỉnh kề với G: Không có đỉnh nào mới.
11. Các đỉnh kề với H: Không có đỉnh nào mới.

Vậy, thứ tự duyệt là: K, A, I, B, C, E, D, F, G, H.

Câu 45:

Một công thức được gọi là có dạng chuẩn tắc tuyển nếu …?

Lời giải:

Đáp án đúng: C

Công thức ở dạng chuẩn tắc tuyển (Disjunctive Normal Form - DNF) là một tuyển của các biểu thức hội cơ bản. Mỗi biểu thức hội cơ bản là một hội của các biến hoặc phủ định của biến. Do đó, đáp án C là đáp án chính xác.

Câu 46:

Giả sử p₁, p₂, …, p_n là các biến mệnh đề. Một biểu thức logic F theo các biến mệnh đề p₁, p₂, …, p_n được gọi là một biểu thức hội cơ bản nếu nó có dạng?

Lời giải:

Đáp án đúng: A

Câu hỏi yêu cầu xác định dạng của biểu thức hội cơ bản. Biểu thức hội cơ bản là phép hội (AND) của các biến mệnh đề hoặc phủ định của chúng. Phân tích các đáp án để tìm ra biểu thức phù hợp.

Câu 47:

Mệnh đề P→Q tương đương logic với mệnh đề nào sau đây?

Lời giải:

Đáp án đúng: B

Mệnh đề P→Q (P kéo theo Q) có thể được viết lại dưới dạng "¬P ∨ Q" (không P hoặc Q). Điều này xuất phát từ định nghĩa của phép kéo theo trong logic mệnh đề. Khi P đúng và Q sai, P→Q sai. Trong tất cả các trường hợp còn lại, P→Q đúng. Biểu thức "¬P ∨ Q" cũng đúng trong tất cả các trường hợp ngoại trừ khi P đúng và Q sai, do đó hai biểu thức này tương đương logic.

Câu 48:

Luật nào sau đây là luật kéo theo?

Lời giải: