Giải Bài 2.25 trang 50 Chuyên đề Toán 11
Đề bài
Kiểm tra xem các điều kiện của định lí Ore có thoả mãn với các đồ thị trên Hình 2.39 không.
Hình 2.39: Hai đồ thị dạng ngũ giác với các đỉnh (đỉnh trên), (phải trên), (phải dưới), (trái dưới), (trái trên).
a) Ngũ giác có các cạnh ngoài , , , , ; cùng các cạnh trong (đường chéo): , , (từ kẻ tới và , và nối ).
b) Ngũ giác có các cạnh ngoài , , , , ; cùng một cạnh trong .
Lời giải
Nhắc lại định lí Ore. Nếu đơn đồ thị có đỉnh và với mọi cặp đỉnh không kề nhau ta đều có thì có chu trình Hamilton.
Cả hai đồ thị trong Hình 2.39 đều có đỉnh, nên ta cần kiểm tra điều kiện: mọi cặp đỉnh không kề nhau có tổng bậc không nhỏ hơn .
a) Đồ thị có các cạnh , , , , , , , .
Bậc của các đỉnh:
- kề với , , , nên ;
- kề với , , nên ;
- kề với , , nên ;
- kề với , , nên ;
- kề với , , nên .
Vì kề với tất cả các đỉnh còn lại nên các cặp đỉnh không kề nhau chỉ gồm và . Ta có:
Vậy mọi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn , do đó điều kiện của định lí Ore được thoả mãn.
b) Đồ thị có các cạnh , , , , , .
Bậc của các đỉnh:
- kề với , nên ;
- kề với , , nên ;
- kề với , nên ;
- kề với , nên ;
- kề với , , nên .
Các cặp đỉnh không kề nhau là , , , . Xét cặp :
Vậy tồn tại cặp đỉnh không kề nhau có tổng bậc nhỏ hơn , do đó điều kiện của định lí Ore không được thoả mãn.
Đá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.