Giải Bài 2.14 trang 45 Chuyên đề Toán 11
Đề bài
Với giá trị nào của thì đồ thị đầy đủ có một chu trình Hamilton? Có một đường đi Hamilton?
Lời giải
Nhắc lại. Đồ thị đầy đủ là đồ thị có đỉ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 đỉnh, nên trước hết cần .
- Với : đánh số các đỉnh là . Vì đầy đủ nên các cạnh và cạnh đều tồn tại. Do đó
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 hoặc : không có chu trình (chưa đủ đỉnh).
Kết luận: có chu trình Hamilton khi và chỉ khi .
b) Đường đi Hamilton.
- Với mọi : với các đỉnh , các cạnh đều có trong , nê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 : đồ thị chỉ có một đỉnh, coi như đã có đường đi Hamilton tầm thường.
Kết luận: có đường đi Hamilton với mọi (có ý nghĩa thực sự khi ).
Kiểm tra lại. (tam giác): có chu trình — đúng. (một cạnh): có đường đi nhưng không có chu trình — đúng với kết luận cho chu trình. : có cả chu trình lẫn đường đi Hamilton — phù hợp.
Đá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.