Để giải bài toán này, chúng ta cần tìm một chu trình Hamilton (đi qua mỗi nhà đúng một lần và quay lại điểm xuất phát) có tổng thời gian ngắn nhất. Các bước thực hiện: Liệt kê tất cả các chu trình có thể (do có 4 điểm, số chu trình là 3! = 6). Tính tổng thời gian của từng chu trình. Chọn chu trình có tổng thời gian ngắn nhất. Danh sách các chu trình: Ký hiệu: Hạnh (H), Đô (Đ), Hà (Ha), Ngọc (N). H → Đ → Ha → N → H H-Đ: 6 phút Đ-Ha: 4 phút Ha-N: 10 phút N-H: 14 phút Tổng: 6 + 4 + 10 + 14 = 34 phút H → Đ → N → Ha → H H-Đ: 6 phút Đ-N: 8 phút N-Ha: 10 phút Ha-H: 6 phút Tổng: 6 + 8 + 10 + 6 = 30 phút H → Ha → Đ → N → H H-Ha: 6 phút Ha-Đ: 4 phút Đ-N: 8 phút N-H: 14 phút Tổng: 6 + 4 + 8 + 14 = 32 phút H → Ha → N → Đ → H H-Ha: 6 phút Ha-N: 10 phút N-Đ: 8 phút Đ-H: 6 phút Tổng: 6 + 10 + 8 + 6 = 30 phút H → N → Đ → Ha → H H-N: 14 phút N-Đ: 8 phút Đ-Ha: 4 phút Ha-H: 6 phút Tổng: 14 + 8 + 4 + 6 = 32 phút H → N → Ha → Đ → H H-N: 14 phút N-Ha: 10 phút Ha-Đ: 4 phút Đ-H: 6 phút Tổng: 14 + 10 + 4 + 6 = 34 phút Kết quả: Các chu trình có tổng thời gian ngắn nhất là 30 phút: H → Đ → N → Ha → H (6 + 8 + 10 + 6 = 30 phút) H → Ha → N → Đ → H (6 + 10 + 8 + 6 = 30 phút) Chọn một trong hai chu trình: Chu trình 1: Xuất phát từ nhà Hạnh → Đô → Ngọc → Hà → Hạnh. Thời gian: 30 phút. Kết luận: Đường đi phù hợp nhất là: Nhà Hạnh → Nhà Đô → Nhà Ngọc → Nhà Hà → Nhà Hạnh với tổng thời gian 30 phút.