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

Giải Bài 2.26 trang 51 Chuyên đề Toán 11

Bài tập cuối chương II   Đã kiểm chéo

Đề bài

Tìm một chu trình Euler trong đồ thị trên Hình 2.40.

Bài có hình vẽ / bảng trong sách — xem ở trang 51 · mở sách.
Hình trong bài (mô tả bằng lời):

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 đó):

- deg⁡(A)\deg(A): các cạnh A ⁣− ⁣B, A ⁣− ⁣F, A ⁣− ⁣E, A ⁣− ⁣CA\!-\!B,\ A\!-\!F,\ A\!-\!E,\ A\!-\!C nên deg⁡(A)=4\deg(A)=4.
- deg⁡(B)\deg(B): các cạnh A ⁣− ⁣B, B ⁣− ⁣CA\!-\!B,\ B\!-\!C nên deg⁡(B)=2\deg(B)=2.
- deg⁡(C)\deg(C): các cạnh B ⁣− ⁣C, C ⁣− ⁣D, A ⁣− ⁣C, E ⁣− ⁣CB\!-\!C,\ C\!-\!D,\ A\!-\!C,\ E\!-\!C nên deg⁡(C)=4\deg(C)=4.
- deg⁡(D)\deg(D): các cạnh C ⁣− ⁣D, D ⁣− ⁣EC\!-\!D,\ D\!-\!E nên deg⁡(D)=2\deg(D)=2.
- deg⁡(E)\deg(E): các cạnh D ⁣− ⁣E, E ⁣− ⁣F, A ⁣− ⁣E, E ⁣− ⁣CD\!-\!E,\ E\!-\!F,\ A\!-\!E,\ E\!-\!C nên deg⁡(E)=4\deg(E)=4.
- deg⁡(F)\deg(F): các cạnh E ⁣− ⁣F, F ⁣− ⁣AE\!-\!F,\ F\!-\!A nên deg⁡(F)=2\deg(F)=2.

Tất cả các đỉnh đều có bậc chẵn (4,2,4,2,4,24,2,4,2,4,2) và đồ thị liên thông. Do đó đồ thị có chu trình Euler.

Bước 2. Tìm chu trình Euler.

Đồ thị có 99 cạnh, nên chu trình Euler phải đi qua đúng 99 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 AA, lần lượt đi theo các cạnh chưa dùng:

A→B→C→D→E→F→A→E→C→A.A \to B \to C \to D \to E \to F \to A \to E \to C \to A.

Bước 3. Kiểm tra lại.

Các cạnh đã đi qua theo thứ tự:
A ⁣− ⁣B, B ⁣− ⁣C, C ⁣− ⁣D, D ⁣− ⁣E, E ⁣− ⁣F, F ⁣− ⁣A, A ⁣− ⁣E, E ⁣− ⁣C, C ⁣− ⁣A.A\!-\!B,\ B\!-\!C,\ C\!-\!D,\ D\!-\!E,\ E\!-\!F,\ F\!-\!A,\ A\!-\!E,\ E\!-\!C,\ C\!-\!A.

Đây đúng là 99 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 AA (nơi xuất phát). Vậy đó là một chu trình Euler cần tìm.

Đáp số

Một chu trình Euler: A→B→C→D→E→F→A→E→C→AA \to B \to C \to D \to E \to F \to A \to E \to C \to A

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.