Chuyên đề học tập Toán 11

Giải Hoạt động 2 trang 43 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm chéo

Đề bài

Nhận biết đường đi Hamilton
Có 5 thành phố du lịch AA, BB, CC, DD, EE 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.

Bài có hình vẽ / bảng trong sách — xem ở trang 43 · mở sách.
Hình trong bài (mô tả bằng lời):

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:

- AA nối với: BB, DD, CC
- BB nối với: AA, CC
- CC nối với: AA, EE, BB
- DD nối với: AA, EE
- EE nối với: DD, CC

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ừ BB. Vì BB chỉ nối với AA và CC, ta thử đi B→AB \to A. Từ AA còn các đường tới DD, CC; chọn A→DA \to D. Từ DD chỉ còn đường tới EE, nên D→ED \to E. Từ EE còn đường tới CC, nên E→CE \to C. Đến đây đã qua đủ cả 5 thành phố.

Kiểm tra lại lộ trình B→A→D→E→CB \to A \to D \to E \to C:

- B→AB \to A: có đường A–BA\text{–}B ✓
- A→DA \to D: có đường A–DA\text{–}D ✓
- D→ED \to E: có đường D–ED\text{–}E ✓
- E→CE \to C: có đường E–CE\text{–}C ✓

Lộ trình đi qua cả 5 thành phố AA, BB, CC, DD, EE, 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ố

Một cách đi: B→A→D→E→CB \to A \to D \to E \to C (đi qua cả 5 thành phố, mỗi nơi đúng một lần)

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.