1. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT

Hoạt động: Cho sơ đồ như trên Hình 2.28, ở đó A, B, C, D, E, F là các địa điểm nối với nhau bởi các con đường với độ dài của mỗi con đường được cho như trên hình.

a) Hãy chỉ ra hai đường đi từ A đến F và so sánh độ dài của hai đường đi đó.

b) Với mỗi đỉnh V của sơ đồ trên Hình 2.28, ta gắn số I(V) là khoảng cách ngắn nhất để đi từ A đến V và gọi là nhãn vĩnh viễn của đỉnh V. Như vậy, ta có ngay I(A) = 0. Dựa vào Hình 2.28, hãy tìm các nhãn vĩnh viễn I(B), I(C) của hai đỉnh kề với A là B, C.

Giải chi tiết:

a) Hai đường đi từ A đến F là: ABDF và ACEF.

Độ dài đường đi ABDF là 3 + 7 + 9 = 19; độ dài đường đi ACEF là 1 + 5 + 8 = 14. Suy ra: độ dài ABDF lớn hơn độ dài ACEF.

b) I(B) = 3; I(C) = 1.

2. BÀI TOÁN NGƯỜI ĐƯA THƯ

Luyện tập: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.32.

Giải chi tiết:

Đồ thị chỉ có 2 đỉnh bậc lẻ là A và D nên ta có thể tìm được một đường đi Euler từ đến D.

Một đường đi Euler từ A đến D là AEFABEDBCD và tổng độ dài của nó là: 7 + 9 + 10 + 2 + 8 + 16 + 15 + 3 + 4 = 74.

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ D đến A theo thuật toán đã mô tả ở Mục 1.

Đường đi ngắn nhất từ D đến A là DCBA và có độ dài là 4 + 3 + 2 = 9.

Vậy chu trình cần tìm là AEFABEDBCDCBA và có độ dài là 74 + 9 = 83.

BÀI TẬP

2.15. Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.

Giải chi tiết:

Ta có bảng sau:

Đường đi ngắn nhất từ A đến D là AFCED với độ dài 17.

2.16. Tìm đường đi ngắn nhất từ đỉnh S đến mỗi đỉnh khác của đồ thị có trọng số trên Hình 2.34.

Giải chi tiết:

Đường đi ngắn nhất từ đỉnh S đến đỉnh F: SADEF, có độ dài 15.

Đường đi ngắn nhất từ đỉnh S đến đỉnh A: SA, có độ dài 2.

Đường đi ngắn nhất từ đỉnh S đến đỉnh B: SB, có độ dài 1.

Đường đi ngắn nhất từ đỉnh S đến đỉnh C: SBC, có độ dài 6.

Đường đi ngắn nhất từ đỉnh S đến đỉnh D: SAD, có độ dài 7.

Đường đi ngắn nhất từ đỉnh S đến đỉnh E: SADE, có độ dài 9.

2.17. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.

Giải chi tiết:

Vì đồ thị liên thông và các đỉnh đều có bậc chẵn (đỉnh A, F bậc 2, đỉnh B, C, D, E bậc 4) nên đồ thị có chu trình Euler.

Một chu trình Euler xuất phát từ đỉnh A là ABDFEDCEBCA và độ dài là 51.

2.18. Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.

Giải chi tiết:

Đồ thị chỉ có hai đỉnh bậc lẻ là C và E nên ta có thể tìm được một đường đi Euler từ C đến E (đường đi này đi qua mỗi cạnh đúng một lần).

Một đường đi Euler từ C đến E là CABDEBCE và tổng độ dài của nó là: 2 + 1 + 3 + 6 + 5 + 4 + 10 = 31.

Để quay trở lại điểm xuất phát và có đường đi ngắn nhất, ta cần tìm một đường đi ngắn nhất từ E đến C theo thuật toán đã mô tả ở Mục 1.

Đường đi ngắn nhất từ E đến C là EBAC và có độ dài là 5 + 1 + 2 = 8.

Vậy một chu trình cần tìm là CABDEBCEBAC và có độ dài là 31 + 8 = 39.