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

Giải Bài 2.18 trang 49 Chuyên đề Toán 11

Bài 9. Đường đi Euler và đường đi Hamilton   Đã 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.36.

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.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à:
S=1+2+4+3+5+10+6=31.S = 1 + 2 + 4 + 3 + 5 + 10 + 6 = 31.
Đâ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 |
|---|---|---|
| AA | AB,ACAB, AC | 22 |
| BB | AB,BC,BD,BEAB, BC, BD, BE | 44 |
| CC | AC,BC,CEAC, BC, CE | 33 |
| DD | BD,DEBD, DE | 22 |
| EE | BE,CE,DEBE, CE, DE | 33 |

Có đúng hai đỉnh bậc lẻ là CC và EE. 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ẻ CC và EE, ta cần đi lặp thêm các cạnh trên đường đi ngắn nhất nối CC và EE (khi đó CC và EE trở thành bậc chẵn, mọi đỉnh đều bậc chẵn). So sánh các đường đi từ CC đến EE:

- C→EC \to E (trực tiếp): 1010
- C→B→EC \to B \to E: 4+5=94 + 5 = 9
- C→A→B→EC \to A \to B \to E: 2+1+5=82 + 1 + 5 = 8
- C→B→D→EC \to B \to D \to E: 4+3+6=134 + 3 + 6 = 13

Đường đi ngắn nhất là C→A→B→EC \to A \to B \to E với độ dài 88. Vậy cần đi lặp lại các cạnh CA,  AB,  BECA,\; AB,\; BE.

Bước 4. Tính tổng quãng đường nhỏ nhất.

ℓmin⁡=S+8=31+8=39.\ell_{\min} = S + 8 = 31 + 8 = 39.

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

Sau khi thêm bản sao của các cạnh AB,AC,BEAB, AC, BE, 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 AA) là:
A→1B→4C→10E→5B→5E→6D→3B→1A→2C→2A.A \xrightarrow{1} B \xrightarrow{4} C \xrightarrow{10} E \xrightarrow{5} B \xrightarrow{5} E \xrightarrow{6} D \xrightarrow{3} B \xrightarrow{1} A \xrightarrow{2} C \xrightarrow{2} A.
Kiểm tra tổng: 1+4+10+5+5+6+3+1+2+2=391+4+10+5+5+6+3+1+2+2 = 39 (các cạnh AB,AC,BEAB, AC, BE đượ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à 3939.

Đáp số

Quãng đường nhỏ nhất bằng 39 (đi lặp thêm các cạnh CA, AB, BE); ví dụ hành trình A–B–C–E–B–E–D–B–A–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.