Câu 2. Một người đưa thư xuất phát từ bưu điện (vị trí C), các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng 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. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo km) được biểu diễn ở hình vẽ bên. Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu km?

Câu 2. Một người đưa thư xuất phát từ bưu điện (vị trí C), các điểm cần phát thư nằm dọc các con đường cần đi qua. Biết rằng 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. Sơ đồ các con đường cần đi qua và độ dài của chúng (tính theo km) được biểu diễn ở hình vẽ bên. Hỏi tổng quãng đường người đưa thư có thể đi ngắn nhất có thể là bao nhiêu km?


Phương pháp & hướng dẫn giải
Phương pháp & hướng dẫn giải: Bài toán người đưa thư (Chinese Postman) trên đồ thị với các cạnh AB=1, AC=2, BC=4, BD=3, BE=5, DE=6, CE=10. Tổng độ dài tất cả các cạnh: 1+2+4+3+5+6+10 = 31 km. Bậc các... Xem đáp án chính thức và trọn bộ lời giải chi tiết từng bước câu hỏi thuộc Đề Thi Tham Khảo Tốt Nghiệp THPT Toán 2024-2025 Sở GD&ĐT Đồng Nai THPT Chuyên Lương Thế Vinh - Đề Số 1 trên dethichuan.com.



Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.