Câu 20THPT#Toán rời rạc - Đồ thị#Bài toán người du lịch
Thuộc đề: Đề thi thử tốt nghiệp THPT năm 2025 môn Toán sở GD&ĐT Quảng BìnhCâ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.


Đáp án chính thức: 53
Hướng dẫn giải chi tiết
Xét các chu trình Hamilton đi qua đỉnh : chu trình có tổng chi phí là (triệu đồng), là chi phí thấp nhất.