Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 14
(Sở Quảng Bình 2025) Một công ty vận tải cần giao hàng đến tất cả các thành phố $ A,B,C,D,E $ (hình vẽ bên dưới). Chi phí di chuyển giữa các thành phố được mô tả trên hình (đơn vị tính: triệu đồng). Xe giao hàng của công ty xuất phát từ một thành phố trong năm thành phố trên đi qua tất cả các thành phố còn lại đúng một lần sau đó trở lại thành phố ban đầu. Tìm chi phí thấp nhất của xe giao hàng.
Xem lời giải
Lời giải
Đáp án: $ 53 $.
Ta gọi mỗi đoạn thẳng nối giữa hai thành phố là một cạnh. Trong hình vẽ ta có 8 cạnh và tổng số chi phí ghi trong 8 cạnh này là: $ 10+9+11+12+13+14+14+8=91 $.
Nhận xét rằng xe phải đi qua 5 cạnh trong 8 cạnh của hình vẽ (bỏ đi hai cạnh chung đỉnh $ E $ và một cạnh không có đỉnh chung với hai cạnh đó).
Tổng số chi phí nhỏ nhất khi tổng số chi phí ba cạnh bỏ đi là lớn nhất. Ta xét các trường hợp sau:
TH1: Nếu bỏ đi ba cạnh $ EB,EA,CD $ thì tổng số chi phí bỏ đi là: $ 8+10+13=31 $.
TH2: Nếu bỏ đi ba cạnh $ EC,EB,AD $ thì tổng số chi phí bỏ đi là: $ 8+12+11=31 $.
TH3: Nếu bỏ đi ba cạnh $ ED,EC,AB $ thì tổng số chi phí bỏ đi là: $ 9+12+14=35 $.
TH4: Nếu bỏ đi ba cạnh $ ED,EA,BC $ thì tổng số chi phí bỏ đi là: $ 14+10+14=38 $.
Suy ra đường đi có tổng số chi phí nhỏ nhất là $ 91–38=53 $.
