Giải Bài 2.8 trang 44 Chuyên đề Toán 11
Đề 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?
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ó dải đất, kí hiệu bốn đỉnh , và cây cầu, tương ứng cạnh. Đếm số cầu nối vào mỗi dải đất, ta được bậc của các đỉnh:
(Tổng các bậc , đú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 hoặc bằng .
Ở đây cả bốn đỉnh đều có bậc lẻ (), tức là có đỉnh bậc lẻ. Vì 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ố
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.