Câu 9HSG
Thuộc đề: Đề Khảo Sát Học Sinh Giỏi Liên Trường Toán 12 Sở GD&ĐT Ninh Bình 2025-2026 - Đề Số 1Một anh phục vụ bàn đang phục vụ trong một khu vực có 4 bàn đặt tại với khoảng cách (được tính theo đơn vị mét) được ghi như các trọng số của các cạnh trong hình bên. Anh nhân viên này xuất phát từ một bàn và phải đi qua tất cả các bàn và phải quay về vị trí ban đầu, mỗi bàn chỉ được đi qua một lần (trừ lần trở về bàn ban đầu). Hỏi quãng đường ngắn nhất để anh nhân viên thực hiện được công việc là bao nhiêu mét?
Một anh phục vụ bàn đang phục vụ trong một khu vực có 4 bàn đặt tại với khoảng cách (được tính theo đơn vị mét) được ghi như các trọng số của các cạnh trong hình bên. Anh nhân viên này xuất phát từ một bàn và phải đi qua tất cả các bàn và phải quay về vị trí ban đầu, mỗi bàn chỉ được đi qua một lần (trừ lần trở về bàn ban đầu). Hỏi quãng đường ngắn nhất để anh nhân viên thực hiện được công việc là bao nhiêu mét?
Chọn một phương án bên dưới để kiểm tra đáp án ngay:
Đáp án chính thức: D
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Đây là bài toán chu trình Hamilton (người bán hàng). Các cạnh: . Xét các chu trình qua 4 đỉnh xuất phát từ :
- :
- :
- :
- :
- :
- :
Quãng đường ngắn nhất là mét (chu trình hoặc ). Vậy chọn đáp án D.
Đây là bài toán chu trình Hamilton (người bán hàng). Các cạnh: . Xét các chu trình qua 4 đỉnh xuất phát từ :
- :
- :
- :
- :
- :
- :
Quãng đường ngắn nhất là mét (chu trình hoặc ). Vậy chọn đáp án D.