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

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

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

Đề 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ể.

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.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 A,B,C,DA, B, C, D (đồ thị đầy đủ K4K_4).

Các cạnh: A–C, A–B, A–D, D–C, D–B, C–BA\text{–}C,\ A\text{–}B,\ A\text{–}D,\ D\text{–}C,\ D\text{–}B,\ C\text{–}B. Mỗi đỉnh nối với cả ba đỉnh còn lại nên bậc mỗi đỉnh đều bằng 33 (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: A→B→C→D→AA \to B \to C \to D \to A (đi qua cả 44 đỉnh, mỗi cạnh AB,BC,CD,DAAB, BC, CD, DA đều có trong đồ thị).

b) Đồ thị 5 đỉnh đầy đủ K5K_5 (nối mọi cặp đỉnh).

Mỗi đỉnh nối với 44 đỉnh còn lại nên bậc mỗi đỉnh đều bằng 44 (chẵn); đồ thị liên thông. Do đó đồ thị có chu trình Euler. Đồ thị có 1010 cạnh; một chu trình Euler là:
A→B→C→D→E→A→C→E→B→D→A,A \to B \to C \to D \to E \to A \to C \to E \to B \to D \to A,
lần lượt dùng các cạnh AB,BC,CD,DE,EA,AC,CE,EB,BD,DAAB, BC, CD, DE, EA, AC, CE, EB, BD, DA — đúng đủ 1010 cạnh, mỗi cạnh một lần.

(Đồ thị cũng có chu trình Hamilton, ví dụ A→B→C→D→E→AA \to B \to C \to D \to E \to A.)

c) Đồ thị 8 đỉnh dạng hình lập phương (vuông ngoài ABCDABCD, vuông trong EFGHEFGH, các cạnh nối A–E,B–F,C–G,D–HA\text{–}E, B\text{–}F, C\text{–}G, D\text{–}H).

Mỗi đỉnh có bậc 33 (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: A→B→C→D→H→G→F→E→AA \to B \to C \to D \to H \to G \to F \to E \to A (đi qua cả 88 đỉnh; các cạnh AB,BC,CD,DH,HG,GF,FE,EAAB, BC, CD, DH, HG, GF, FE, EA đều có trong đồ thị).

d) Đồ thị 5 đỉnh A,BA, B (hàng trên) và C,D,EC, D, E (hàng dưới).

Các cạnh: A–E,A–D,A–C,B–D,B–C,B–EA\text{–}E, A\text{–}D, A\text{–}C, B\text{–}D, B\text{–}C, B\text{–}E. Bậc các đỉnh: AA và BB có bậc 33 (lẻ); C,D,EC, D, E có bậc 22.

- Vì có đỉnh bậc lẻ (A,BA, B) nên đồ thị không có chu trình Euler.
- Mọi cạnh đều nối một đỉnh thuộc {A,B}\{A, B\} với một đỉnh thuộc {C,D,E}\{C, D, E\}, 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 đủ 55 đỉnh lại có độ dài 55 (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 2×(số cạnh)2\times(\text{số cạnh}):

a) 4⋅3=12=2⋅64\cdot3=12=2\cdot6;

b) 5⋅4=20=2⋅105\cdot4=20=2\cdot10;

c) 8⋅3=24=2⋅128\cdot3=24=2\cdot12;

d) 3+3+2+2+2=12=2⋅63+3+2+2+2=12=2\cdot6 — 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ố

a) Không có chu trình Euler (các đỉnh bậc 3 lẻ); có chu trình Hamilton: A→B→C→D→Ab) Có chu trình Euler: A→B→C→D→E→A→C→E→B→D→A (và có chu trình Hamilton A→B→C→D→E→A)c) Không có chu trình Euler (các đỉnh bậc 3 lẻ); có chu trình Hamilton: A→B→C→D→H→G→F→E→Ad) Không có chu trình Euler (A, B bậc lẻ) và không có chu trình Hamilton (đồ thị hai phía, không có chu trình lẻ qua đủ 5 đỉnh)

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.