Đồ thị lập phương Qn là đồ thị:
2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau một bit.
2n đỉnh, mỗi đỉnh kề nhau chỉ khác nhau nhiều nhất 2 bit.
2n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit
n đỉnh, mỗi đỉnh được biểu diễn bởi một xâu bit độ dài n sao cho hai đỉnh kề nhau chỉ khác nhau một bit.
Đá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
1. Khởi tạo: Chọn một đỉnh bất kỳ làm đỉnh bắt đầu. Trong ví dụ này, ta có thể chọn đỉnh 1.
2. Lặp:
* Tìm cạnh có trọng số nhỏ nhất nối đỉnh đã chọn với một đỉnh chưa được chọn.
* Thêm cạnh này vào cây khung.
* Thêm đỉnh mới vào tập các đỉnh đã chọn.
3. Kết thúc: Lặp lại bước 2 cho đến khi tất cả các đỉnh đều thuộc cây khung.
Áp dụng thuật toán Prim cho đồ thị đã cho:
1. Bắt đầu từ đỉnh 1.
2. Các cạnh kề với đỉnh 1: (1,4) = 5, (1,5) = 9. Chọn cạnh (1,4) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4)}.
3. Các đỉnh đã chọn: {1, 4}.
4. Các cạnh kề với {1, 4}: (1,5) = 9, (4,7) = 2, (4,5) = 5. Chọn cạnh (4,7) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7)}.
5. Các đỉnh đã chọn: {1, 4, 7}.
6. Các cạnh kề với {1, 4, 7}: (1,5) = 9, (4,5) = 5, (7,3) = 3. Chọn cạnh (7,3) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3)}.
7. Các đỉnh đã chọn: {1, 4, 7, 3}.
8. Các cạnh kề với {1, 4, 7, 3}: (1,5) = 9, (4,5) = 5, (3,2) = 4, (3,5) = 6, (3,6) = 7. Chọn cạnh (3,2) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2)}.
9. Các đỉnh đã chọn: {1, 4, 7, 3, 2}.
10. Các cạnh kề với {1, 4, 7, 3, 2}: (1,5) = 9, (4,5) = 5, (3,5) = 6, (3,6) = 7, (2,5) = 8, (2,6) = 1. Chọn cạnh (2,6) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2), (2,6)}.
11. Các đỉnh đã chọn: {1, 4, 7, 3, 2, 6}.
12. Các cạnh kề với {1, 4, 7, 3, 2, 6}: (1,5) = 9, (4,5) = 5, (3,5) = 6, (6,5) = 3. Chọn cạnh (6,5) vì có trọng số nhỏ nhất. Tập cạnh T = {(1,4), (4,7), (7,3), (3,2), (2,6), (6,5)}.
13. Các đỉnh đã chọn: {1, 4, 7, 3, 2, 6, 5}.
Vậy cây khung nhỏ nhất H = (V, T) có tập cạnh T = {(4,1), (7,4), (3,7), (2,3), (6,2), (5,6)} tương ứng với đáp án T ={(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)} sau khi sắp xếp lại các đỉnh.
Ta có: \(\overline Q \vee (P \wedge Q) \equiv (\overline Q \vee P) \wedge (\overline Q \vee Q) \equiv (\overline Q \vee P) \wedge 1 \equiv \overline Q \vee P\)
Hay \(P \vee \overline Q \)
Luật kéo theo (hay còn gọi là luật suy ra) trong logic mệnh đề phát biểu rằng: một mệnh đề kéo theo \(p \to q\) tương đương với mệnh đề phủ định của \(p\) hoặc \(q\). Hay nói cách khác, \(p \to q\) đúng khi và chỉ khi \(p\) sai hoặc \(q\) đúng.
Công thức chính xác của luật kéo theo là: \(p \to q \Leftrightarrow \overline{p} \vee q\)
Vậy, đáp án đúng là đáp án 1.
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.
Trong đồ thị đã cho, ta thấy các đỉnh a, k, m, c, d, h đều có bậc lẻ. Do đó, đồ thị không phải là đồ thị Euler.
Vậy đáp án đúng là: Không, vì nó chứa các đỉnh bậc lẻ (a,k,m,c,d,h)
