Giải Bài 2.12 trang 45 Chuyên đề Toán 11
Đề bài
a) Giả sử là một đồ thị với đỉnh và cạnh. Sử dụng Định lí Ore, hãy chứng minh có một chu trình Hamilton.
b) Tìm một đồ thị với đỉnh và cạnh mà không có chu trình Hamilton.
Lời giải
Nhắc lại Định lí Ore. Cho là đồ thị đơn, vô hướng có đỉnh với . Nếu với *mọi* cặp đỉnh không kề nhau ta đều có thì có một chu trình Hamilton.
a) Chứng minh có chu trình Hamilton.
Số cạnh của là
Lấy tùy ý hai đỉnh không kề nhau của . Ta sẽ chứng minh .
Xóa hai đỉnh (cùng các cạnh nối với chúng) khỏi , ta được một đồ thị đơn có đỉnh. Vì đồ thị đơn đỉnh có nhiều nhất cạnh nên
Mỗi cạnh bị xóa khi bỏ là cạnh nối với hoặc nối với . Do và *không kề nhau* nên không có cạnh nào nối trực tiếp với , vì vậy số cạnh nối với hoặc đúng bằng (không bị đếm trùng). Suy ra
Từ đó
Tính hiệu hai phân số:
Vậy
Vì là cặp đỉnh không kề nhau tùy ý nên điều kiện của Định lí Ore được thỏa mãn (với ). Theo Định lí Ore, có một chu trình Hamilton.
b) Đồ thị có cạnh mà không có chu trình Hamilton.
Xét đồ thị gồm:
- Một đồ thị đầy đủ trên đỉnh (mọi cặp trong đỉnh này đều kề nhau), có đúng cạnh;
- Thêm đỉnh thứ , gọi là , và nối với đúng một đỉnh của bằng một cạnh.
Khi đó có đỉnh và số cạnh là
Đỉnh chỉ có . Trong một chu trình Hamilton, mỗi đỉnh phải nối với hai đỉnh khác của chu trình, tức mọi đỉnh của chu trình đều có bậc ít nhất bằng . Vì nên không thể nằm trên bất kì chu trình nào; do đó không có chu trình Hamilton.
(Đồ thị này cho thấy số cạnh ở câu a) là nhỏ nhất bảo đảm chắc chắn có chu trình Hamilton: chỉ cần ít hơn cạnh thì kết luận có thể không còn đúng.)
Đá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.