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

Giải Bài 2.14 trang 45 Chuyên đề Toán 11

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

Đề bài

Với giá trị nào của nn thì đồ thị đầy đủ KnK_n có một chu trình Hamilton? Có một đường đi Hamilton?

Lời giải

Nhắc lại. Đồ thị đầy đủ KnK_n là đồ thị có nn đỉnh, trong đó hai đỉnh phân biệt bất kì đều được nối với nhau bởi một cạnh. Nhờ tính chất này, với một thứ tự tùy ý của các đỉnh, mỗi đỉnh liền trước và đỉnh liền sau trong thứ tự đó luôn kề nhau, nên ta ghép chúng thành đường đi (hoặc chu trình) đi qua tất cả các đỉnh được.

a) Chu trình Hamilton.
- Một chu trình phải có ít nhất 33 đỉnh, nên trước hết cần n≥3n \ge 3.
- Với n≥3n \ge 3: đánh số các đỉnh là v1,v2,…,vnv_1, v_2, \dots, v_n. Vì KnK_n đầy đủ nên các cạnh v1v2, v2v3, …, vn−1vnv_1v_2,\ v_2v_3,\ \dots,\ v_{n-1}v_n và cạnh vnv1v_nv_1 đều tồn tại. Do đó
v1 v2 v3⋯vn−1 vn v1v_1 \, v_2 \, v_3 \cdots v_{n-1} \, v_n \, v_1
là một chu trình đi qua mỗi đỉnh đúng một lần, tức là một chu trình Hamilton.
- Với n=1n = 1 hoặc n=2n = 2: không có chu trình (chưa đủ 33 đỉnh).

Kết luận: KnK_n có chu trình Hamilton khi và chỉ khi n≥3n \ge 3.

b) Đường đi Hamilton.
- Với mọi n≥2n \ge 2: với các đỉnh v1,v2,…,vnv_1, v_2, \dots, v_n, các cạnh v1v2, v2v3, …, vn−1vnv_1v_2,\ v_2v_3,\ \dots,\ v_{n-1}v_n đều có trong KnK_n, nên
v1 v2 v3⋯vn−1 vnv_1 \, v_2 \, v_3 \cdots v_{n-1} \, v_n
là một đường đi qua mỗi đỉnh đúng một lần, tức là một đường đi Hamilton.
- Với n=1n = 1: đồ thị chỉ có một đỉnh, coi như đã có đường đi Hamilton tầm thường.

Kết luận: KnK_n có đường đi Hamilton với mọi n≥1n \ge 1 (có ý nghĩa thực sự khi n≥2n \ge 2).

Kiểm tra lại. K3K_3 (tam giác): có chu trình v1v2v3v1v_1v_2v_3v_1 — đúng. K2K_2 (một cạnh): có đường đi v1v2v_1v_2 nhưng không có chu trình — đúng với kết luận n≥3n\ge 3 cho chu trình. K4K_4: có cả chu trình lẫn đường đi Hamilton — phù hợp.

Đáp số

Chu trình Hamilton: với mọi n≥3n \ge 3Đường đi Hamilton: với mọi n≥1n \ge 1 (thực chất n≥2n \ge 2)

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.