Câu 18THPT#Lý thuyết đồ thị#Bài toán người đưa thư
Thuộc đề: Đề thi thử tốt nghiệp THPT 2025 môn Toán lần 2 sở GD&ĐT Bình Phước (Mã đề 0101)Mạng lưới giao thông ở một thành phố được mô phỏng như hình vẽ bên dưới, trong đó là các điểm nút giao thông, số ghi trên mỗi cạnh trong hình vẽ là khoảng cách giữa hai điểm đầu và cuối của con đường đó (đơn vị là ). Một khách du lịch muốn đi tham quan thành phố bằng cách xuất phát từ một vị trí bất kì trong các điểm nút . Hỏi quãng đường ngắn nhất để hành khách đi hết các con đường và trở về vị trí xuất phát là bao nhiêu ?
Mạng lưới giao thông ở một thành phố được mô phỏng như hình vẽ bên dưới, trong đó là các điểm nút giao thông, số ghi trên mỗi cạnh trong hình vẽ là khoảng cách giữa hai điểm đầu và cuối của con đường đó (đơn vị là ). Một khách du lịch muốn đi tham quan thành phố bằng cách xuất phát từ một vị trí bất kì trong các điểm nút . Hỏi quãng đường ngắn nhất để hành khách đi hết các con đường và trở về vị trí xuất phát là bao nhiêu ?

Đáp án chính thức: 40
Hướng dẫn giải chi tiết
Tổng chiều dài tất cả các con đường là . Đồ thị có đúng hai đỉnh bậc lẻ là và (bậc ), các đỉnh còn lại đều bậc chẵn. Để đi qua tất cả các cạnh và quay về điểm xuất phát, hành khách phải đi lặp lại một đường đi nối giữa và ; đường ngắn nhất giữa và là có độ dài . Vậy quãng đường ngắn nhất là .