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 17
(Sở Long An 2025) Trong kì nghỉ hè bạn Phong muốn đi du lịch qua các địa điểm du lịch $ A,B,C,D,E $ như hình vẽ. Khoảng cách giữa các địa điểm du lịch như sau $ AB=16,BC=17,CD=11, DE=15,EA=14, $ $ AC=6,CE=20,EB=5,BD=3,DA=9 $ (đơn vị là km). Biết rằng số tiền bạn Phong phải trả cho 1 km là 15 000 đồng. Giả sử rằng bạn Phong xuất phát từ điểm $ A $ đi qua các điểm $ B,C,D,E $ đúng một lần sau đó trở về điểm $ A. $ Số tiền bạn Phong phải trả thấp nhất là bao nhiêu (kết quả làm tròn đến hàng nghìn)?
Xem lời giải
Lời giải
Đáp án: 585.
Bài toán yêu cầu tìm chu trình Hamilton ngắn nhất.
Ta thấy đồ thị có 5 đỉnh và mỗi đỉnh đều là bậc $ 4>\frac { 5 } { 2 } $ nên có chu trình Hamilton.
Áp dụng phương pháp láng giềng gần nhất, ta được chu trình:
$ ACDBEA=6+11+3+5+14=39{ \rm{ } }{ \rm{ k } }{ \rm{ m } }{ \rm{ . } } $
Dễ dàng thấy các chu trình khác đều lớn hơn $ 39{ \rm{ } }{ \rm{ k } }{ \rm{ m } } $ nên số tiền phải trả thấp nhất là
$ 39.15{ \rm{ } }000=585{ \rm{ } }{ \rm{ 0 } }{ \rm{ 0 } }{ \rm{ 0 } } $ đồng $ =585 $ nghìn đồng.
