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

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

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

Đề bài

Tìm đường đi ngắn nhất từ đỉnh SS đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.

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.34: Đồ thị có trọng số gồm các đỉnh S, A, D, B, E, C, F. Các cạnh và trọng số: S–A = 2; S–B = 1; S–C = 7; A–D = 5; A–B = 6; A–E = 12 (hoặc cạnh chéo); D–E = 2; B–E = 15; B–F = 10; B–C = 5; C–F = 14; E–F = 6; C–E = 9; và cạnh A–E = 8. Các số ghi trên hình: S–A = 2, S–B = 1, S–C = 7, A–D = 5, A–B = 6, D–E = 2, B–E = 15, đường chéo = 8, B–C = 5, C–F = 14, E–F = 6, B–F = 10, C–E = 9, D–... = 12.

Lời giải

Ta dùng thuật toán Dijkstra (thuật toán gán nhãn) để tìm đường đi ngắn nhất từ đỉnh SS đến mọi đỉnh còn lại.

Ý tưởng: Mỗi đỉnh được gán một *nhãn tạm thời* là độ dài đường đi ngắn nhất tạm tính từ SS. Ở mỗi bước, ta chọn đỉnh có nhãn tạm nhỏ nhất để cố định (nhãn đó trở thành chính thức), rồi dùng nó để cập nhật nhãn của các đỉnh kề.

Trọng số các cạnh (theo Hình 2.34):
SA=2, SB=1, SC=7, AB=6, AD=5, AE=8, BC=5, BE=15, BF=10, CE=9, CF=14, DE=2, EF=6.SA=2,\ SB=1,\ SC=7,\ AB=6,\ AD=5,\ AE=8,\ BC=5,\ BE=15,\ BF=10,\ CE=9,\ CF=14,\ DE=2,\ EF=6.

a) Tiến hành gán nhãn (ô ghi nhãn tạm hiện hành; dấu ∗* đánh dấu đỉnh vừa được cố định ở bước đó):

| Bước (cố định) | SS | AA | BB | CC | DD | EE | FF |
|---|---|---|---|---|---|---|---|
| Khởi tạo | 00 | ∞\infty | ∞\infty | ∞\infty | ∞\infty | ∞\infty | ∞\infty |
| Cố định S=0S=0 | 0∗0^* | 22 | 11 | 77 | ∞\infty | ∞\infty | ∞\infty |
| Cố định B=1B=1 | | 22 | 1∗1^* | 66 | ∞\infty | 1616 | 1111 |
| Cố định A=2A=2 | | 2∗2^* | | 66 | 77 | 1010 | 1111 |
| Cố định C=6C=6 | | | | 6∗6^* | 77 | 1010 | 1111 |
| Cố định D=7D=7 | | | | | 7∗7^* | 99 | 1111 |
| Cố định E=9E=9 | | | | | | 9∗9^* | 1111 |
| Cố định F=11F=11 | | | | | | | 11∗11^* |

Giải thích các lần cập nhật chính:
- Cố định BB: C=1+5=6<7C=1+5=6<7; E=1+15=16E=1+15=16; F=1+10=11F=1+10=11.
- Cố định AA: D=2+5=7D=2+5=7; E=min⁡(16, 2+8)=10E=\min(16,\,2+8)=10.
- Cố định DD: E=min⁡(10, 7+2)=9E=\min(10,\,7+2)=9.
- Cố định EE: FF qua EE là 9+6=15>119+6=15>11 nên giữ nguyên F=11F=11.

b) Kết quả — độ dài đường đi ngắn nhất từ SS và đường đi tương ứng (truy ngược theo đỉnh đã cố định):

| Đỉnh | Độ dài ngắn nhất | Đường đi |
|---|---|---|
| AA | 22 | S→AS\to A |
| BB | 11 | S→BS\to B |
| CC | 66 | S→B→CS\to B\to C |
| DD | 77 | S→A→DS\to A\to D |
| EE | 99 | S→A→D→ES\to A\to D\to E |
| FF | 1111 | S→B→FS\to B\to F |

Kiểm tra lại: S→B→C=1+5=6<SC=7S\to B\to C=1+5=6<SC=7 ✓; S→A→D→E=2+5+2=9<S→A→E=2+8=10S\to A\to D\to E=2+5+2=9<S\to A\to E=2+8=10 ✓; S→B→F=1+10=11<S→A→D→E→F=9+6=15S\to B\to F=1+10=11<S\to A\to D\to E\to F=9+6=15 ✓. Các đáp số hợp lí.

Đáp số

Đến A: độ dài 2, đường S→AĐến B: độ dài 1, đường S→BĐến C: độ dài 6, đường S→B→CĐến D: độ dài 7, đường S→A→DĐến E: độ dài 9, đường S→A→D→EĐến F: độ dài 11, đường S→B→F

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.