Giải Bài 2.26 trang 51 Chuyên đề Toán 11
Đề bài
Tìm một chu trình Euler trong đồ thị trên Hình 2.40.
Hình 2.40: Đồ thị gồm 6 đỉnh A, B, C, D, E, F sắp xếp thành hình lục giác (A trên đỉnh, theo chiều kim đồng hồ: A, B, C, D, E, F). Các cạnh: A–B, B–C, C–D, D–E, E–F, F–A (các cạnh của lục giác ngoài); thêm các cạnh chéo bên trong: A–E, A–C và E–C (tạo thành tam giác A, E, C).
Lời giải
Bước 1. Kiểm tra điều kiện tồn tại chu trình Euler.
Đồ thị có chu trình Euler khi và chỉ khi nó liên thông và mọi đỉnh đều có bậc chẵn.
Liệt kê bậc của từng đỉnh (đếm số cạnh nối với đỉnh đó):
- : các cạnh nên .
- : các cạnh nên .
- : các cạnh nên .
- : các cạnh nên .
- : các cạnh nên .
- : các cạnh nên .
Tất cả các đỉnh đều có bậc chẵn () và đồ thị liên thông. Do đó đồ thị có chu trình Euler.
Bước 2. Tìm chu trình Euler.
Đồ thị có cạnh, nên chu trình Euler phải đi qua đúng cạnh, mỗi cạnh một lần, rồi trở về đỉnh xuất phát. Xuất phát từ đỉnh , lần lượt đi theo các cạnh chưa dùng:
Bước 3. Kiểm tra lại.
Các cạnh đã đi qua theo thứ tự:
Đây đúng là cạnh của đồ thị, mỗi cạnh được đi qua đúng một lần, và chu trình kết thúc tại đỉnh (nơi xuất phát). Vậy đó là một chu trình Euler cần tìm.
Đá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.