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

Câu hỏi số 774093:

Thông hiểu

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?

Trả lời:

Đáp án đúng là:

Quảng cáo

Xem lời giải

Câu hỏi:774093

Phương pháp giải

Tính tổng quãng đường đi.

Giải chi tiết

Đồ thị trên chỉ có hai đỉnh bậc lẻ là C và E nên ta có thể tìm được một đường đi Euler từ C đến E (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler từ C đến E là CABDEBCE và tổng độ dài của nó là

$2 + 1 + 3 + 6 + 5 + 4 + 10 = 31$ (km).

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến C.

Đường đi ngắn nhất từ E đến C là EBAC và có độ dài là $5 + 1 + 2 = 8(~\text{km})$.

Vậy tổng quãng đường đưa thư có thể đi ngắn nhất là $31 + 8 = 39(~\text{km})$.

Đáp án cần điền là: 39

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.