Cho đồ thị vô hướng trọng số trên cạnh G = (V, E) trong đó V = {1,2,3,4,5,6} và E = {(1,2), (1,3), (1,6), (2,3), (2,5), (2,6), (4,5), (4,6), (5,6)}. Trọng số trên cạnh w(1,2) = 1, w(1,3) = 1, w(1,6) = 4, w(2,3) = 1, w(2,5) = 2, w(2,6) = 2, w(4,5) = 3, w(4,6) = 5, w(5,6) = 2. Hỏi cây khung nhỏ nhất của G có trọng số bằng bao nhiêu?
Trả lời:
Đáp án đúng: A
Để tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) của đồ thị G, ta có thể sử dụng thuật toán Prim hoặc Kruskal. Ở đây, tôi sẽ sử dụng thuật toán Kruskal, vì nó thường dễ thực hiện bằng tay hơn trong trường hợp đồ thị nhỏ.
1. **Sắp xếp các cạnh theo trọng số tăng dần:**
- (1,2): 1
- (1,3): 1
- (2,3): 1
- (2,5): 2
- (2,6): 2
- (5,6): 2
- (4,5): 3
- (1,6): 4
- (4,6): 5
2. **Chọn các cạnh theo thứ tự, đảm bảo không tạo thành chu trình:**
- Chọn (1,2): 1
- Chọn (1,3): 1
- Chọn (2,3): 1 (loại, tạo chu trình 1-2-3-1)
- Chọn (2,5): 2
- Chọn (2,6): 2
- Chọn (5,6): 2 (loại, tạo chu trình 2-5-6-2)
- Chọn (4,5): 3
- Chọn (1,6): 4 (loại)
- Chọn (4,6): 5 (loại)
Như vậy, các cạnh được chọn là:
- (1,2): 1
- (1,3): 1
- (2,5): 2
- (2,6): 2
- (4,5): 3
Tổng trọng số của cây khung nhỏ nhất là: 1 + 1 + 2 + 2 + 3 = 9.
Vậy đáp án đúng là B. 9
