Câu hỏi:
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?
Trả lời:
Đáp án đúng:
Bài toán yêu cầu tìm chu trình Euler có độ dài nhỏ nhất.
Đầu tiên, ta tính tổng độ dài các cạnh của đồ thị: $5+3+4+2+3+4+2 = 23$ km.
Tiếp theo, ta xét các đỉnh bậc lẻ: A(3), C(3), D(3), E(3).
Để tạo thành chu trình Euler, ta cần tăng thêm các cạnh sao cho tất cả các đỉnh đều có bậc chẵn. Ta cần tìm cách nối các đỉnh bậc lẻ này sao cho tổng độ dài các cạnh thêm vào là nhỏ nhất.
Có 3 cách ghép cặp các đỉnh bậc lẻ:
- AC và DE: AC = 3, DE = 2. Tổng = 3 + 2 = 5
- AD và CE: AD = 5+3 = 8, CE = 4+2 = 6. Tổng = 8 + 6 = 14
- AE và CD: AE = 5+4 = 9, CD = 4. Tổng = 9 + 4 = 13
Câu hỏi này thuộc đề thi trắc nghiệm dưới đây, bấm vào Bắt đầu thi để làm toàn bài
Câu hỏi liên quan

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Giáo Dục Kinh Tế Và Pháp Luật Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Lịch Sử Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Công Nghệ Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Hóa Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT

Bộ 50 Đề Thi Thử Tốt Nghiệp THPT Môn Sinh Học Năm 2026 – Theo Cấu Trúc Đề Minh Họa Bộ GD&ĐT
