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

Cho đồ thị có trọng số như Hình 16.

Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo

Toán - Văn - Anh - Lí - Hóa - Sinh

Đề bài

Cho đồ thị có trọng số như Hình 16.

a) Tính độ dài các đường đi ABCD, MBNCP.

b) Chỉ ra ba đường đi khác nhau từ M đến N và tính độ dài của chúng.

c) MBC có phải là đường đi ngắn nhất từ M đến C không?

Phương pháp giải - Xem chi tiết

Nếu mỗi cạnh của đồ thị G được gắn với một số thực (có thể là độ dài của đường đi trên mỗi cạnh, chi phí vận chuyển trên mỗi cạnh đó,…) thì đồ thị G được gọi là đồ thị có trọng số. Trọng số của cạnh a kí hiệu là \({w_a}\)

Tổng trọng số (hay độ dài) của các cạnh tạo thành đường đi gọi là độ dài của đường đi đó. Độ dài đường đi m kí hiệu là \({l_m}\). Đường đi có độ dài ngắn nhất trong các đường đi từ đỉnh A đến đỉnh B gọi là đường đi ngắn nhất từ A đến B.

Lời giải chi tiết

a) Ta có:

\(\begin{array}{*{20}{l}}{{l_{ABCD}}\; = {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BC}}\; + {\rm{ }}{w_{CD}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}15{\rm{ }} + {\rm{ }}4{\rm{ }} = {\rm{ }}24.}\\{{l_{MBNCP}}\; = {\rm{ }}{w_{MB}}\; + {\rm{ }}{w_{BN}}\; + {\rm{ }}{w_{NC}}\; + {\rm{ }}{w_{CP}}\; = {\rm{ }}7{\rm{ }} + {\rm{ }}7{\rm{ }} + {\rm{ }}6{\rm{ }} + {\rm{ }}25{\rm{ }} = {\rm{ }}45.}\end{array}\)

Vậy độ dài các đường đi ABCD, MBNCP lần lượt là 24 và 45.

b) Ba đường đi khác nhau từ M đến N là: MAN, MBN, MABN.

Ta có:

\(\begin{array}{*{20}{l}}{{l_{MAN}}\; = {\rm{ }}{w_{MA}}\; + {\rm{ }}{w_{AN}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}14.}\\{{l_{MBN}}\; = {\rm{ }}{w_{MB}}\; + {\rm{ }}{w_{BN}}\; = {\rm{ }}7{\rm{ }} + {\rm{ }}7{\rm{ }} = {\rm{ }}14.}\\{{l_{MABN}}\; = {\rm{ }}{w_{MA}}\; + {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BN}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}5{\rm{ }} + {\rm{ }}7{\rm{ }} = {\rm{ }}17.}\end{array}\)

Vậy ba đường đi khác nhau từ M đến N là MAN, MBN, MABN có độ dài lần lượt bằng 14; 14; 17.

c) Ta có MANC là một đường đi từ M đến C.

M \({l_{MANC}}\; = {\rm{ }}{w_{MA}}\; + {\rm{ }}{w_{AN}}\; + {\rm{ }}{w_{NC}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}9{\rm{ }} + {\rm{ }}6{\rm{ }} = {\rm{ }}20,{\rm{ }}{l_{MBC}}\; = {\rm{ }}{w_{MB}}\; + {\rm{ }}{w_{BC}}\; = {\rm{ }}7{\rm{ }} + {\rm{ }}15{\rm{ }} = {\rm{ }}22.\)

Vì 20 < 22 nên \({l_{MANC}}\; < {\rm{ }}{l_{MBC}}.\)

Vậy MBC không phải là đường đi ngắn nhất từ M đến C.