Ma trận kề của đồ thị có hướng không phải là:
Đáp án đúng: A
Ma trận kề của đồ thị có hướng biểu diễn các cạnh nối giữa các đỉnh. Trong đồ thị có hướng, một cạnh có hướng từ đỉnh i đến đỉnh j không nhất thiết có nghĩa là có cạnh từ đỉnh j đến đỉnh i. Do đó, ma trận kề không nhất thiết phải đối xứng. Các ma trận đường chéo trên và đường chéo dưới cũng không phải là đặc điểm bắt buộc của ma trận kề đồ thị có hướng.
A. Ma trận đối xứng: Sai. Ma trận kề của đồ thị có hướng không nhất thiết phải đối xứng, vì một cạnh từ i đến j không đảm bảo có cạnh từ j đến i.
B. Ma trận đường chéo trên: Sai. Ma trận kề không bắt buộc phải là ma trận đường chéo trên.
C. Ma trận không đối xứng: Đúng. Ma trận kề của đồ thị có hướng thường không đối xứng vì tính chất có hướng của các cạnh.
D. Ma trận đường chéo dưới: Sai. Ma trận kề không bắt buộc phải là ma trận đường chéo dưới.
Vậy, đáp án đúng là A, B và D vì ma trận kề của đồ thị có hướng không phải là ma trận đối xứng, ma trận đường chéo trên, và ma trận đường chéo dưới.
Câu hỏi liên quan
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.
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.
