Câu 17THPT#toan-12#toan-roi-rac
Thuộc đề: Đề thi thử tốt nghiệp THPT năm 2025 môn Toán Sở GD&ĐT Sóc Trăng (Mã đề 1011)Cho bảy điểm có là hình chữ nhật, là trung điểm , độ dài các cạnh được ghi trên hình vẽ (đơn vị độ dài).
Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
Cho bảy điểm có là hình chữ nhật, là trung điểm , độ dài các cạnh được ghi trên hình vẽ (đơn vị độ dài).
Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
Một trò chơi được quy định như sau: xuất phát từ một điểm bất kỳ trong bảy điểm trên đi qua hết tất cả các cạnh trên hình vẽ mỗi cạnh ít nhất một lần rồi quay lại điểm xuất phát. Người chơi là người thắng cuộc nếu tổng độ dài đường đi là ngắn nhất. Tính tổng độ dài đường đi đó.
Đáp án chính thức: 106
Hướng dẫn giải chi tiết
Đây là bài toán tìm chu trình ngắn nhất đi qua tất cả các cạnh của đồ thị (bài toán người đưa thư Trung Hoa). Tổng độ dài tất cả các cạnh ban đầu cộng với độ dài các cạnh cần đi lặp lại tối thiểu giữa các đỉnh bậc lẻ cho kết quả bằng .