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

Giải Bài 2.9 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.26. Tìm một chu trình Hamilton xuất phát từ đỉnh SS của GG.

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.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ị GG:
- SS: B,A,CB, A, C
- BB: S,DS, D
- DD: B,E,F,CB, E, F, C
- EE: D,F,RD, F, R
- FF: D,E,CD, E, C
- CC: S,D,A,H,FS, D, A, H, F
- AA: S,CS, C
- HH: C,RC, R
- RR: E,HE, H

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 22 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 BB bậc 2 (S,DS, D) ⇒\Rightarrow bắt buộc dùng S ⁣− ⁣BS\!-\!B và B ⁣− ⁣DB\!-\!D.
- Đỉnh AA bậc 2 (S,CS, C) ⇒\Rightarrow bắt buộc dùng S ⁣− ⁣AS\!-\!A và A ⁣− ⁣CA\!-\!C.
- Đỉnh HH bậc 2 (C,RC, R) ⇒\Rightarrow bắt buộc dùng C ⁣− ⁣HC\!-\!H và H ⁣− ⁣RH\!-\!R.
- Đỉnh RR bậc 2 (E,HE, H) ⇒\Rightarrow bắt buộc dùng R ⁣− ⁣ER\!-\!E và R ⁣− ⁣HR\!-\!H.

Suy ra khung của chu trình.

Tại SS đã có hai cạnh S ⁣− ⁣BS\!-\!B và S ⁣− ⁣AS\!-\!A, nên cạnh S ⁣− ⁣CS\!-\!C 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:
C ⁣− ⁣H ⁣− ⁣R ⁣− ⁣E.C\!-\!H\!-\!R\!-\!E.
Tại EE các cạnh còn lại là E ⁣− ⁣DE\!-\!D hoặc E ⁣− ⁣FE\!-\!F (cạnh E ⁣− ⁣RE\!-\!R đã dùng). Để còn ghép được đỉnh FF vào đường đi từ DD đến CC, ta chọn:
D ⁣− ⁣F ⁣− ⁣E ⁣− ⁣R ⁣− ⁣H ⁣− ⁣C.D\!-\!F\!-\!E\!-\!R\!-\!H\!-\!C.
Đoạn này dùng các cạnh D ⁣− ⁣F, F ⁣− ⁣E, E ⁣− ⁣R, R ⁣− ⁣H, H ⁣− ⁣CD\!-\!F,\ F\!-\!E,\ E\!-\!R,\ R\!-\!H,\ H\!-\!C đều là cạnh của GG.

Ghép thành chu trình Hamilton.

Nối các đoạn S ⁣− ⁣B ⁣− ⁣DS\!-\!B\!-\!D, D ⁣− ⁣F ⁣− ⁣E ⁣− ⁣R ⁣− ⁣H ⁣− ⁣CD\!-\!F\!-\!E\!-\!R\!-\!H\!-\!C và C ⁣− ⁣A ⁣− ⁣SC\!-\!A\!-\!S ta được:
S→B→D→F→E→R→H→C→A→S.S\to B\to D\to F\to E\to R\to H\to C\to A\to S.

Kiểm tra lại.

- Các đỉnh đi qua: S,B,D,F,E,R,H,C,AS, B, D, F, E, R, H, C, A — đúng 99 đỉnh, mỗi đỉnh một lần, rồi quay về SS.
- Các cạnh sử dụng: S ⁣− ⁣B, B ⁣− ⁣D, D ⁣− ⁣F, F ⁣− ⁣E, E ⁣− ⁣R, R ⁣− ⁣H, H ⁣− ⁣C, C ⁣− ⁣A, A ⁣− ⁣SS\!-\!B,\ B\!-\!D,\ D\!-\!F,\ F\!-\!E,\ E\!-\!R,\ R\!-\!H,\ H\!-\!C,\ C\!-\!A,\ A\!-\!S — tất cả đều là cạnh của GG.

Vậy đây là một chu trình Hamilton xuất phát từ SS.

Đáp số

Chu trình Hamilton: S→B→D→F→E→R→H→C→A→SS \to B \to D \to F \to E \to R \to H \to C \to A \to 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.