Một người đưa thư xuất phát từ điểm $A$ phải đi qua mỗi con đường (cạnh) của sơ đồ ít nhất một lần rồi quay về $A$. Sơ đồ gồm các điểm $A$, $B$, $C$, $D$ và các con đường có độ dài (đơn vị: km): $AB = 2$, $BC = 3$, $AC = 4$, $CD = 5$. Tính độ dài ngắn nhất của hành trình.
ĐÁP ÁN
1
9
LỜI GIẢI
Bước 1 — Tính bậc của từng đỉnh.
Đếm số con đường nối vào mỗi đỉnh, ta thấy đúng hai đỉnh bậc lẻ là $C$ và $D$ (các đỉnh còn lại bậc chẵn).
Bước 2 — Vì có đỉnh bậc lẻ nên phải đi lặp.
Không tồn tại chu trình Euler. Để hành trình ngắn nhất, ta đi lặp lại các cạnh trên đường đi ngắn nhất giữa hai đỉnh bậc lẻ $C$ và $D$.
Bước 3 — Tìm đường đi ngắn nhất giữa hai đỉnh bậc lẻ.
Đường ngắn nhất từ $C$ đến $D$ là $C \to D$ có độ dài $d(C,D) = 5$ km.
Bước 4 — Cộng tổng.
Tổng độ dài các con đường là $W = 14$ km. Độ dài ngắn nhất $= W + d(C,D) = 14 + 5 = 19$ km.
Kết luận: độ dài ngắn nhất là $19$ km. Đáp số: $19$.
66% trả lời đúng
479 đúng · 243 sai