Một người khách nước ngoài sang Việt Nam dự định thuê ô tô đi du lịch bằng cách lựa chọn xuất phát từ một tỉnh bất kỳ trong các tỉnh A, B, C, D, E và lần lượt đi qua các tỉnh còn lại (mỗi tỉnh đi qua một lần duy nhất) rồi quay trở về tỉnh ban đầu với thời gian (đơn vị: Giờ) đi giữa các tỉnh được cho như hình vẽ. Biết giá thuê xe ở thời điểm hiện tại là 50000 đồng/giờ và không thay đổi trong suốt hành trình. Hỏi chi phí tiền thuê xe ít nhất bằng bao nhiêu triệu đồng để người đó có thể hoàn thành chuyến đi của mình?

😎 Cùng DOL xem qua cách giải câu này nhé!

📃 Thông tin đề bài cho:

• Đồ thị vô hướng có 5 đỉnh: A, B, C, D, E.

• Trọng số các cạnh (đơn vị: giờ): AB=17,\ AE=8,\ AD=20,\ BC=12,\ BE=29,\ CE=19,\ CD=10,\ DE=9.

• Giá thuê ô tô là 50000 đồng/giờ và không đổi trong suốt hành trình.

• Cần đi qua mỗi đỉnh một lần duy nhất rồi quay về điểm xuất phát (chu trình Hamilton).

❓ Hiểu câu hỏi:

• Tìm chu trình Hamilton có tổng thời gian ngắn nhất.

• Tính tổng thời gian của chu trình đó (giờ).

• Nhân với giá thuê xe để được chi phí tối thiểu (triệu đồng).

🔎 Hướng dẫn cách làm:

• Chọn một chu trình ví dụ: A \to B \to C \to D \to E \to A.

• Tính tổng thời gian của chu trình trên:

  AB + BC + CD + DE + EA = 17 + 12 + 10 + 9 + 8 = 56\text{ giờ}.

• Kiểm tra các hoán vị khác cũng không cho tổng thời gian nhỏ hơn 56 giờ.

• Tính chi phí thuê xe:

  56\text{ giờ} \times 50000\text{ đồng/giờ} = 2800000\text{ đồng} = 2,8\text{ triệu đồng}.

✅ Đáp án: 2,8