Câu 17THPT
Một người đưa thư xuất phát từ bưu điện ở vị trí , các điểm cần phát thư nằm dọc theo các con đường cần phải đi qua. Biết 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. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể bằng bao nhiêu?
Một người đưa thư xuất phát từ bưu điện ở vị trí , các điểm cần phát thư nằm dọc theo các con đường cần phải đi qua. Biết 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. Độ dài các con đường như hình vẽ (đơn vị độ dài). Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể bằng bao nhiêu?
Đáp án chính thức: 63
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Đây là bài toán người đưa thư (Chinese Postman). Tổng độ dài các con đường: , , , , , , , , tổng . Bậc các đỉnh: bậc 3, bậc 4, bậc 2, bậc 3, bậc 4. Vậy chỉ có và là đỉnh bậc lẻ, nên cần lặp lại một đường đi ngắn nhất từ đến . Các phương án: ; ; ; . Đường lặp ngắn nhất là với độ dài 12. Tổng quãng đường ngắn nhất .
Đây là bài toán người đưa thư (Chinese Postman). Tổng độ dài các con đường: , , , , , , , , tổng . Bậc các đỉnh: bậc 3, bậc 4, bậc 2, bậc 3, bậc 4. Vậy chỉ có và là đỉnh bậc lẻ, nên cần lặp lại một đường đi ngắn nhất từ đến . Các phương án: ; ; ; . Đường lặp ngắn nhất là với độ dài 12. Tổng quãng đường ngắn nhất .