Đáp án đúng: A
Trong lý thuyết đồ thị, một cây là một đồ thị liên thông không có chu trình. Một tính chất quan trọng của cây là số cạnh của nó luôn ít hơn số đỉnh đúng 1. Vì vậy, nếu một cây có 1000 đỉnh, nó sẽ có 1000 - 1 = 999 cạnh.
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
Thuật toán Prim bắt đầu từ một đỉnh ngẫu nhiên và mở rộng cây bằng cách thêm các cạnh có trọng số nhỏ nhất kết nối cây hiện tại với các đỉnh chưa thuộc cây. Ta có thể bắt đầu từ đỉnh 1. 1. Bắt đầu từ đỉnh 1, cạnh có trọng số nhỏ nhất kề với 1 là (1,2) với trọng số 2. Thêm (1,2) vào T. T = {(1,2)}. 2. Các đỉnh đã xét: {1, 2}. Các cạnh kề với {1,2} là (1,8), (2,8), (2,4). Cạnh có trọng số nhỏ nhất là (1,8) với trọng số 4. Thêm (1,8) vào T. T = {(1,2), (1,8)}. 3. Các đỉnh đã xét: {1, 2, 8}. Các cạnh kề với {1, 2, 8} là (2,4), (8,3), (8,5). Cạnh có trọng số nhỏ nhất là (2,4) với trọng số 5. Thêm (2,4) vào T. T = {(1,2), (1,8), (2,4)}. 4. Các đỉnh đã xét: {1, 2, 8, 4}. Các cạnh kề với {1, 2, 8, 4} là (8,3), (8,5), (4,7). Cạnh có trọng số nhỏ nhất là (8,5) với trọng số 6. Thêm (8,5) vào T. T = {(1,2), (1,8), (2,4), (8,5)}. 5. Các đỉnh đã xét: {1, 2, 8, 4, 5}. Các cạnh kề với {1, 2, 8, 4, 5} là (8,3), (4,7), (5,7), (5,6). Cạnh có trọng số nhỏ nhất là (4,7) với trọng số 7. Thêm (4,7) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7)}. 6. Các đỉnh đã xét: {1, 2, 8, 4, 5, 7}. Các cạnh kề với {1, 2, 8, 4, 5, 7} là (8,3), (5,6), (7,6). Cạnh có trọng số nhỏ nhất là (5,6) với trọng số 8. Thêm (5,6) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7), (5,6)}. 7. Các đỉnh đã xét: {1, 2, 8, 4, 5, 7, 6}. Các cạnh kề là (8,3), (6,3). Cạnh có trọng số nhỏ nhất là (8,3) hoặc (6,3) với trọng số 9. Thêm (8,3) vào T. T = {(1,2), (1,8), (2,4), (8,5), (4,7), (5,6), (8,3)}. Vậy, T = {(1,2), (1,8), (8,5), (8,3), (5,6), (2,4), (4,7)}. Sắp xếp lại ta được T = {(1,2),(3,8),(8,5), (3,6), (6,7), (2,4), (4,7)}.
