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

Giải Luyện tập trang 49 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã kiểm

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

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

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 |
|------|-------------|-----|
| AA | AB, AE, AFAB,\ AE,\ AF | 33 (lẻ) |
| BB | AB, BC, BD, BEAB,\ BC,\ BD,\ BE | 44 (chẵn) |
| CC | BC, CDBC,\ CD | 22 (chẵn) |
| DD | BD, CD, DEBD,\ CD,\ DE | 33 (lẻ) |
| EE | AE, BE, DE, EFAE,\ BE,\ DE,\ EF | 44 (chẵn) |
| FF | AF, EFAF,\ EF | 22 (chẵn) |

Đồ thị có đúng hai đỉnh bậc lẻ là AA và DD 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 AA với DD.

Bước 2. Tổng trọng số tất cả các cạnh

S=2+10+7+8+3+15+4+16+9=74.S = 2+10+7+8+3+15+4+16+9 = 74.

Bước 3. Tìm đường đi ngắn nhất nối hai đỉnh bậc lẻ AA và DD

A ⁣− ⁣B ⁣− ⁣D=2+15=17,A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣D=2+3+4=9,A\!-\!B\!-\!D = 2+15 = 17,\qquad A\!-\!B\!-\!C\!-\!D = 2+3+4 = 9,
A ⁣− ⁣E ⁣− ⁣D=7+16=23,A ⁣− ⁣E ⁣− ⁣B ⁣− ⁣C ⁣− ⁣D=7+8+3+4=22.A\!-\!E\!-\!D = 7+16 = 23,\qquad A\!-\!E\!-\!B\!-\!C\!-\!D = 7+8+3+4 = 22.

Đường đi ngắn nhất là A ⁣− ⁣B ⁣− ⁣C ⁣− ⁣DA\!-\!B\!-\!C\!-\!D với độ dài 99.

Bước 4. Độ dài hành trình ngắn nhất

Đi lặp lại (nhân đôi) ba cạnh AB, BC, CDAB,\ BC,\ CD 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ề AA. Độ dài ngắn nhất là

Wmin⁡=74+9=83.W_{\min} = 74 + 9 = 83.

Bước 5. Một hành trình cụ thể (xuất phát và kết thúc tại AA)

A→2B→3C→4D→16E→8B→15D→4C→3B→2A→10F→9E→7A.A \xrightarrow{2} B \xrightarrow{3} C \xrightarrow{4} D \xrightarrow{16} E \xrightarrow{8} B \xrightarrow{15} D \xrightarrow{4} C \xrightarrow{3} B \xrightarrow{2} A \xrightarrow{10} F \xrightarrow{9} E \xrightarrow{7} A.

Kiểm tra: hành trình đi qua đủ 99 cạnh gốc, trong đó lặp lại AB, BC, CDAB,\ BC,\ CD, và

2+3+4+16+8+15+4+3+2+10+9+7=83.2+3+4+16+8+15+4+3+2+10+9+7 = 83.

Vậy quãng đường ngắn nhất của người đưa thư là 8383.

Đáp số

Hành trình ngắn nhất của người đưa thư: A→B→C→D→E→B→D→C→B→A→F→E→AA \to B \to C \to D \to E \to B \to D \to C \to B \to A \to F \to E \to A, tổng trọng số =83= 83

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.