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:

Thuật toán Prim để tìm cây khung nhỏ nhất hoạt động như sau: 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.