Có năm địa điểm A, B, C, D, E được nối với nhau theo những con đường với độ dài (đơn vị là kilômét) được mô tả bằng đồ thị có trọng số ở hình vẽ dưới đây. Một người giao hàng đi giao hàng bắt đầu xuất phát từ địa điểm A đến các địa điểm còn lại và phải đi qua tất cả các con đường sau đó quay trở về địa điểm A. Hỏi người đó phải đi quãng đường ngắn nhất là bao nhiêu kilômét?

(AI giải đề cho tôi)
Đây là bài toán người đưa thư Trung Hoa (Chinese Postman). Từ hình vẽ trang 6, đồ thị có các cạnh: $AB=1$, $BC=2$, $CD=3$, $BD=4$, $ED=5$, $AE=6$ (cạnh thẳng đứng), $BE=7$ (đường chéo), và cạnh cong ngoài $AE=8$. Tổng trọng số các cạnh: $1+2+3+4+5+6+7+8=36$ km. Xét bậc các đỉnh: $A$ bậc 3 (các cạnh $AB$, $AE=6$, cạnh cong $AE=8$) — lẻ; $B$ bậc 4 — chẵn; $C$ bậc 2 — chẵn; $D$ bậc 3 (các cạnh $BD$, $CD$, $ED$) — lẻ; $E$ bậc 4 — chẵn. Vậy chỉ có hai đỉnh bậc lẻ là $A$ và $D$, nên cần lặp lại con đường ngắn nhất nối $A$ với $D$. Đường đi ngắn nhất từ $A$ đến $D$: $A\to B\to D$ có độ dài $1+4=5$ (so sánh: $A\to E\to D=6+5=11$; $A\to B\to E\to D=1+7+5=13$). Quãng đường ngắn nhất $=36+5=41$ km. Hành trình cụ thể đạt 41 km: đi cạnh $A\to B\to D$ (lặp lại một lần) và mỗi cạnh còn lại đúng một lần, ví dụ $A\to B\to C\to D\to B\to E\to D\to E\to A(6)\to A(8)\to B\to A$... tổng bằng $36+5=41$. Kết quả khớp với đáp án nguồn: 41.