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$, $E$ và các con đường có độ dài (đơn vị: km): $AB = 4$, $BC = 3$, $CD = 5$, $DA = 6$, $AE = 2$, $BE = 3$. Trong hành trình ngắn nhất, tổng độ dài những con đường phải đi lặp lại (đi quá một lần) là bao nhiêu km?
ĐÁP ÁN
4
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à $A$ và $B$.
Bước 2 — Các cạnh đi lặp nằm trên đường nối hai đỉnh bậc lẻ.
Để chuyển hai đỉnh bậc lẻ thành bậc chẵn (điều kiện đi qua mỗi cạnh rồi về chỗ cũ), ta phải đi lặp các cạnh dọc đường đi ngắn nhất giữa $A$ và $B$.
Bước 3 — Tìm đường đi ngắn nhất.
Đường ngắn nhất từ $A$ đến $B$ là $A \to B$, có tổng độ dài $4$ km. Đây chính là tổng độ dài phải đi lặp lại.
Kết luận: tổng quãng đường đi lặp là $4$ km. Đáp số: $4$.
67% trả lời đúng
116 đúng · 57 sai