Đề 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?

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.