Giải Bài 2.10 trang 44 Chuyên đề Toán 11
Đề bài
Cho đồ thị như Hình 2.27. Tìm một đường đi Hamilton từ đến .
Hình 2.27: đồ thị G có đỉnh vào S (ô vuông, trái, có mũi tên đi vào) và đỉnh ra R (ô vuông, phải, có mũi tên đi ra). Các đỉnh trong: A, C, F (trên), B, G, E (giữa), D (dưới). Các cạnh: S–A, S–D, A–C, A–B, C–F, C–B, C–G, C–E, C–D, F–E, B–D, B–G, G–D, G–E, E–D, E–R, D–R.
Lời giải
Phân tích. Đường đi Hamilton là đường đi qua mỗi đỉnh của đồ thị đúng một lần. Đồ thị có đỉnh là ; ta cần tìm đường đi xuất phát từ , kết thúc tại và đi qua đỉnh còn lại, mỗi đỉnh đúng một lần.
Nhận xét. Đỉnh chỉ nối với hai đỉnh và (bậc của bằng ). Vì không phải điểm đầu, cũng không phải điểm cuối của đường đi, nên khi đi qua ta buộc phải dùng cả hai cạnh và . Do đó đường đi cần tìm nhất định chứa đoạn liên tiếp .
Dựng đường đi. Từ chỉ có thể đi sang hoặc . Ta chọn , rồi sắp xếp các đỉnh còn lại sao cho giữ nguyên đoạn và kết thúc tại :
Kiểm tra.
- Các cạnh sử dụng: , , , , , , , — đều là cạnh của đồ thị . ✓
- Các đỉnh đi qua: — đủ đỉnh, mỗi đỉnh đúng một lần, bắt đầu tại và kết thúc tại . ✓
Kết luận. Một đường đi Hamilton từ đến là:
*(Bài toán có thể có nhiều đáp án; chẳng hạn cũng là một đường đi Hamilton từ đến .)*
Đá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.