Câu 1HSG
Thuộc đề: Đề Khảo Sát Học Sinh Giỏi Liên Trường Môn Toán 12 Sở GD&ĐT Ninh Bình 2025-2026 - Đề Số 2Mộ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: B
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Đây là bài toán tìm chu trình Hamilton ngắn nhất trên đồ thị với các cạnh: , , , , , . Xét các chu trình xuất phát từ (do tính đối xứng, chỉ cần 3 chu trình):
- : .
- : .
- : .
Vậy quãng đường ngắn nhất là mét (chu trình hoặc chiều ngược lại).
Đây là bài toán tìm chu trình Hamilton ngắn nhất trên đồ thị với các cạnh: , , , , , . Xét các chu trình xuất phát từ (do tính đối xứng, chỉ cần 3 chu trình):
- : .
- : .
- : .
Vậy quãng đường ngắn nhất là mét (chu trình hoặc chiều ngược lại).