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 đ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át 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?
Đáp án:
Đáp án:
Sử dụng định lí về đường đi Euler.
Theo sơ đồ đường đi thấy có 2 đỉnh bậc lẻ là A và D nên có thể tìm được một đường đi Euler từ A đến D (đường này đi qua mỗi cạnh đúng một lần).
Một đường Euler từ A đến D là: AEABEDBCD và độ dài của nó là:
6 + 7 + 8 + 10 + 9 + 4 + 5 + 2 = 51.
Đường đi ngắn nhất từ D đến A là DBA và có độ dài là: 4 + 8 = 12.
Vậy tổng quãng đường đưa thư có thể đi ngắn nhất là 51 + 12 = 63.
