Câu 1 Phần III · Thi thử 2025 · Sở Quảng Ninh
Đề bài
Câu 1 · Phần III · 0,5 điểmTại một khu trung tâm dữ liệu, kỹ sư IT cần kiểm tra kết nối giữa các máy chủ trong hệ thống gồm các trạm A, B, C, D, E. Các tuyến cáp quang nối giữa các trạm được biểu diễn trong sơ đồ sau, với con số ghi trên mỗi tuyến là chiều dài dây cáp (đơn vị: km). Kỹ sư cần thực hiện một hành trình bắt đầu từ một trạm bất kỳ, đi qua tất cả các tuyến cáp ít nhất một lần và kết thúc tại đúng trạm khởi hành, nhằm đảm bảo toàn bộ hệ thống được kiểm tra. Tổng chiều dài đường đi ngắn nhất mà kỹ sư cần di chuyển là bao nhiêu km?
Tự làm câu này trước
Tại một khu trung tâm dữ liệu, kỹ sư IT cần kiểm tra kết nối giữa các máy chủ trong hệ thống gồm các trạm A, B, C, D, E. Các tuyến cáp quang nối giữa các trạm được biểu diễn trong sơ đồ sau, với con số ghi trên mỗi tuyến là chiều dài dây cáp (đơn vị: km). Kỹ sư cần thực hiện một hành trình bắt đầu từ một trạm bất kỳ, đi qua tất cả các tuyến cáp ít nhất một lần và kết thúc tại đúng trạm khởi hành, nhằm đảm bảo toàn bộ hệ thống được kiểm tra. Tổng chiều dài đường đi ngắn nhất mà kỹ sư cần di chuyển là bao nhiêu km?
Hướng dẫn giải
Hướng đi của dạng
- Vẽ đồ thị với các đỉnh và cạnh có trọng số.
- Liệt kê các đường đi có thể, hoặc dùng thuật toán tìm đường đi ngắn nhất.
- So tổng trọng số để chọn đường tốt nhất.
Lời giải tóm tắt
- Tổng 20; bốn đỉnh bậc lẻ A, B, C, E; ghép cặp rẻ nhất AC + BE = 4. Đáp số 24.
Đáp án: 24khớp đáp án của Sở