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

Đề bài

Tìm đường đi ngắn nhất từ đỉnh M đến N trong đồ thị có trọng số sau:

Lời giải chi tiết

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

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

⦁ \({n_A}\; = {\rm{ }}{n_M}\; + {\rm{ }}{w_{MA}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}3{\rm{ }} = {\rm{ }}3\).Vì \(3{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của A thành 3.

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

⦁ \({n_C}\; = {\rm{ }}{n_M}\; + {\rm{ }}{w_{MC}}\; = {\rm{ }}0{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}5\).Vì \(5{\rm{ }} < {\rm{ }}\infty \) 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à A nên ta khoanh tròn đỉnh A (đỉnh gần M nhất, chỉ tính các điểm khác M).

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

\({n_D}\; = {\rm{ }}{n_A}\; + {\rm{ }}{w_{AD}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}8{\rm{ }} = {\rm{ }}11\).Vì \(11{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của D thành 11.

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

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 M thứ hai).

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

⦁ \({n_D}\; = {\rm{ }}{n_B}\; + {\rm{ }}{w_{BD}}\; = {\rm{ }}4{\rm{ }} + {\rm{ }}8{\rm{ }} = {\rm{ }}12\).Vì 12 > 11 (11 là nhãn hiện tại của D) nên ta giữ nguyên nhãn của D là 11.

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

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

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

⦁ \({n_E}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CE}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}6{\rm{ }} = {\rm{ }}11\).Vì \(11{\rm{ }} < {\rm{ }}13\) (13 là nhãn hiện tại của E) nên ta đổi nhãn của E thành 11.

⦁ \({n_F}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CF}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}8{\rm{ }} = {\rm{ }}13\).Vì \(13{\rm{ }} > {\rm{ }}10\) (10 là nhãn hiện tại của F) nên ta giữ nguyên nhãn của F là 10.

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 M thứ tư).

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

\({n_N}\; = {\rm{ }}{n_F}\; + {\rm{ }}{w_{FN}}\; = {\rm{ }}10{\rm{ }} + {\rm{ }}12{\rm{ }} = {\rm{ }}22\).Vì \(22{\rm{ }} < {\rm{ }}\infty \) nên ta đổi nhãn của N thành 22.

rong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là D, E nên ta tùy ý khoanh tròn đỉnh E (đỉnh gần M thứ năm).

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

\({n_N}\; = {\rm{ }}{n_E}\; + {\rm{ }}{w_{EN}}\; = {\rm{ }}11{\rm{ }} + {\rm{ }}7{\rm{ }} = {\rm{ }}18\).Vì \(18{\rm{ }} < {\rm{ }}22\) (22 là nhãn hiện tại của N) nên ta đổi nhãn của N thành 18.

Trong các đỉnh chưa được khoanh tròn, đỉnh có nhãn bé nhất là D nên ta tùy ý khoanh tròn đỉnh D (đỉnh gần M thứ sáu).

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

\({n_N}\; = {\rm{ }}{n_D}\; + {\rm{ }}{w_{DN}}\; = {\rm{ }}11{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}20\).Vì \(20{\rm{ }} > {\rm{ }}18\) (18 là nhãn hiện tại của N) nên ta giữ nguyên nhãn của N là 18.

Lúc này, ta thấy chỉ còn đỉnh N chưa được khoanh tròn nên ta khoanh tròn đỉnh N (đỉnh gần M thứ bảy).

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

\(\begin{array}{*{20}{l}}{{n_N}\; = {\rm{ }}18{\rm{ }} = {\rm{ }}{n_E}\; + {\rm{ }}{w_{EN}}\; = {\rm{ }}{n_C}\; + {\rm{ }}{w_{CE}}\; + {\rm{ }}{w_{EN}}\; = {\rm{ }}{n_M}\; + {\rm{ }}{w_{MC}}\; + {\rm{ }}{w_{CE}}\; + {\rm{ }}{w_{EN}}}\\{ = {\rm{ }}{w_{MC}}\; + {\rm{ }}{w_{CE}}\; + {\rm{ }}{w_{EN}}\; = {\rm{ }}{l_{MCEN}}.}\end{array}\)

Vậy MCEN là đường đi ngắn nhất từ đỉnh M đến N, với độ dài bằng 18.