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

Giải Bài 2.10 trang 44 Chuyên đề Toán 11

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

Đề bài

Cho đồ thị GG như Hình 2.27. Tìm một đường đi Hamilton từ SS đến RR.

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

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ị GG có 99 đỉnh là S,A,B,C,D,E,F,G,RS, A, B, C, D, E, F, G, R; ta cần tìm đường đi xuất phát từ SS, kết thúc tại RR và đi qua 77 đỉnh còn lại, mỗi đỉnh đúng một lần.

Nhận xét. Đỉnh FF chỉ nối với hai đỉnh CC và EE (bậc của FF bằng 22). Vì FF 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 FF ta buộc phải dùng cả hai cạnh CFCF và FEFE. Do đó đường đi cần tìm nhất định chứa đoạn liên tiếp C−F−EC - F - E.

Dựng đường đi. Từ SS chỉ có thể đi sang AA hoặc DD. Ta chọn S→AS \to A, rồi sắp xếp các đỉnh còn lại sao cho giữ nguyên đoạn C−F−EC - F - E và kết thúc tại RR:
S→A→B→G→D→C→F→E→R.S \to A \to B \to G \to D \to C \to F \to E \to R.

Kiểm tra.

- Các cạnh sử dụng: SASA, ABAB, BGBG, GDGD, DCDC, CFCF, FEFE, ERER — đều là cạnh của đồ thị GG. ✓

- Các đỉnh đi qua: S,A,B,G,D,C,F,E,RS, A, B, G, D, C, F, E, R — đủ 99 đỉnh, mỗi đỉnh đúng một lần, bắt đầu tại SS và kết thúc tại RR. ✓

Kết luận. Một đường đi Hamilton từ SS đến RR là:
S→A→B→G→D→C→F→E→R.S \to A \to B \to G \to D \to C \to F \to E \to R.

*(Bài toán có thể có nhiều đáp án; chẳng hạn S→A→C→F→E→G→B→D→RS \to A \to C \to F \to E \to G \to B \to D \to R cũng là một đường đi Hamilton từ SS đến RR.)*

Đáp số

S→A→B→G→D→C→F→E→RS \to A \to B \to G \to D \to C \to F \to E \to R

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.