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. Hỏi người đó phải đi như thế nào để đường đi là ngắn nhất?

Question

Beedemy · Accepted Answer

Lời giải: Đồ thị trên chỉ có hai đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ A đến D (đường đi này đi qua mỗi cạnh đúng một lần). Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là 1000 + 900 + 700 + 200 + 800 + 1600 + 1500 + 300 + 400 = 7400. Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ D đến A theo thuật toán gắn nhãn vĩnh viễn. Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 400 + 300 + 200 = 900. Vậy một chu trình cần tìm là AFEABEDBCDCBA và có độ dài là 7400 + 900 = 8300. Đáp án: 8300

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 28