Tổng chiều dài đường đi ngắn nhất mà kỹ sư cần di chuyển là bao nhiêu kilômét?
32/34
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 kilômét?
Đáp án: 24.
+) Đường đi ảo giữa hai đỉnh là đường đi ngắn nhất giữa hai đỉnh đó.
+) Ý tưởng giải bài toán là tạo ra tất cả các đỉnh bậc chẵn bằng cách thêm đường đi ảo. Khi đó sẽ có chu trình Euler (tức là đường đi từ 1 đỉnh qua tất cả các cạnh đúng 1 lần và trở về đỉnh ban đầu).
Áp dụng:
+) Trước tiên, ta thấy tổng độ dài tất các các con đường là: 3 + 1 + 5 + 3 + 4 + 2 + 2 = 20.
+) Vì đồ thị có đúng 4 đỉnh bậc lẻ A, B, C, E nên có 3 cách ghép cặp đỉnh để xây dựng đường đi ảo giữa các cặp đỉnh đó như sau:
Cách 1: A - B và C - E: Tổng độ dài đường đi ảo là: 3 + 5 = 8.
Cách ghép này cho ta chu trình Euler có độ dài 20 + 8 = 28.
Cách 2: A - C và B - E: Tổng độ dài đường đi ảo là: 2 + 2 = 4.
Cách ghép này cho ta chu trình Euler có độ dài 20 + 4 = 24.
Cách 3: A - E và B - C: Tổng độ dài đường đi ảo là: 5 + 1 = 6.
Cách ghép này cho ta chu trình Euler có độ dài 20 + 6 = 26.
Vậy đáp án của bài toán là 24 km.