Đề bài

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

a) Chỉ ra trọng số của các cạnh AE, MN, CN.

b) Tính độ dài của các đường đi ABEN, EMFNE.

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

d) Đường đi EMF có phải là đường đi ngắn nhất từ E đến F không?

 

Phương pháp giải

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 của GV Loigiaihay.com

a) Ta có \({w_{AE}}\; = {\rm{ }}5;{\rm{ }}{w_{MN}}\; = {\rm{ }}1;{\rm{ }}{w_{CN}}\; = {\rm{ }}2.\)

b) Ta có:

\({l_{ABEN}}\; = {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BE}}\; + {\rm{ }}{w_{EN}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}2{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}14;\)

\({l_{EMFNE}}\; = {\rm{ }}{w_{EM}}\; + {\rm{ }}{w_{MF}}\; + {\rm{ }}{w_{FN}}\; + {\rm{ }}{w_{NE}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}6{\rm{ }} + {\rm{ }}4{\rm{ }} + {\rm{ }}9{\rm{ }} = {\rm{ }}22.\)

c) Ba đường đi khác nhau từ A đến D là: AMD, AENFD, ABNCD.

Ta có:

\({l_{AMD}}\; = {\rm{ }}{w_{AM}}\; + {\rm{ }}{w_{MD}}\; = {\rm{ }}4{\rm{ }} + {\rm{ }}5{\rm{ }} = {\rm{ }}9.\)

\({l_{AENFD}}\; = {\rm{ }}{w_{AE}}\; + {\rm{ }}{w_{EN}}\; + {\rm{ }}{w_{NF}}\; + {\rm{ }}{w_{FD}}\; = {\rm{ }}5{\rm{ }} + {\rm{ }}9{\rm{ }} + {\rm{ }}4{\rm{ }} + {\rm{ }}7{\rm{ }} = {\rm{ }}25.\)

\({l_{ABNCD}}\; = {\rm{ }}{w_{AB}}\; + {\rm{ }}{w_{BN}}\; + {\rm{ }}{w_{NC}}\; + {\rm{ }}{w_{CD}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}6{\rm{ }} + {\rm{ }}2{\rm{ }} + {\rm{ }}10{\rm{ }} = {\rm{ }}21.\)

Vậy ba đường đi khác nhau từ A đến D là AMD (có độ dài bằng 9), AENFD (có độ dài bằng 25), ABNCD (có độ dài bằng 21).

d) Ta có EMNF là một đường đi từ E đến F.

Mà \({l_{EMNF}}\; = {\rm{ }}{w_{EM}}\; + {\rm{ }}{w_{MN}}\; + {\rm{ }}{w_{NF}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}1{\rm{ }} + {\rm{ }}4{\rm{ }} = {\rm{ }}8,{\rm{ }}{l_{EMF}}\; = {\rm{ }}{w_{EM}}\; + {\rm{ }}{w_{MF}}\; = {\rm{ }}3{\rm{ }} + {\rm{ }}6{\rm{ }} = {\rm{ }}9.\)

Vì 8 < 9 nên \({l_{EMNF}}\; < {\rm{ }}{l_{EMF}}.\)

Vậy đường đi EMF không phải là đường đi ngắn nhất từ E đến F.