Giải Bài 2.9 trang 44 Chuyên đề Toán 11
Đề bài
Cho đồ thị như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh của .
Hình 2.26: đồ thị G có các đỉnh S (trái giữa), B (trên trái), D (giữa trên), E (trên phải), F (giữa phải), C (giữa dưới), A (dưới trái), H (dưới giữa), R (phải dưới). Các cạnh: S–B, S–A, S–C, B–D, D–E, D–F, D–C, E–F, E–R, C–A, C–H, C–F, H–R.
Lời giải
Phân tích các đỉnh bậc 2 (bắt buộc đi qua).
Ta liệt kê các đỉnh kề của đồ thị :
- :
- :
- :
- :
- :
- :
- :
- :
- :
Một chu trình Hamilton đi qua mỗi đỉnh đúng một lần rồi quay về đỉnh xuất phát, nên tại mỗi đỉnh chu trình dùng đúng cạnh. Với các đỉnh chỉ có bậc 2, cả hai cạnh của nó buộc phải nằm trong chu trình:
- Đỉnh bậc 2 () bắt buộc dùng và .
- Đỉnh bậc 2 () bắt buộc dùng và .
- Đỉnh bậc 2 () bắt buộc dùng và .
- Đỉnh bậc 2 () bắt buộc dùng và .
Suy ra khung của chu trình.
Tại đã có hai cạnh và , nên cạnh không được dùng (mỗi đỉnh chỉ dùng 2 cạnh). Từ các cạnh bắt buộc trên, ta ghép được đoạn:
Tại các cạnh còn lại là hoặc (cạnh đã dùng). Để còn ghép được đỉnh vào đường đi từ đến , ta chọn:
Đoạn này dùng các cạnh đều là cạnh của .
Ghép thành chu trình Hamilton.
Nối các đoạn , và ta được:
Kiểm tra lại.
- Các đỉnh đi qua: — đúng đỉnh, mỗi đỉnh một lần, rồi quay về .
- Các cạnh sử dụng: — tất cả đều là cạnh của .
Vậy đây là một chu trình Hamilton xuất phát từ .
Đá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.