Câu hỏi:
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. Hỏi người đó phải đi như thế nào để đường đi là ngắn nhất?
Đáp án đúng: 8300
Đồ thị trên chỉ có hai đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ A đến D (đường đi này đi qua mỗi cạnh đúng một lần).
Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là:
\(1000+900+700+200+800+1600+1500+300+400=7400\).
Để 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ừ D đến A theo thuật toán gắn nhãn vĩnh viễn.
Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là:
\(400+300+200=900\).
Vậy một chu trình cần tìm là AFEABEDBCDCBA và có độ dài là:
\(7400+900=8300\).
Câu hỏi này thuộc đề thi trắc nghiệm dưới đây, bấm vào Bắt đầu thi để làm toàn bài
Tuyển Tập Đề Thi Tham Khảo Tốt Nghiệp THPT Quốc Gia Năm 2025 – Môn Toán – Bộ Đề 01 do cụm trường tỉnh Đồng Nai biên soạn là tài liệu ôn luyện hữu ích dành cho học sinh lớp 12 đang chuẩn bị cho kỳ thi tốt nghiệp THPT. Đề thi được xây dựng bám sát theo cấu trúc và mức độ của đề minh họa do Bộ Giáo dục và Đào tạo công bố, bao gồm đầy đủ các dạng câu hỏi từ nhận biết, thông hiểu đến vận dụng và vận dụng cao. Tài liệu không chỉ giúp học sinh rèn luyện kỹ năng làm bài mà còn hỗ trợ giáo viên trong công tác giảng dạy và đánh giá năng lực học sinh một cách hiệu quả.
Câu hỏi liên quan

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Giáo Dục Kinh Tế Và Pháp Luật Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Lịch Sử Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Công Nghệ Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Hóa Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Sinh Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT
