Chuyên đề học tập Toán 11

Giải Bài 2.28 trang 51 Chuyên đề Toán 11

Bài tập cuối chương II   Đã kiểm chéo

Đề 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.

Bài có hình vẽ / bảng trong sách — xem ở trang 51 · mở sách.
Hình trong bài (mô tả bằng lời):

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ố): AB=4AB=4, AC=4AC=4, AD=2AD=2, BD=2BD=2, BE=3BE=3, BE=5BE=5 (cung ngoài), DE=6DE=6, DC=2DC=2, CE=1CE=1.

Bậc của mỗi đỉnh:
- deg⁡(A)\deg(A): các cạnh AB, AC, AD⇒deg⁡(A)=3AB,\,AC,\,AD \Rightarrow \deg(A)=3 (lẻ)
- deg⁡(B)\deg(B): các cạnh AB, BD, BE, BE⇒deg⁡(B)=4AB,\,BD,\,BE,\,BE \Rightarrow \deg(B)=4 (chẵn)
- deg⁡(C)\deg(C): các cạnh AC, DC, CE⇒deg⁡(C)=3AC,\,DC,\,CE \Rightarrow \deg(C)=3 (lẻ)
- deg⁡(D)\deg(D): các cạnh AD, BD, DE, DC⇒deg⁡(D)=4AD,\,BD,\,DE,\,DC \Rightarrow \deg(D)=4 (chẵn)
- deg⁡(E)\deg(E): các cạnh BE, BE, DE, CE⇒deg⁡(E)=4BE,\,BE,\,DE,\,CE \Rightarrow \deg(E)=4 (chẵn)

Tổng trọng số tất cả các cạnh:
4+4+2+2+3+5+6+2+1=29.4+4+2+2+3+5+6+2+1 = 29.

Bước 2. Đồ thị có đúng hai đỉnh bậc lẻ là AA và CC.

Đồ 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ẻ AA và CC, ta cần nhân đôi (đi lại) các cạnh trên đường đi ngắn nhất nối AA và CC để mọi đỉnh đều có bậc chẵn.

Bước 3. Tìm đường đi ngắn nhất từ AA đến CC.

- A→CA \to C (trực tiếp): độ dài 44
- A→D→CA \to D \to C: 2+2=42+2 = 4
- A→B→D→CA \to B \to D \to C: 4+2+2=84+2+2 = 8
- A→D→E→CA \to D \to E \to C: 2+6+1=92+6+1 = 9

Đường đi ngắn nhất từ AA đến CC có độ dài min⁡=4\min = 4 (chọn cạnh ACAC, hoặc đường A ⁣− ⁣D ⁣− ⁣CA\!-\!D\!-\!C).

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 2929) và đi lại thêm phần đường ngắn nhất nối hai đỉnh lẻ (độ dài 44):
Lmin⁡=29+4=33.L_{\min} = 29 + 4 = 33.

Bước 5. Chỉ ra một hành trình đạt độ dài nhỏ nhất.

Nhân đôi cạnh ACAC 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 AA):
A→2D→2B→3E→5B→4A→4C→1E→6D→2C→4A.A \xrightarrow{2} D \xrightarrow{2} B \xrightarrow{3} E \xrightarrow{5} B \xrightarrow{4} A \xrightarrow{4} C \xrightarrow{1} E \xrightarrow{6} D \xrightarrow{2} C \xrightarrow{4} A.

Kiểm tra tổng độ dài:
2+2+3+5+4+4+1+6+2+4=33.2+2+3+5+4+4+1+6+2+4 = 33.

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 ACAC 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à 3333.

Đáp số

Độ dài hành trình ngắn nhất: 33 (đi lại cạnh AC; ví dụ A–D–B–E–B–A–C–E–D–C–A)

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.