Cho bản đồ như hình trên, mỗi đỉnh là một thành phố, cạnh nối hai đỉnh là đường đi nối hai thành phố tương ứng. Hè này, bố mẹ cho bạn An đi tham quan. An đã cho điểm mỗi thành phố (điểm số chỉ mức độ ưa thích của An), được ghi như trên bản đồ.
Bạn hãy chỉ cho An và gia đình tour du lịch đi qua 5 thành phố liên tiếp nhau sao cho tổng số điểm là lớn nhất.
Đáp án: Phương án tối ưu là An và gia đình chọn lộ trình đi các thành phố được đánh số sau: 9, 6, 8, 9. 7 (tổng bằng 39).
Nguồn: Olm.vn
