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 20
(Sở Tuyên Quang 2025) Một người đưa thư xuất phát từ bưu điện (vị trí $ A $) và phải đi qua các con đường để phát thư rồi quay lại bưu điện. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo mét) được biểu diễn ở hình vẽ dưới. Khi đó, quãng đường ngắn nhất người đưa thư có thể lựa chọn đi là bao nhiêu mét?
Xem lời giải
Lời giải
Đáp án: $ 8700 $.
Vì đồ thị có đúng hai đỉnh bậc lẻ là $ A $ và $ D $ nên có một đường đi Euler từ $ A $ đến $ D $. Tổng độ dài đường đi là $ 200+300+400+1500+900+1700+800+700+1000=7500\,(m) $
Bây giờ ta tìm một đường đi ngắn nhất từ $ D $ về $ A $, đường đi này là $ DCBA $ có độ dài là $ 400+300+200=1200\,(m) $. Vậy quãng đường ngắn nhất người đưa thư có thể đi là $ 7500+1200=8700\,(m) $
