Câu 66: Một công ty viễn thông đang lên kế hoạch mở rộng mạng lưới dịch vụ của mình tại một khu vực gồm sáu thị trấn: $A, B, C, D, E$ và $F$. Để cung cấp dịch vụ internet và điện thoại đến từng thị trấn, công ty cần phải kéo cáp ngầm nối các thị trấn với nhau. Mỗi đoạn cáp nối hai thị trấn có một chi phí nhất định, tùy thuộc vào khoảng cách địa lý và điều kiện địa hình. Sơ đồ dưới đây thể hiện các tuyến cáp có thể xây dựng, cùng với chi phí đi kèm (tính bằng nghìn đô la) cho từng tuyến.
Chi phí tối thiểu (nghìn đô la) mà công ty phải bỏ ra để xây dựng hệ thống cáp sao cho tất cả sáu thị trấn đều được kết nối với nhau là:
A. 780
B. 820
C. 760
D. 800
Đáp án đúng: A.
Công thức, Lý thuyết và Phương pháp giải
Lý thuyết
- Đồ thị: Tập hợp các đỉnh (thị trấn) và các cạnh (tuyến cáp) nối chúng.
- Cây khung (Spanning Tree): Là một đồ thị con chứa tất cả các đỉnh của đồ thị ban đầu, liên thông và không có chu trình. Với $n$ đỉnh, cây khung sẽ có đúng $n-1$ cạnh.
- Cây khung nhỏ nhất (MST): Là cây khung có tổng trọng số (chi phí) của các cạnh là nhỏ nhất.
Phương pháp giải: Thuật toán Kruskal
Đây là phương pháp nhanh nhất cho các bài toán trắc nghiệm:
- Liệt kê tất cả các cạnh theo thứ tự trọng số từ nhỏ đến lớn.
- Lựa chọn lần lượt các cạnh có trọng số nhỏ nhất.
- Điều kiện: Nếu việc thêm một cạnh tạo thành một chu trình (vòng khép kín) thì bỏ qua cạnh đó.
- Dừng lại khi đã chọn đủ $n-1$ cạnh (ở bài này là $6-1 = 5$ cạnh).
Bài giải chi tiết hoàn chỉnh
Dựa vào sơ đồ, ta có danh sách các cạnh và chi phí tương ứng:
- $BD = 100$
- $BE = 120$
- $AC = 140$
- $DF = 160$
- $DE = 180$
- $EF = 220$
- $CD = 260$
- $AB = 300$
Các bước thực hiện thuật toán Kruskal:
- Chọn cạnh $BD$ (chi phí $100$).
- Chọn cạnh $BE$ (chi phí $120$).
- Chọn cạnh $AC$ (chi phí $140$).
- Chọn cạnh $DF$ (chi phí $160$).
- Lúc này đã có 4 cạnh nối các đỉnh: $\{A, C\}$ và $\{B, D, E, F\}$.
- Xét cạnh tiếp theo là $DE$ (chi phí $180$): Loại, vì $B, D, E$ đã tạo thành một phần của mạng lưới, thêm $DE$ sẽ tạo chu trình $B-D-E-B$.
- Xét cạnh tiếp theo là $EF$ (chi phí $220$): Loại, vì tạo chu trình $B-D-F-E-B$.
- Chọn cạnh $CD$ (chi phí $260$): Nhận, vì nó kết nối hai cụm $\{A, C\}$ và $\{B, D, E, F\}$ lại với nhau.
Tổng chi phí tối thiểu là:
$$T = 100 (BD) + 120 (BE) + 140 (AC) + 160 (DF) + 260 (CD)$$
$$T = 780$$
Đáp án đúng: A.
Cách giải nhanh bằng Trắc nghiệm
Khi làm trắc nghiệm, bạn không cần viết ra, chỉ cần dùng bút chì khoanh trực tiếp vào hình:
- Tìm số bé nhất: Khoanh $100$.
- Số bé tiếp theo: Khoanh $120$, $140$, $160$.
- Đếm số cạnh: Đã được $4$ cạnh. Cần $5$ cạnh cho $6$ thị trấn.
- Xét số tiếp theo là $180$: Thấy nó tạo thành tam giác $BDE \rightarrow$ Bỏ qua.
- Xét số tiếp theo là $220$: Thấy nó tạo thành vòng khép kín $B-D-F-E \rightarrow$ Bỏ qua.
- Xét số tiếp theo là $260$: Nhận (nối được điểm $C$ vào cụm còn lại).
- Cộng nhẩm: $100+120+140+160+260 = 780$.
Mẹo nhỏ: Luôn nhớ nguyên tắc “Không tạo vòng khép kín” và “Số cạnh = Số đỉnh – 1”.