Giải Bài 2.18 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.36.
Hình 2.36: Đồ thị có trọng số gồm 5 đỉnh A, B, C, D, E. Các cạnh và trọng số: A–B = 1; A–C = 2; B–C = 4; B–D = 3; B–E = 5 (đường chéo); C–E = 10; D–E = 6.
Lời giải
Phân tích bài toán người đưa thư. Người đưa thư cần xuất phát từ một đỉnh, đi qua mỗi cạnh ít nhất một lần rồi trở về đỉnh xuất phát sao cho tổng quãng đường đi là nhỏ nhất.
Bước 1. Tính tổng trọng số các cạnh.
Tổng trọng số của toàn bộ các cạnh là:
Đây là quãng đường nếu mỗi cạnh chỉ đi đúng một lần.
Bước 2. Xét bậc các đỉnh để tìm chu trình Euler.
Đồ thị có chu trình Euler (mỗi cạnh đi đúng một lần, về chỗ cũ) khi và chỉ khi mọi đỉnh đều có bậc chẵn. Ta tính bậc:
| Đỉnh | Các cạnh kề | Bậc |
|---|---|---|
| | | |
| | | |
| | | |
| | | |
| | | |
Có đúng hai đỉnh bậc lẻ là và . Do đó đồ thị không có chu trình Euler; người đưa thư buộc phải đi lặp lại một số cạnh.
Bước 3. Tìm quãng đường đi lặp nhỏ nhất.
Vì chỉ có hai đỉnh bậc lẻ và , ta cần đi lặp thêm các cạnh trên đường đi ngắn nhất nối và (khi đó và trở thành bậc chẵn, mọi đỉnh đều bậc chẵn). So sánh các đường đi từ đến :
- (trực tiếp):
- :
- :
- :
Đường đi ngắn nhất là với độ dài . Vậy cần đi lặp lại các cạnh .
Bước 4. Tính tổng quãng đường nhỏ nhất.
Bước 5. Chỉ ra một hành trình đạt độ dài .
Sau khi thêm bản sao của các cạnh , mọi đỉnh đều có bậc chẵn nên tồn tại chu trình Euler trên đồ thị mới. Một hành trình thỏa mãn (xuất phát và kết thúc tại ) là:
Kiểm tra tổng: (các cạnh được đi hai lần, các cạnh còn lại đi một lần).
Kết luận: 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.