Số đỉnh bậc lẻ trong đồ thị G vô hướng:
Đáp án đúng: C
Trong đồ thị vô hướng, tổng bậc của tất cả các đỉnh bằng hai lần số cạnh. Vì vậy, tổng bậc của tất cả các đỉnh là một số chẵn. Để tổng này là một số chẵn, số lượng đỉnh bậc lẻ phải là một số chẵn. Vì nếu số đỉnh bậc lẻ là một số lẻ, thì tổng bậc của các đỉnh bậc lẻ sẽ là một số lẻ, và do đó tổng bậc của tất cả các đỉnh cũng sẽ là một số lẻ, điều này mâu thuẫn với thực tế là tổng bậc phải là một số chẵn.
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!
Câu hỏi liên quan
Bước 1: Bắt đầu từ đỉnh 2. Các cạnh kề với đỉnh 2 là (2,3) = 5, (2,6) = 6, (2,5) = 2. Chọn cạnh (2,5) = 2. T = {(2,5)}.
Bước 2: Các đỉnh đã xét {2,5}. Các cạnh kề với {2,5} là (2,3) = 5, (2,6) = 6, (5,4) = 4. Chọn cạnh (5,4) = 4. T = {(2,5), (5,4)}.
Bước 3: Các đỉnh đã xét {2,5,4}. Các cạnh kề là (2,3) = 5, (2,6) = 6, (4,1) = 3, (4,7) = 5. Chọn cạnh (4,1) = 3. T = {(2,5), (5,4), (4,1)}.
Bước 4: Các đỉnh đã xét {2,5,4,1}. Các cạnh kề là (2,3) = 5, (2,6) = 6, (4,7) = 5, (1,3) = 9. Chọn cạnh (2,3) = 5. T = {(2,5), (5,4), (4,1), (2,3)}.
Bước 5: Các đỉnh đã xét {2,5,4,1,3}. Các cạnh kề là (2,6) = 6, (4,7) = 5, (3,6) = 8, (3,7) = 7. Chọn cạnh (4,7) = 5. T = {(2,5), (5,4), (4,1), (2,3), (4,7)}.
Bước 6: Các đỉnh đã xét {2,5,4,1,3,7}. Các cạnh kề là (2,6) = 6, (3,6) = 8, (7,6) = 1. Chọn cạnh (7,6) = 1. T = {(2,5), (5,4), (4,1), (2,3), (4,7), (7,6)}.
Vậy T = {(2,5), (5,4), (4,1), (2,3), (4,7), (6,7)}. Không có đáp án nào hoàn toàn chính xác.
Tuy nhiên, đáp án gần đúng nhất là phương án 2, sai khác ở cạnh (7,4) thay vì (7,6) và (5,3) thay vì (5,4), nhưng có đủ số lượng cạnh và các đỉnh liên quan.
Do không có đáp án chính xác, ta xem xét các cạnh có trọng số nhỏ nhất được chọn trong quá trình duyệt Prim. Cụ thể, ta cần các cạnh: (4,1), (2,3), (5,4), (2,5), và thêm 2 cạnh nữa để tạo thành cây khung.
So sánh với các đáp án, ta thấy:
- Đáp án 1: Sai hoàn toàn.
- Đáp án 2: Có (4,1), (2,3). Các cạnh còn lại có thể xem xét được.
- Đáp án 3: Có (4,1), (2,3). Tuy nhiên cạnh (5,1) không hợp lý.
- Đáp án 4: Có (2,3), (4,1).
Như vậy, đáp án 2 là gần đúng nhất, dù không hoàn toàn chính xác.
Ta có thể biến đổi mệnh đề \(\overline Q \vee (P \wedge Q)\) như sau:
\(\overline Q \vee (P \wedge Q) \equiv (\overline Q \vee P) \wedge (\overline Q \vee Q)\)
Vì \(\overline Q \vee Q\) luôn đúng (là hằng đúng), nên:
\((\overline Q \vee P) \wedge (\overline Q \vee Q) \equiv \overline Q \vee P \equiv P \vee \overline Q\)
Vậy, mệnh đề \(\overline Q \vee (P \wedge Q)\) tương đương logic với mệnh đề \(P \vee \overline Q\).
1. Nhóm 4 ô ở góc trên bên trái (00, 01, 11, 10) khi A'B' = 1. Đây là một tế bào tối đại vì nó bao gồm tất cả các ô có thể nhóm được trong khu vực này.
2. Nhóm 4 ô ở góc dưới bên phải (11, 10, 00, 01) khi AB = 1. Đây là một tế bào tối đại vì nó bao gồm tất cả các ô có thể nhóm được trong khu vực này.
Như vậy, có 2 tế bào tối đại trong bảng Karnaugh này.
