Câu 30HSG#tax:v1#topic:M11.E03.GRAPH_THEORY
Thuộc đề: Đề Khảo Sát Học Sinh Giỏi Lớp 12 Sở GD&ĐT Ninh Bình Cụm THPT Số 11Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các con đường để phát thư rồi quay lại bưu điện. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo mét) được biểu diễn ở hình vẽ dưới. Độ dài đường đi ngắn nhất của người đó là bao nhiêu mét?
Một người đưa thư xuất phát từ bưu điện (vị trí A) và phải đi qua các con đường để phát thư rồi quay lại bưu điện. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo mét) được biểu diễn ở hình vẽ dưới. Độ dài đường đi ngắn nhất của người đó là bao nhiêu mét?
Đáp án chính thức: 7700
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Tổng độ dài các cạnh: , tổng m. Bậc các đỉnh: , , , , , . Chỉ có hai đỉnh bậc lẻ là và , nên theo bài toán người đưa thư (Chinese Postman) phải lặp lại đường đi ngắn nhất từ đến . Các phương án: ; ; ; ; . Ngắn nhất là m. Đáp số: m.
Tổng độ dài các cạnh: , tổng m. Bậc các đỉnh: , , , , , . Chỉ có hai đỉnh bậc lẻ là và , nên theo bài toán người đưa thư (Chinese Postman) phải lặp lại đường đi ngắn nhất từ đến . Các phương án: ; ; ; ; . Ngắn nhất là m. Đáp số: m.