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

Giải Bài 2.15 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ừ AA đến DD trong đồ thị có trọng số trên Hình 2.33.

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.33: Đồ 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 = 4; A–F = 3; B–C = 11; B–F = 6; B–D (cung cong phía trên) = 20; B–E = 5; C–F = 2; C–E = 10; C–D = 10; F–E = 15; E–B... (cạnh chéo) ; E–D = 7; F–C = 9. Cụ thể các số ghi trên hình: A–B = 4, A–F = 3, B–F = 6, B–C = 11, cung cong A–D = 20, đường chéo B–E = 5, đường chéo C–F = 9, C–E = 2, C–D = 10, F–E = 15, E–D = 7.

Lời giải

Phân tích bài toán. Đồ thị có trọng số gồm 6 đỉnh với các cạnh (lấy theo số ghi trên Hình 2.33):

A ⁣− ⁣B=4,  A ⁣− ⁣F=3,  A ⁣− ⁣D=20,  B ⁣− ⁣C=11,  B ⁣− ⁣F=6,  B ⁣− ⁣E=5,A\!-\!B=4,\; A\!-\!F=3,\; A\!-\!D=20,\; B\!-\!C=11,\; B\!-\!F=6,\; B\!-\!E=5,
C ⁣− ⁣F=9,  C ⁣− ⁣E=2,  C ⁣− ⁣D=10,  E ⁣− ⁣D=7,  F ⁣− ⁣E=15.C\!-\!F=9,\; C\!-\!E=2,\; C\!-\!D=10,\; E\!-\!D=7,\; F\!-\!E=15.

Ta dùng thuật toán gán nhãn (Dijkstra) để tìm đường đi ngắn nhất từ AA đến DD. Mỗi đỉnh được gán một nhãn là độ dài ngắn nhất tạm thời từ AA tới nó; ở mỗi bước ta chọn đỉnh có nhãn tạm nhỏ nhất để cố định (nhãn chính thức), rồi cập nhật nhãn các đỉnh kề.

Bước 0. Gán nhãn chính thức cho AA: d(A)=0d(A)=0. Các đỉnh khác nhãn tạm =+∞=+\infty.

Bước 1. Từ AA cập nhật các đỉnh kề:
d(B)=4 (A),d(F)=3 (A),d(D)=20 (A).d(B)=4\,(A),\quad d(F)=3\,(A),\quad d(D)=20\,(A).
Nhãn tạm nhỏ nhất là d(F)=3d(F)=3 → cố định FF.

Bước 2. Từ F (=3)F\,(=3) cập nhật: d(C)=3+9=12 (F)d(C)=3+9=12\,(F); d(E)=3+15=18 (F)d(E)=3+15=18\,(F); với BB: 3+6=9>43+6=9>4 nên giữ d(B)=4d(B)=4.
Hiện có d(B)=4, d(C)=12, d(E)=18, d(D)=20d(B)=4,\,d(C)=12,\,d(E)=18,\,d(D)=20. Nhỏ nhất là d(B)=4d(B)=4 → cố định BB.

Bước 3. Từ B (=4)B\,(=4) cập nhật: d(E)=min⁡(18, 4+5)=9 (B)d(E)=\min(18,\,4+5)=9\,(B); với CC: 4+11=15>124+11=15>12 nên giữ d(C)=12d(C)=12.
Hiện d(E)=9, d(C)=12, d(D)=20d(E)=9,\,d(C)=12,\,d(D)=20. Nhỏ nhất là d(E)=9d(E)=9 → cố định EE.

Bước 4. Từ E (=9)E\,(=9) cập nhật: d(C)=min⁡(12, 9+2)=11 (E)d(C)=\min(12,\,9+2)=11\,(E); d(D)=min⁡(20, 9+7)=16 (E)d(D)=\min(20,\,9+7)=16\,(E).
Hiện d(C)=11, d(D)=16d(C)=11,\,d(D)=16. Nhỏ nhất là d(C)=11d(C)=11 → cố định CC.

Bước 5. Từ C (=11)C\,(=11) cập nhật DD: 11+10=21>1611+10=21>16 nên giữ d(D)=16d(D)=16. Còn lại chỉ có DD, cố định DD với d(D)=16d(D)=16.

Truy vết đường đi. DD lấy nhãn từ EE, EE lấy nhãn từ BB, BB lấy nhãn từ AA. Vậy đường đi ngắn nhất là:
A  →4  B  →5  E  →7  D,A\;\xrightarrow{4}\;B\;\xrightarrow{5}\;E\;\xrightarrow{7}\;D,
với độ dài 4+5+7=164+5+7=16.

Kiểm tra lại. So với vài đường khác: A ⁣− ⁣F ⁣− ⁣C ⁣− ⁣E ⁣− ⁣D=3+9+2+7=21A\!-\!F\!-\!C\!-\!E\!-\!D=3+9+2+7=21; A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣C ⁣− ⁣D=4+5+2+10=21A\!-\!B\!-\!E\!-\!C\!-\!D=4+5+2+10=21; A ⁣− ⁣D=20A\!-\!D=20 (cung cong trực tiếp). Tất cả đều lớn hơn 1616. Vậy A ⁣− ⁣B ⁣− ⁣E ⁣− ⁣DA\!-\!B\!-\!E\!-\!D là đường đi ngắn nhất.

Kết luận. Đường đi ngắn nhất từ AA đến DD là A→B→E→DA\to B\to E\to D, độ dài bằng 1616.

Đáp số

Đường đi ngắn nhất: A→B→E→DA\to B\to E\to D, độ dài 1616

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.