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).

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? (ảnh 1) 

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:

verified
Giải bởi Vietjack

Đá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.

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}\].

Câu 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.

Câu 3

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.

Nâng cấp VIP

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.

Nâng cấp VIP