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:
Trả lời:
Đáp án đúng: C
Thuật toán Prim bắt đầu từ một đỉnh tùy ý, sau đó lặp đi lặp lại việc thêm cạnh có trọng số nhỏ nhất kết nối cây hiện tại với một đỉnh chưa thuộc cây. Ta có thể bắt đầu từ đỉnh số 2.
Bước 1: Chọn cạnh (2,6) vì nó có trọng số nhỏ nhất là 1. T = {(2,6)}
Bước 2: Chọn cạnh (6,3) vì nó có trọng số nhỏ nhất trong số các cạnh kết nối từ {2,6} đến các đỉnh chưa thuộc cây. T = {(2,6), (6,3)}
Bước 3: Chọn cạnh (3,5) vì nó có trọng số nhỏ nhất trong số các cạnh kết nối từ {2,6,3} đến các đỉnh chưa thuộc cây. T = {(2,6), (6,3), (3,5)}
Bước 4: Chọn cạnh (5,4) vì nó có trọng số nhỏ nhất trong số các cạnh kết nối từ {2,6,3,5} đến các đỉnh chưa thuộc cây. T = {(2,6), (6,3), (3,5), (5,4)}
Bước 5: Chọn cạnh (4,1) vì nó có trọng số nhỏ nhất trong số các cạnh kết nối từ {2,6,3,5,4} đến các đỉnh chưa thuộc cây. T = {(2,6), (6,3), (3,5), (5,4), (4,1)}
Bước 6: Chọn cạnh (4,7) vì nó có trọng số nhỏ nhất trong số các cạnh kết nối từ {2,6,3,5,4,1} đến các đỉnh chưa thuộc cây. T = {(2,6), (6,3), (3,5), (5,4), (4,1), (4,7)}
Vậy đáp án đúng là: B. T = {(5,3)(3,7)(2,3)(6,2)(4,1)(7,4)}. Tuy nhiên, các cạnh (3,7), (2,3) không có trên hình và (7,4) cũng sai, cạnh này phải là (4,7), do đó không có đáp án nào đúng
