Giải Bài 2.17 trang 49 Chuyên đề Toán 11
Đề bài
Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.
Hình 2.35: Đồ thị có trọng số gồm 6 đỉnh A, B, C, D, E, F. Các cạnh và trọng số: A–B = 3; A–C = 4; B–D = 6; B–C = 5; B–E = 8 (đường chéo); D–C = 2 (đường chéo); D–E = 4 (đường chéo); D–F = 3; C–E = 7; E–F = 9.
Lời giải
Nhắc lại cách giải bài toán người đưa thư: Người đưa thư xuất phát từ một đỉnh, phải đi qua tất cả các cạnh (ít nhất một lần) rồi quay về đỉnh xuất phát, sao cho tổng quãng đường đi là nhỏ nhất.
- Nếu đồ thị (liên thông) có mọi đỉnh đều bậc chẵn thì nó có chu trình Euler (đi qua mỗi cạnh đúng một lần rồi về chỗ cũ). Khi đó quãng đường ngắn nhất đúng bằng tổng trọng số tất cả các cạnh (không phải đi lại cạnh nào).
- Nếu có đỉnh bậc lẻ thì bắt buộc phải đi lặp lại một số cạnh.
Bước 1. Xét bậc của các đỉnh.
Liệt kê các cạnh:
| Đỉnh | Các cạnh kề | Bậc |
|---|---|---|
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
Mọi đỉnh đều có bậc chẵn và đồ thị liên thông, nên đồ thị có chu trình Euler. Vì vậy người đưa thư có thể đi qua mỗi cạnh đúng một lần rồi trở về đỉnh xuất phát, không phải đi lặp lại cạnh nào.
Bước 2. Tính độ dài quãng đường ngắn nhất.
Quãng đường ngắn nhất bằng tổng trọng số tất cả các cạnh:
Bước 3. Chỉ ra một hành trình (chu trình Euler) cụ thể.
Xuất phát từ :
Hành trình này đi qua đủ cả cạnh, mỗi cạnh đúng một lần, rồi quay về . Tổng độ dài:
Kết luận: Người đưa thư nên đi theo một chu trình Euler của đồ thị; quãng đường ngắn nhất cần đi là (đơn vị độ dài).
Đá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.