Câu 38THPTChuyên đề: Đường đi và chu trình Euler • Lớp 11Đường đi ngắn nhất trên đồ thịVận dụng#secondary:M11.E03.GRAPH_THEORY.L3.SHORTEST#curriculum:undetermined
Một người đưa thư xuất phát từ bưu điện ở vị trí A, 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. Độ 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ể là bao nhiêu?
Một người đưa thư xuất phát từ bưu điện ở vị trí A, 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. Độ 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ể là 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)
Bài toán người đưa thư (Chinese Postman). Từ hình vẽ, các con đường: AB = 8, BC = 5, CD = 2, BD = 4, DE = 9, BE = 10, AE = 6 (đoạn thẳng) và AE = 7 (cung cong). Tổng độ dài tất cả các con đường: S = 8 + 5 + 2 + 4 + 9 + 10 + 6 + 7 = 51. Xét bậc các đỉnh: A bậc 3 (AB, AE = 6, AE = 7) — lẻ; B bậc 4 (AB, BC, BD, BE) — chẵn; C bậc 2 (BC, CD) — chẵn; D bậc 3 (BD, CD, DE) — lẻ; E bậc 4 (AE = 6, AE = 7, DE, BE) — chẵn. Vậy chỉ có A và D là đỉnh bậc lẻ, cần lặp lại đường đi ngắn nhất từ A đến D. Các phương án: A–B–D = 8 + 4 = 12; A–E–D = 6 + 9 = 15; A–B–E–D = 8 + 10 + 9 = 27. Ngắn nhất là 12. Tổng quãng đường ngắn nhất = 51 + 12 = 63, khớp đáp án chính thức (Câu 3, Mã đề 101: 63).
Bài toán người đưa thư (Chinese Postman). Từ hình vẽ, các con đường: AB = 8, BC = 5, CD = 2, BD = 4, DE = 9, BE = 10, AE = 6 (đoạn thẳng) và AE = 7 (cung cong). Tổng độ dài tất cả các con đường: S = 8 + 5 + 2 + 4 + 9 + 10 + 6 + 7 = 51. Xét bậc các đỉnh: A bậc 3 (AB, AE = 6, AE = 7) — lẻ; B bậc 4 (AB, BC, BD, BE) — chẵn; C bậc 2 (BC, CD) — chẵn; D bậc 3 (BD, CD, DE) — lẻ; E bậc 4 (AE = 6, AE = 7, DE, BE) — chẵn. Vậy chỉ có A và D là đỉnh bậc lẻ, cần lặp lại đường đi ngắn nhất từ A đến D. Các phương án: A–B–D = 8 + 4 = 12; A–E–D = 6 + 9 = 15; A–B–E–D = 8 + 10 + 9 = 27. Ngắn nhất là 12. Tổng quãng đường ngắn nhất = 51 + 12 = 63, khớp đáp án chính thức (Câu 3, Mã đề 101: 63).
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 đó.
