(Sở Quảng Ninh 2025) 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?

Question

Beedemy · Accepted Answer

Lời giải: Đáp án: 24 Tổng quãng đường đi qua tất cả các cạnh là $ 3+2+4+3+2+5+1=20 $. Để có chu trình ơle thì ta phải có số đỉnh bậc lẻ bằng 0 hoặc chỉ có hai đỉnh bậc lẻ. Ta có 4 đỉnh bậc lẻ là $ A,B,C,E $. Tìm cặp ghép giữa các đỉnh bậc lẻ sao cho tổng quãng đường ngắn nhất Các cặp có thể ghép là A-B: 3 A-C:2 B-C:1 B-E:2 C-E:5 A-D:4 E-D:3 Ta cần ghép hai cặp sao cho không cùng đỉnh và tổng đường đi bé nhất. Vậy ta ghép $ A-C $ và $ B-E $ thì tổng đường đi là 4 Vậy tổng chiều dài ngắn nhất là 24 và đi theo chu trình $ A-B-C-A-D-E-B-E-C-A $.

Bài tự luận Một số bài toán thuộc chuyên đề Toán học 10–11–12 · Bài 18