Giải Luyện tập 2 trang 44 Chuyên đề Toán 11
Đề bài
Đồ thị nào trong Hình 2.23 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamilton của nó.
Hình 2.23 gồm hai đồ thị:
a) 5 đỉnh A, B ở hàng trên; E, D, C ở hàng dưới. Các cạnh: A–E, A–D, A–C (A nối tới E, D, C tạo hình chữ V), B–E, B–D, B–C (B nối tới E, D, C). Tức A và B đều nối tới cả E, D, C, tạo các đường chéo cắt nhau; các cạnh thực tế: A–E, A–C, B–E, B–D... (đồ thị hai nhánh tam giác đan chéo).
b) 4 đỉnh: A ở đỉnh trên, D ở giữa, C ở dưới trái, B ở dưới phải. Các cạnh: A–C, A–B, A–D, C–D, D–B, C–B. (A, C, B tạo tam giác ngoài, D ở trong nối với cả A, C, B).
Lời giải
Nhắc lại khái niệm. Một *đường đi Hamilton* của đồ thị là đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần.
### a) Đồ thị thứ nhất (5 đỉnh )
Theo hình, các cạnh là:
Như vậy hai đỉnh đều nối với cả ba đỉnh , còn giữa và cũng như giữa các đỉnh không có cạnh nào (đồ thị hai phần với hai lớp và ).
Ta thử đi lần lượt, xen kẽ một đỉnh ở lớp rồi một đỉnh ở lớp :
Kiểm tra các cạnh: (có), (có), (có), (có). Đường đi này qua đủ cả 5 đỉnh, mỗi đỉnh đúng một lần.
➡️ Đồ thị a) có đường đi Hamilton, chẳng hạn .
*(Nhận xét thêm: đồ thị a) không có chu trình Hamilton, vì đây là đồ thị hai phần với hai lớp có số đỉnh khác nhau — nhưng ở đây chỉ yêu cầu đường đi.)*
###
b) Đồ thị thứ hai (4 đỉnh )
Theo hình, các cạnh là:
Đây là đồ thị đầy đủ đỉnh (mọi cặp đỉnh đều có cạnh nối), nên chắc chắn có đường đi Hamilton.
Chọn thứ tự:
Kiểm tra các cạnh: (có), (có), (có). Đường đi này qua đủ cả 4 đỉnh, mỗi đỉnh đúng một lần.
➡️ Đồ thị
b) có đường đi Hamilton, chẳng hạn .
### Kết luận
Cả hai đồ thị trong Hình 2.23 đều có đường đi Hamilton.
Đá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.