Một công ty du lịch thiết kế tour đi bộ khám phá khu phố cổ gồm 5 địa điểm tham quan chính , , , , . Sơ đồ các tuyến đường hai chiều và chiều dài của chúng (đơn vị: kilômét) được cho như hình vẽ.
Hướng dẫn viên dẫn đoàn xuất phát từ địa điểm , cần đi qua tất cả các tuyến đường được thể hiện trên sơ đồ ít nhất một lần để giới thiệu trọn vẹn vẻ đẹp của phố cổ, và cuối cùng quay về lại địa điểm . Tổng quãng đường đi ngắn nhất là bao nhiêu? (đơn vị: kilômét).
Một công ty du lịch thiết kế tour đi bộ khám phá khu phố cổ gồm 5 địa điểm tham quan chính , , , , . Sơ đồ các tuyến đường hai chiều và chiều dài của chúng (đơn vị: kilômét) được cho như hình vẽ.
Hướng dẫn viên dẫn đoàn xuất phát từ địa điểm , cần đi qua tất cả các tuyến đường được thể hiện trên sơ đồ ít nhất một lần để giới thiệu trọn vẹn vẻ đẹp của phố cổ, và cuối cùng quay về lại địa điểm . Tổng quãng đường đi ngắn nhất là bao nhiêu? (đơn vị: kilômét).
Hướng dẫn viên dẫn đoàn xuất phát từ địa điểm , cần đi qua tất cả các tuyến đường được thể hiện trên sơ đồ ít nhất một lần để giới thiệu trọn vẹn vẻ đẹp của phố cổ, và cuối cùng quay về lại địa điểm . Tổng quãng đường đi ngắn nhất là bao nhiêu? (đơn vị: kilômét).Đáp án chính thức: 4,2
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ư Trung Hoa (Euler circuit với đỉnh xuất phát = đỉnh kết thúc). Các cạnh: , , , , , , tổng độ dài tất cả các cạnh km. Bậc các đỉnh: bậc 3 (AB, AE, AD), bậc 3 (EC, BC, DC), còn đều bậc 2. Vậy đồ thị có đúng hai đỉnh bậc lẻ là và , nên cần lặp lại đường đi ngắn nhất từ đến . Các khả năng: ; ; . Chọn đường lặp ngắn nhất km. Tổng quãng đường ngắn nhất km, khớp với đáp án nguồn.
Đây là bài toán người đưa thư Trung Hoa (Euler circuit với đỉnh xuất phát = đỉnh kết thúc). Các cạnh: , , , , , , tổng độ dài tất cả các cạnh km. Bậc các đỉnh: bậc 3 (AB, AE, AD), bậc 3 (EC, BC, DC), còn đều bậc 2. Vậy đồ thị có đúng hai đỉnh bậc lẻ là và , nên cần lặp lại đường đi ngắn nhất từ đến . Các khả năng: ; ; . Chọn đường lặp ngắn nhất km. Tổng quãng đường ngắn nhất km, khớp với đáp án nguồn.