Cho G =(V,E) là đồ thị vô hướng liên thông n đỉnh. Cây T =(V_T, E_T) được gọi là cây khung của đồ thị G nếu:

T liên thông và mỗi cạnh của nó đều là cầu.

Nếu thêm vào T một cạnh thì ta có ít nhất một chu trình

\({V_T} = V,{\rm{ }}{E_T} \times {\rm{ }}E\)

T liên thông, có đúng n cạnh và \({E_T} \times E.\)

Trả lời:

Đáp án đúng: C

Cây khung của một đồ thị vô hướng liên thông G=(V,E) là một cây T=(V_T, E_T) sao cho V_T = V và E_T là một tập con của E, đồng thời T liên thông và không có chu trình. Điều này có nghĩa là nếu thêm một cạnh vào T, ta sẽ tạo ra một chu trình. Do đó, đáp án đúng là phương án 2. Các phương án khác không đầy đủ hoặc không chính xác về định nghĩa cây khung. Cụ thể, phương án 1 nói về cạnh cầu, không phải là đặc điểm chính của cây khung. Phương án 3 sai vì E_T phải là tập con của E chứ không phải tích của hai tập này. Phương án 4 không đúng vì cây có n đỉnh thì phải có n-1 cạnh chứ không phải n cạnh.

525 câu trắc nghiệm môn Toán rời rạc kèm lời giải chi tiết - Phần 6

Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!

30 câu hỏi 60 phút

Bắt đầu thi

Câu hỏi liên quan

Câu 24:

Cho mạng G, điểm phát s điểm thu t. Lát cắt (X, Y) được gọi là lát cắt hẹp nhất nếu:

Lời giải:

Đáp án đúng: D

Lát cắt hẹp nhất trong mạng G, với điểm phát s và điểm thu t, là lát cắt có khả năng thông qua nhỏ nhất trong tất cả các lát cắt phân tách s và t. Điều này có nghĩa là, trong tất cả các cách cắt mạng thành hai tập hợp X và Y sao cho s thuộc X và t thuộc Y, lát cắt (X, Y) có tổng khả năng thông qua của các cung từ X sang Y là nhỏ nhất. Do đó, đáp án chính xác là khả năng thông qua của lát cắt (X,Y) bé nhất.

Câu 25:

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

Lời giải:

Đáp án đúng: C

Thuật toán BFS (Breadth-First Search) duyệt đồ thị theo chiều rộng. Bắt đầu từ đỉnh K, ta duyệt các đỉnh kề với K (B, F, H). Sau đó, duyệt các đỉnh kề với B (A, C), rồi các đỉnh kề với F (D, E), và cuối cùng các đỉnh kề với H (G, I). Như vậy, thứ tự duyệt sẽ là: K, B, F, H, A, C, D, E, G, I.

Câu 26:

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 (OR) của các mệnh đề hội (AND). Mỗi mệnh đề hội này được gọi là một biểu thức hội cơ bản. Vì vậy, đáp án đúng là "Nó là tuyển của các biểu thức hội cơ bản".

Câu 27:

Xác định chân trị của biểu thức (\(\neg \)X→ \(\neg \)Y ) v (\(\neg \)Y → \(\neg \)Z ) và (\(\neg \)X → \(\neg \)Z) khi X = Y=0, Z= 1?

Lời giải:

Đáp án đúng: C

Để xác định chân trị của biểu thức logic, ta thay các giá trị X = 0, Y = 0, và Z = 1 vào biểu thức và tính toán:

(¬X → ¬Y) v (¬Y → ¬Z) và (¬X → ¬Z)

Với X = 0, Y = 0, Z = 1:

¬X = ¬0 = 1

¬Y = ¬0 = 1

¬Z = ¬1 = 0

Thay vào biểu thức thứ nhất: (¬X → ¬Y) v (¬Y → ¬Z) = (1 → 1) v (1 → 0) = 1 v 0 = 1

Thay vào biểu thức thứ hai: (¬X → ¬Z) = (1 → 0) = 0

Vậy, chân trị của biểu thức lần lượt là 1 và 0.

Câu 28:

Câu nào sau đây KHÔNG phải là một mệnh đề:

Lời giải:

Đáp án đúng: A

Mệnh đề là một câu khẳng định có tính đúng hoặc sai. Trong các phương án trên, "Có ai ở nhà không?" là một câu hỏi, không phải là một khẳng định và do đó không phải là một mệnh đề.

Câu 29:

Có bao nhiêu cạnh trong đồ thị có 8 đỉnh, mỗi đỉnh có bậc là 10?

Lời giải: