Giải Hoạt động 2 trang 43 Chuyên đề Toán 11
Đề bài
Nhận biết đường đi Hamilton
Có 5 thành phố du lịch , , , , và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần.
Hình 2.20: Đồ thị gồm 5 đỉnh (thành phố) A, B, C, D, E. A ở trên bên trái, B ở trên bên phải, D ở bên trái, E ở giữa, C ở dưới bên phải. Các cạnh (con đường) nối: A–B, A–D, A–C (đường chéo đi từ A xuống C, đi qua vùng gần E), D–E, E–C, B–C. Đỉnh E nằm trên đường nối D và C.
Lời giải
Ta liệt kê các con đường (cạnh) nối giữa các thành phố theo Hình 2.20:
- nối với: , ,
- nối với: ,
- nối với: , ,
- nối với: ,
- nối với: ,
Yêu cầu "đi tham quan cả 5 thành phố mà không đến địa điểm nào quá một lần" chính là tìm một đường đi Hamilton (đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần).
Ta xuất phát từ . Vì chỉ nối với và , ta thử đi . Từ còn các đường tới , ; chọn . Từ chỉ còn đường tới , nên . Từ còn đường tới , nên . Đến đây đã qua đủ cả 5 thành phố.
Kiểm tra lại lộ trình :
- : có đường ✓
- : có đường ✓
- : có đường ✓
- : có đường ✓
Lộ trình đi qua cả 5 thành phố , , , , , mỗi thành phố đúng một lần. Vậy đây là một cách đi thỏa mãn yêu cầu (một đường đi Hamilton của đồ thị).
Đáp số
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.