Câu hỏi:
23/05/2025 709
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?
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?
Quảng cáo
Trả lời:
Đá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.
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
- 250+ Công thức giải nhanh môn Toán 12 (chương trình mới) ( 18.000₫ )
- 20 Bộ đề, Tổng ôn, sổ tay môn Toán (có đáp án chi tiết) ( 55.000₫ )
- Bộ đề thi tốt nghiệp 2025 các môn Toán, Lí, Hóa, Văn, Anh, Sinh, Sử, Địa, KTPL (có đáp án chi tiết) ( 36.000₫ )
- Tổng ôn lớp 12 môn Toán, Lí, Hóa, Văn, Anh, Sinh Sử, Địa, KTPL (Form 2025) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
a) Đúng. Vì người chơi chọn ngẫu nhiên một trong hai đồng xu (một cân bằng và một thiên lệch), nên xác suất chọn được đồng xu cân bằng là \[P\left( A \right) = \frac{1}{2}\].
Lời giải
Hàm số \(y = {3^{ - x}} \Leftrightarrow y = {\left( {\frac{1}{3}} \right)^x}\) là hàm số mũ, cơ số \(a = \frac{1}{3}\) với \(0 < a < 1\) nên nghịch biến trên \(\mathbb{R}\). Chọn B.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.