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 52
(Sở Nam Đị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 vẽ. Xe giao hàng của công ty xuất phát từ một 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: 35.
Bài toán yêu cầu xuất phát từ 1 đỉnh trong 5 đỉnh (5 thành phố) $ A $; $ B $; $ C $; $ D $; $ E $ và quay lại điểm xuất phát ban đầu với chi phí thấp nhất.
Như vậy, với yêu cầu trên mỗi đỉnh cần 2 con đường (1 đi vào và 1 đi ra) nghĩa là mỗi đỉnh đó sẽ là đỉnh bậc 2. Để chi phí thấp nhất ta chỉ cần 5 con đường để nối 5 đỉnh đó là tối ưu.
Theo hình vẽ có 8 con đường ta cần bỏ đi 3 con đường (với tổng chi phí cao nhất).
Ta thấy đỉnh E bậc 4 và kết nối với các đỉnh còn lại nên ta sẽ bỏ đi 2 con đường (liền kề) từ đỉnh này và bỏ đi con đường đối diện của nó.
Ta xét các khả năng:
$ • $ Bỏ $ EA+ED+BC $: $ 6+9+9=24 $.
$ • $ Bỏ $ EA+EB+CD $: $ 6+10+5=21 $.
$ • $ Bỏ $ EB+EC+AD $: $ 10+6+7=23 $.
$ • $ Bỏ $ EC+ED+AB $: $ 6+9+7=22 $.
Khi đó, ta sẽ bỏ đi các con đường $ EA+ED+BC $: $ 6+9+9=24 $ vì chi phí cao nhất.
Vậy chi phí thấp nhất của xe giao hàng thỏa yêu cầu bài toán là tổng chi phí các con đường còn lại: $ 7+10+6+5+7=35 $.
