Câu 2. Một người đưa thư xuất phát từ bưu điện (vị trí C), các điểm cần phát thư nằm dọc các con đường cần đ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. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo km) được biểu diễn ở hình vẽ bên. Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu km?

(AI giải đề cho tôi)
Bài toán người đưa thư (Chinese Postman) trên đồ thị với các cạnh AB=1, AC=2, BC=4, BD=3, BE=5, DE=6, CE=10. Tổng độ dài tất cả các cạnh: 1+2+4+3+5+6+10 = 31 km. Bậc các đỉnh: deg(A)=2, deg(D)=2 (chẵn); deg(B)=3 (kề A, D, E), deg(C)=3 (kề A, B, E), deg(E)=3 (kề B, D, C) — ba đỉnh lẻ, không thể vì số đỉnh bậc lẻ phải chẵn. Kiểm tra lại: E kề B(5), D(6), C(10) → deg(E)=3; B kề A(1), C(4), D(3), E(5) → deg(B)=4; C kề A(2), B(4), E(10) → deg(C)=3. Vậy đỉnh lẻ là C và E. Cần lặp lại đường đi ngắn nhất giữa C và E: trực tiếp CE = 10, hoặc C–B–E = 4+5 = 9, hoặc C–A–B–E = 2+1+5 = 8. Đường ngắn nhất là 8 km. Tổng quãng đường ngắn nhất = 31 + 8 = 39 km.