Cho đồ thị trọng số G = (V, E) như hình vẽ. Cây khung nhỏ nhất H = (V, T) theo thuật toán Prim có tập cạnh là:

Thuật toán Prim để tìm cây khung nhỏ nhất bắt đầu từ một đỉnh, sau đó mở rộng cây bằng cách thêm các cạnh có trọng số nhỏ nhất mà kết nối cây hiện tại với một đỉnh chưa thuộc cây. Ta thực hiện thuật toán Prim như sau: 1. **Bắt đầu từ đỉnh 1:** * Các cạnh kề với đỉnh 1 là (1,2) = 5 và (1,8) = 4. Chọn cạnh (1,8) vì nó có trọng số nhỏ hơn. Vậy T = {(1,8)}. 2. **Mở rộng cây từ đỉnh 8:** * Các cạnh kề với đỉnh 8 là (8,2) = 2, (8,5) = 4, (8,3) = 8, và (1,8) đã có. * Chọn cạnh (8,2) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2)}. 3. **Mở rộng cây từ đỉnh 2:** * Các cạnh kề với đỉnh 2 là (2,4) = 7, (1,2) = 5, (8,2) = 2 (đã có). * Chọn cạnh (2,4) vì nó có trọng số nhỏ hơn các cạnh khác kề với các đỉnh đã có trong cây và đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4)}. 4. **Mở rộng cây từ đỉnh 4:** * Các cạnh kề với đỉnh 4 là (4,7) = 9, (2,4) = 7 (đã có). * Chọn cạnh (4,7) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7)}. 5. **Mở rộng cây từ đỉnh 7:** * Các cạnh kề với đỉnh 7 là (7,6) = 1, (4,7) = 9 (đã có), (7,5) = 3. * Chọn cạnh (7,6) vì nó có trọng số nhỏ nhất. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6)}. 6. **Mở rộng cây từ đỉnh 6:** * Các cạnh kề với đỉnh 6 là (6,3) = 5, (7,6) = 1 (đã có), (6,5) = 6. * Chọn cạnh (6,3) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3)}. 7. **Mở rộng cây từ đỉnh 3:** * Các cạnh kề với đỉnh 3 là (3,8) = 8, (3,6) = 5 (đã có). * Chọn cạnh (8,5) vì nó có trọng số nhỏ nhất và kết nối với đỉnh chưa có trong cây. Vậy T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}. Vậy, cây khung nhỏ nhất H = (V, T) có tập cạnh T = {(1,8), (8,2), (2,4), (4,7), (7,6), (6,3), (8,5)}. So sánh với các đáp án, ta thấy đáp án B phù hợp.