Giải Bài 2.27 trang 51 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.41.
Hình 2.41: Đồ thị 4 đỉnh A (trên trái), B (trên phải), C (dưới phải), D (dưới trái). Các cạnh và trọng số: A–B có hai cạnh song song với trọng số 7 (cung ngoài phía trên) và 1 (cạnh trong); A–D trọng số 5 (cạnh trái); B–C trọng số 6 (cạnh phải); D–C có hai cạnh song song với trọng số 3 (cạnh trong) và 8 (cung ngoài phía dưới); hai đường chéo: A–C trọng số 2 và B–D trọng số 4.
Lời giải
Phân tích bài toán. Bài toán người đưa thư yêu cầu tìm một hành trình khép kín (xuất phát và kết thúc tại cùng một đỉnh) đi qua mỗi cạnh ít nhất một lần sao cho tổng trọng số nhỏ nhất.
Bước 1. Tính tổng trọng số của tất cả các cạnh.
Đồ thị có 8 cạnh với trọng số:
Tổng trọng số:
Bước 2. Xét bậc của các đỉnh.
Đếm số cạnh nối với mỗi đỉnh (lưu ý – và – đều có hai cạnh song song):
- : hai cạnh tới , một cạnh tới , một cạnh tới
- : hai cạnh tới , một cạnh tới , một cạnh tới
- : một cạnh tới , hai cạnh tới , một cạnh tới
- : một cạnh tới , hai cạnh tới , một cạnh tới
Mọi đỉnh đều có bậc chẵn, nên đồ thị có chu trình Euler: người đưa thư có thể đi qua mỗi cạnh đúng một lần rồi trở về điểm xuất phát mà không phải lặp lại cạnh nào.
Bước 3. Kết luận độ dài hành trình ngắn nhất.
Vì tồn tại chu trình Euler nên không cần đi lặp bất kì cạnh nào; hành trình ngắn nhất có độ dài bằng đúng tổng trọng số các cạnh:
Bước 4. Chỉ ra một hành trình thỏa mãn.
Một chu trình Euler xuất phát từ :
Hành trình này đi qua cả 8 cạnh đúng một lần và có tổng trọng số:
Kiểm tra lại. Các cạnh được dùng: –, –, –, –, –, –, –, – — đủ 8 cạnh, mỗi cạnh một lần, xuất phát và kết thúc tại . Vậy độ dài nhỏ nhất của hành trình 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.