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

Giải Bài 2.8 trang 44 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm chéo

Đề bài

Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần?

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

Hình 2.25: hình vẽ minh họa các nhánh sông và các cây cầu bắc qua (hình phong cách cổ điển bài toán cầu Euler), gồm các dải đất và nhiều cây cầu nối giữa chúng.

Lời giải

Mô hình hoá bằng đồ thị.

Ta coi mỗi dải đất là một đỉnh và mỗi cây cầu là một cạnh nối hai dải đất mà nó bắc qua. Khi đó "đi dạo qua mỗi cây cầu đúng một lần" chính là tìm một đường đi Euler (đường đi qua mỗi cạnh của đồ thị đúng một lần) trên đồ thị này.

Hình 2.25 chính là bài toán bảy cây cầu ở Königsberg: có 44 dải đất, kí hiệu bốn đỉnh A, B, C, DA,\,B,\,C,\,D, và 77 cây cầu, tương ứng 77 cạnh. Đếm số cầu nối vào mỗi dải đất, ta được bậc của các đỉnh:
deg⁡(A)=3,deg⁡(B)=3,deg⁡(C)=3,deg⁡(D)=5.\deg(A)=3,\quad \deg(B)=3,\quad \deg(C)=3,\quad \deg(D)=5.
(Tổng các bậc =3+3+3+5=14=2⋅7=3+3+3+5=14=2\cdot 7, đúng bằng hai lần số cạnh, phù hợp.)

Áp dụng định lí Euler.

Đồ thị liên thông có đường đi Euler khi và chỉ khi số đỉnh bậc lẻ bằng 00 hoặc bằng 22.

Ở đây cả bốn đỉnh A, B, C, DA,\,B,\,C,\,D đều có bậc lẻ (3, 3, 3, 53,\,3,\,3,\,5), tức là có 44 đỉnh bậc lẻ. Vì 4>24>2 nên đồ thị không có đường đi Euler.

Kết luận. Không thể đi dạo qua tất cả các cây cầu trong Hình 2.25 mà mỗi cây cầu đi đúng một lần.

Đáp số

Không thể — đồ thị có 4 đỉnh bậc lẻ nên không có đường đi Euler

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.