Giải Bài 2.28 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.42.
Hình 2.42: Đồ thị 5 đỉnh A (trái), B (trên), C (dưới), D (giữa trái), E (giữa phải). Các cạnh và trọng số: A–B trọng số 4; A–C trọng số 4; A–D trọng số 2; A–C (đường cong dưới) — thực tế: A–D trọng số 2 và A–C trọng số 4 (các cung bên trái). B–D trọng số 2; B–E trọng số 3; D–E trọng số 6; D–C trọng số 2; C–E trọng số 1; B–E (cung ngoài bên phải) trọng số 5. Cụ thể các cạnh: A–B = 4, A–C = 4, B–D = 2, B–E = 3, B–E (cung ngoài) = 5, A–D = 2, D–E = 6, D–C = 2, C–E = 1.
Lời giải
Bước 1. Xét bậc các đỉnh của đồ thị.
Liệt kê các cạnh (có trọng số): , , , , , (cung ngoài), , , .
Bậc của mỗi đỉnh:
- : các cạnh (lẻ)
- : các cạnh (chẵn)
- : các cạnh (lẻ)
- : các cạnh (chẵn)
- : các cạnh (chẵn)
Tổng trọng số tất cả các cạnh:
Bước 2. Đồ thị có đúng hai đỉnh bậc lẻ là và .
Đồ thị không phải là đồ thị Euler. Người đưa thư buộc phải đi lại một số cạnh. Theo thuật toán giải bài toán người đưa thư: vì chỉ có hai đỉnh bậc lẻ và , ta cần nhân đôi (đi lại) các cạnh trên đường đi ngắn nhất nối và để mọi đỉnh đều có bậc chẵn.
Bước 3. Tìm đường đi ngắn nhất từ đến .
- (trực tiếp): độ dài
- :
- :
- :
Đường đi ngắn nhất từ đến có độ dài (chọn cạnh , hoặc đường ).
Bước 4. Độ dài hành trình ngắn nhất.
Người đưa thư đi qua tất cả các cạnh (tổng ) và đi lại thêm phần đường ngắn nhất nối hai đỉnh lẻ (độ dài ):
Bước 5. Chỉ ra một hành trình đạt độ dài nhỏ nhất.
Nhân đôi cạnh thì mọi đỉnh đều có bậc chẵn, đồ thị có chu trình Euler. Một hành trình (xuất phát và kết thúc tại ):
Kiểm tra tổng độ dài:
Hành trình này đi qua mỗi cạnh ít nhất một lần, chỉ đi lại cạnh một lần, và quay về điểm xuất phát. Vậy độ dài ngắn nhất của bài toán 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.