Giải Luyện tập 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.32.
Hình 2.32: Đồ 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 = 2; A–F = 10; A–E = 7; B–E = 8; B–C = 3; B–D = 15; C–D = 4; E–D = 16; F–E = 9.
Lời giải
Bài toán người đưa thư yêu cầu tìm hành trình xuất phát từ một đỉnh, đi qua mỗi 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 ngắn nhất.
Bước 1. Xác định bậc các đỉnh
| Đỉnh | Các cạnh kề | Bậc |
|------|-------------|-----|
| | | (lẻ) |
| | | (chẵn) |
| | | (chẵn) |
| | | (lẻ) |
| | | (chẵn) |
| | | (chẵn) |
Đồ thị có đúng hai đỉnh bậc lẻ là và nên không có chu trình Euler. Do đó người đưa thư buộc phải đi lặp lại một số cạnh trên đường đi ngắn nhất nối với .
Bước 2. Tổng trọng số tất cả các cạnh
Bước 3. Tìm đường đi ngắn nhất nối hai đỉnh bậc lẻ và
Đường đi ngắn nhất là với độ dài .
Bước 4. Độ dài hành trình ngắn nhất
Đi lặp lại (nhân đôi) ba cạnh thì mọi đỉnh đều có bậc chẵn, nên tồn tại chu trình đi qua tất cả các cạnh và quay về . Độ dài ngắn nhất là
Bước 5. Một hành trình cụ thể (xuất phát và kết thúc tại )
Kiểm tra: hành trình đi qua đủ cạnh gốc, trong đó lặp lại , và
Vậy quãng đường ngắn nhất của người đưa thư là .
Đá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.