Nếu bậc của mỗi đỉnh trong đồ thị đều chẵn thì:
Đáp án đúng: C
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
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ướ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\).
