Giải bài 5 trang 67 Chuyên đề học tập Toán 11 Chân trời sáng tạo

Đề bài

Cho đồ thị có trọng số như Hình 4. Đường đi ngắn nhất từ A đến C là

A. AEC.

B. AEFC.

C. AC.

D. AFC.

Lời giải chi tiết

Đáp án đúng là: B

– Gán nhãn cho A bằng 0 (tức là, n_A = 0), các đỉnh khác bằng ∞. Khoanh tròn đỉnh A.

– Tại các đỉnh kề với A, gồm E, F, B, ta có:

⦁ \({n_E}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AE}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}2{\rm{ }} = {\rm{ }}2\).Vì \(2{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của E thành 2.

⦁ \({n_F}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AF}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}4{\rm{ }} = {\rm{ }}4\).Vì \(4{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của F thành 4.

⦁ \({n_B}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AB}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}2,5{\rm{ }} = {\rm{ }}2,5\).Vì \(2,5{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của B thành 2,5.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là E nên ta khoanh tròn đỉnh E (đỉnh gần A nhất, chỉ tính các đỉnh khác A).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh E gồm D, C, F, ta có:

⦁ \({n_D}\; = {\rm{ }}{n_E}\; + {\rm{ }}{w_{ED}}\; = {\rm{ }}2{\rm{ }} + {\rm{ }}3{\rm{ }} = {\rm{ }}5\).Vì \(5{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của D thành 5.

⦁ \({n_C}\; = {\rm{ }}{n_E}\; + {\rm{ }}{w_{EC}}\; = {\rm{ }}2{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}7\).Vì \(7{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của C thành 7.

⦁ \({n_F}\; = {\rm{ }}{n_E}\; + {\rm{ }}{w_{EF}}\; = {\rm{ }}2{\rm{ }} + {\rm{ }}1{\rm{ }} = {\rm{ }}3\).Vì \(3{\rm{ }} < {\rm{ }}4\) (4 là nhãn hiện tại của F) nên ta đổi nhãn của F thành 3.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là B nên ta khoanh tròn đỉnh B (đỉnh gần A thứ hai).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh B chỉ có F, ta có:

\({n_F}\; = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BF}}\; = {\rm{ }}2,5{\rm{ }} + {\rm{ }}1,5{\rm{ }} = {\rm{ }}4\).Vì \(4{\rm{ }} > {\rm{ }}3\) (3 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 3.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là F nên ta khoanh tròn đỉnh F (đỉnh gần A thứ ba).

– Trong các đỉnh chưa được khoanh tròn, đỉnh kề với đỉnh F chỉ có C, ta có:

\({n_C}\; = {\rm{ }}{n_F}\; + {\rm{ }}{w_{FC}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}2{\rm{ }} = {\rm{ }}5\).Vì \(5{\rm{ }} < {\rm{ }}7\) (7 là nhãn hiện tại của C) nên ta đổi nhãn của C thành 5.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là C, D (đều có nhãn là 5), nhưng do ta cần tìm đường đi ngắn nhất từ A đến C nên ta ưu tiên khoanh tròn đỉnh C (đỉnh gần A thứ tư).

– Nhìn lại các bước trên, ta thấy:

\(\begin{array}{*{20}{l}}{{n_C}\; = {\rm{ }}5{\rm{ }} = {\rm{ }}{n_F}\; + {\rm{ }}{w_{FC}}}\\{ = {\rm{ }}{n_E}\; + {\rm{ }}{w_{EF}}\; + {\rm{ }}{w_{FC}}}\\{ = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AE}}\; + {\rm{ }}{w_{EF}}\; + {\rm{ }}{w_{FC}}}\\{ = {\rm{ }}{w_{AE}}\; + {\rm{ }}{w_{EF}}\; + {\rm{ }}{w_{FC}}}\\{ = {\rm{ }}{l_{AEFC}}.}\end{array}\)

Vậy AEFC là đường đi ngắn nhất từ A đến C, với độ dài bằng 5.

Do đó ta chọn phương án B.