Câu 20THPTChuyên đề: Chu trình Hamilton • Lớp 11Vận dụng#Toán rời rạc - Đồ thị#Bài toán người du lịch
Câu 4. Một công ty vận tải cần giao hàng đến tất cả các thành phố (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.

Câu 4. Một công ty vận tải cần giao hàng đến tất cả các thành phố (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.


Phương pháp & hướng dẫn giải
Phương pháp & hướng dẫn giải: Xét các chu trình Hamilton đi qua 5 đỉnh A, B, C, D, E: chu trình A - B - E - C - D - A có tổng chi phí là 9 + 8 + 12 + 13 + 11 = 53 (triệu đồng), là chi phí thấp nhất. Xem đáp án chính thức và trọn bộ lời giải chi tiết từng bước câu hỏi thuộc Đề Thi Thử Tốt Nghiệp THPT 2025 Môn Toán Sở GD&ĐT Quảng Bình trên dethichuan.com.

