Giải Bài 2.7 trang 44 Chuyên đề Toán 11
Đề bài
Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy chỉ ra một chu trình Euler hoặc một chu trình Hamilton khi có thể.
Hình 2.24 gồm bốn đồ thị:
a) 4 đỉnh: A ở đỉnh trên, D ở giữa, C dưới trái, B dưới phải. Cạnh: A–C, A–B, A–D, D–C, D–B, C–B (tam giác ACB với D ở trong nối cả ba đỉnh).
b) 5 đỉnh tạo ngũ giác đều: A trên đỉnh, B phải trên, C phải dưới, D trái dưới, E trái trên. Đồ thị đầy đủ K5: nối tất cả các cặp đỉnh (các cạnh ngũ giác A–B, B–C, C–D, D–E, E–A và các đường chéo A–C, A–D, B–D, B–E, C–E).
c) 8 đỉnh: hình vuông ngoài A (trên trái), B (trên phải), C (dưới phải), D (dưới trái); hình vuông trong E (trên trái), F (trên phải), G (dưới phải), H (dưới trái). Cạnh ngoài A–B, B–C, C–D, D–A; cạnh trong E–F, F–G, G–H, H–E; cạnh nối A–E, B–F, C–G, D–H.
d) 5 đỉnh: A, B hàng trên; E, D, C hàng dưới. Cạnh: A–E, A–D, B–D, B–C, A–C, B–E (hai nhánh đan chéo tương tự Hình 2.23a).
Lời giải
Kiến thức dùng: Một đồ thị liên thông có *chu trình Euler* khi và chỉ khi mọi đỉnh đều có bậc chẵn (chu trình Euler đi qua mỗi *cạnh* đúng một lần rồi về đỉnh xuất phát). Một *chu trình Hamilton* đi qua mỗi *đỉnh* đúng một lần rồi trở về đỉnh xuất phát.
a) Đồ thị 4 đỉnh (đồ thị đầy đủ ).
Các cạnh: . Mỗi đỉnh nối với cả ba đỉnh còn lại nên bậc mỗi đỉnh đều bằng (lẻ).
- Vì có đỉnh bậc lẻ nên đồ thị không có chu trình Euler.
- Đồ thị có chu trình Hamilton, chẳng hạn: (đi qua cả đỉnh, mỗi cạnh đều có trong đồ thị).
b) Đồ thị 5 đỉnh đầy đủ (nối mọi cặp đỉnh).
Mỗi đỉnh nối với đỉnh còn lại nên bậc mỗi đỉnh đều bằng (chẵn); đồ thị liên thông. Do đó đồ thị có chu trình Euler. Đồ thị có cạnh; một chu trình Euler là:
lần lượt dùng các cạnh — đúng đủ cạnh, mỗi cạnh một lần.
(Đồ thị cũng có chu trình Hamilton, ví dụ .)
c) Đồ thị 8 đỉnh dạng hình lập phương (vuông ngoài , vuông trong , các cạnh nối ).
Mỗi đỉnh có bậc (hai cạnh của hình vuông và một cạnh nối trong–ngoài), là số lẻ.
- Vì có đỉnh bậc lẻ nên đồ thị không có chu trình Euler.
- Đồ thị có chu trình Hamilton, chẳng hạn: (đi qua cả đỉnh; các cạnh đều có trong đồ thị).
d) Đồ thị 5 đỉnh (hàng trên) và (hàng dưới).
Các cạnh: . Bậc các đỉnh: và có bậc (lẻ); có bậc .
- Vì có đỉnh bậc lẻ () nên đồ thị không có chu trình Euler.
- Mọi cạnh đều nối một đỉnh thuộc với một đỉnh thuộc , không có cạnh nào trong cùng một nhóm. Một chu trình (nếu có) phải đi xen kẽ giữa hai nhóm nên chỉ có độ dài chẵn; nhưng một chu trình đi qua đủ đỉnh lại có độ dài (lẻ) — mâu thuẫn. Do đó đồ thị không có chu trình Hamilton.
Kiểm tra lại: tổng bậc từng đồ thị đều bằng :
a) ;
b) ;
c) ;
d) — khớp. Kết luận Euler dựa trên tính chẵn/lẻ của bậc là chính xác.
Đá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.