Cho G = (V, E) là đồ thị vô hướng liên thông n đỉnh. T = (VT, ET) được gọi là cây khung của đồ thị G nếu:
Đá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 = (VT, ET) thỏa mãn các điều kiện sau:
- T liên thông.
- T không chứa chu trình.
- T chứa tất cả các đỉnh của G, tức là VT = V.
Như vậy, đáp án C là đáp án chính xác nhất vì nó bao gồm tất cả các điều kiện cần thiết để T là một cây khung của G.
Câu hỏi liên quan
1. Bắt đầu tại C: Thuật toán bắt đầu từ đỉnh C.
2. Thăm A: Từ C, thuật toán thăm đỉnh A.
3. Thăm E: Từ A, thuật toán thăm đỉnh E (vì E đứng trước B theo thứ tự bảng chữ cái).
4. Thăm G: Từ E, thuật toán thăm đỉnh G.
5. Quay lui và thăm B: Từ G, không có đỉnh nào để đi tiếp, quay lại E rồi đến A. Từ A, thuật toán thăm đỉnh B.
6. Thăm D: Từ B, thuật toán thăm đỉnh D.
7. Thăm F: Từ D, thuật toán thăm đỉnh F.
8. Thăm H: Từ F, thuật toán thăm đỉnh H.
9. Thăm K: Từ H, thuật toán thăm đỉnh K.
10. Thăm I: Từ K, thuật toán thăm đỉnh I.
11. Thăm N: Từ I, thuật toán thăm đỉnh N.
Vậy thứ tự duyệt đúng là: C, A, E, G, B, D, F, H, K, I, N
Công thức có dạng chuẩn tắc hội (CNF - Conjunctive Normal Form) là một công thức logic mệnh đề được biểu diễn dưới dạng hội của các mệnh đề tuyển. Mỗi mệnh đề tuyển là một tuyển của các literal (biến hoặc phủ định của biến). Biểu thức hội cơ bản còn được gọi là mệnh đề tuyển (clause). Như vậy, một công thức được gọi là có dạng chuẩn tắc hội nếu nó là hội của các biểu thức tuyển cơ bản.
Ta có P → Q sai khi và chỉ khi P đúng và Q sai.
Khi đó, P Λ Q sai (vì Q sai) và Q → P đúng (vì Q sai).
Vậy, chân trị của P Λ Q là 0 và của Q → P là 1.
* Đáp án A: Quy bài toán ban đầu về bài toán con đơn giản hơn là phương pháp chia để trị hoặc quy nạp.
* Đáp án B: Giả sử điều cần chứng minh là sai để từ đó suy ra mâu thuẫn là định nghĩa chính xác của phương pháp phản chứng.
* Đáp án C: Liệt kê tất cả các khả năng để từ đó đưa ra quyết định là phương pháp vét cạn hoặc duyệt.
* Đáp án D: Biểu diễn nghiệm của bài toán bằng các dữ kiện ban đầu là một cách giải bài toán, nhưng không phải là phương pháp phản chứng.
