Một trò chơi điện tử quy định như sau: Có sáu trụ với số lượng các thứ thạch trên đường đi giữa các cặp trụ được mô tả như trong hình vẽ. Người chơi xuất phát từ một trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thứ thạch của đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất bằng bao nhiêu?
Một trò chơi điện tử quy định như sau: Có sáu trụ với số lượng các thứ thạch trên đường đi giữa các cặp trụ được mô tả như trong hình vẽ. Người chơi xuất phát từ một trụ nào đó, đi qua tất cả các trụ còn lại, mỗi khi đi qua một trụ thì trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa, nhưng người chơi vẫn phải trở về trụ ban đầu. Tổng số thứ thạch của đường đi thỏa mãn điều kiện trên nhận giá trị nhỏ nhất bằng bao nhiêu?
Đáp án chính thức: 34
Hướng dẫn giải chi tiết
(AI giải đề cho tôi)
Đồ thị có các cạnh: AB=4, BC=5, BD=6, AD=7, CD=7, CF=8, CE=9, DF=3, AE=5, FE=10. Cần tìm chu trình Hamilton nhỏ. Các chu trình khả dĩ: A-B-C-D-F-E-A: 4+5+7+3+10+5=34; A-B-C-E-F-D-A: 4+5+9+10+3+7=38; A-E-C-F-D-B-A: 5+9+8+3+6+4=35; A-D-F-E-C-B-A: 7+3+10+9+5+4=38; A-D-B-C-F-E-A: 7+6+5+8+10+5=41; A-E-F-C-D-B-A: 5+10+8+7+6+4=40. Kiểm tra các chu trình khác đều cho giá trị ≥34 (ví dụ phải dùng cạnh DF=3 và tránh FE=10 nếu có thể, nhưng cấu trúc đồ thị buộc hoặc dùng FE hoặc dùng hai cạnh lớn khác). Chu trình nhỏ nhất là A-B-C-D-F-E-A với tổng 34.
Đồ thị có các cạnh: AB=4, BC=5, BD=6, AD=7, CD=7, CF=8, CE=9, DF=3, AE=5, FE=10. Cần tìm chu trình Hamilton nhỏ. Các chu trình khả dĩ: A-B-C-D-F-E-A: 4+5+7+3+10+5=34; A-B-C-E-F-D-A: 4+5+9+10+3+7=38; A-E-C-F-D-B-A: 5+9+8+3+6+4=35; A-D-F-E-C-B-A: 7+3+10+9+5+4=38; A-D-B-C-F-E-A: 7+6+5+8+10+5=41; A-E-F-C-D-B-A: 5+10+8+7+6+4=40. Kiểm tra các chu trình khác đều cho giá trị ≥34 (ví dụ phải dùng cạnh DF=3 và tránh FE=10 nếu có thể, nhưng cấu trúc đồ thị buộc hoặc dùng FE hoặc dùng hai cạnh lớn khác). Chu trình nhỏ nhất là A-B-C-D-F-E-A với tổng 34.