(THPT Phúc Thọ - Hà Nội 2025) Một người đưa thư xuất phát từ vị trí $ A $, các điểm cần phát thư nằm dọc con đường cần phải đi qua. Biết rằng người này phải đi trên mỗi con đường ít nhất một lần (để phát được thư cho tất cả các điểm cần phải nằm dọc theo con đường đó) và cuối cùng quay lại điểm xuất phát. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu?

Question

Beedemy · Accepted Answer

Lời giải: Đáp án: 41 Vì đồ thị có đúng hai đỉnh bậc lẻ là $ A $ và $ D $ nên đồ thị có đường đi Euler đi từ đỉnh $ A $ đến đỉnh $ D $. Một đường đi Euler từ $ A $ đến $ D $ là $ AEABEDBCD $ và có độ dài bằng $ 6+8+1+7+5+4+2+3=36 $. Đường đi ngắn nhất từ $ D $ đến $ A $ có độ dài bằng $ 4+1=5 $. Tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là $ 36+5=41 $.

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 3