Giáo án điện tử chuyên đề Toán 11 kết nối Bài 10: Bài toán tìm đường đi tối ưu trong một vài trường hợp đơn giản

CHÀO MỪNG CẢ LỚP ĐẾN VỚI TIẾT HỌC HÔM NAY!

KHỞI ĐỘNG

HS nhắc lại về khái niệm đường đi Euler và Chu trình Euler? Lấy Ví dụ minh họa.

CHUYÊN ĐỀ 2: LÀM QUEN VỚI MỘT VÀI KHÁI NIỆM CỦA LÍ THUYẾT ĐỒ THỊ

BÀI 10: BÀI TOÁN TÌM ĐƯỜNG ĐI 

TỐI ƯU TRONG MỘT VÀI TRƯỜNG HỢP ĐƠN GIẢN 

NỘI DUNG BÀI HỌC 

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

HĐ

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 2 đườ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:

a) Hai đường đi từ đến , chẳng hạn là và .

Độ dài của đường đi là: 

.

Độ dài của đường đi là: 

.

Do đó, đường đi có độ dài ngắn hơn đường đi .

b) và lần lượt là các khoảng cách ngắn nhất để đi từ đến và .

Ta có .

Ghi nhớ

- Đồ thị có trọng số là một đồ thị liên thông và mỗi cạnh được gắn với một số không âm, gọi là trọng số của cạnh đó.

- Để tìm đường đi ngắn nhất từ đỉnh đến đỉnh của một đồ thị có trọng số, ta xuất phát từ đỉnh và di chuyển theo các cạnh của đồ thị.

Với mỗi đỉnh , ta gắn một số là khoảng cách ngắn nhất để đi từ đến , gọi là nhãn vĩnh viễn của đỉnh . Như vậy, để tìm độ dài của đường đi ngắn nhất nối với ta cần tìm

Ví dụ 1:Tìm độ dài của đường đi ngắn nhất nối A với F trong đồ thị có trọng số trên Hình 2.28.

Giải:

Ta áp dụng thuật toán đã mô tả ở trên.

Đầu tiên ta gắn nhãn đỉnh A là I(A) = 0 và gắn cho 2 đỉnh kề với A là B, C các nhãn tạm thời I(A) + 3 = 3, I(A) + 1 = 1. Chọn số nhỏ nhất trong chúng và viết I(C) = 1. Đỉnh C bây giờ được gắn nhãn vĩnh viễn là 1.

Tiếp theo ta gắn cho các đỉnh kề với C là B, D, E các nhãn tạm thời I(C) + 6 = 7, I(C) + 4 = 5, I(C) + 5 = 6 (B hiện nay có hai nhãn tạm thời là 3 và 7). Nhãn tạm thời nhỏ nhất trong các nhãn đã gán (ở B, D, E) hiện nay là 3 (tại B), nên ta viết I(B) = 3. Đỉnh B được gắn nhãn vĩnh viễn là 3.

Bây giờ ta xét các đỉnh kề với B (mà chưa được gắn nhãn vĩnh viễn) là D và E. Ta gắn cho đỉnh D nhãn tạm thời I(B) + 7 = 10 (D hiện nay có hai nhãn tạm thời là 5 và 10), gắn cho đỉnh E nhãn tạm thời I(B) + 2 = 5 (E có hai nhãn tạm thời là 6 và 5). 

Nhãn tạm thời nhỏ nhất bây giờ là 5 (tại D và E), do đó ta viết I(D) = 5 và I(E) = 5. Hai đỉnh D và E đều được gắn nhãn vĩnh viễn là 5.

Xét đỉnh kề với D là F, ta gắn cho F nhãn tạm thời I(D) + 9 = 14. Xét đỉnh kề với E là F, ta gắn cho F nhãn tạm thời I(E) + 8 = 13. Vậy đỉnh F sẽ được gắn nhãn vĩnh viễn là 13.Vì I(F) = 13 nên đường đi ngắn nhất từ A đến F có độ dài là 13.

Để tìm một đường đi ngắn nhất từ A đến F như vậy, ta sẽ lần ngược từ điểm cuối F. Ta chỉ cần giới hạn ở việc xét những cạnh mà độ dài là hiệu của các nhãn gắn tại các đầu mút của nó, đó là: EF, BE và AB (do I(F) - I(E) = 13 - 5 = 8, I(E) - I(B) = 5 - 3 = 2 và I(B) - I(A) = 3- 0 = 3).

Khi đó ta có thể kết luận, đường đi ngắn nhất từ A đến F phải đi qua các cạnh EF, BE và AB.

Vậy, đường đi ngắn nhất (trong trường hợp này là duy nhất) từ A đến F là 

A B E F.

Chú ý:

a) Nếu đồ thị có trọng số mà mỗi cạnh đều có trọng số là 1 thì bài toán trở thành tìm số các cạnh của đường đi ngắn nhất từ A đến F.

b) Các con số trong sơ đồ ở Hình 2.28 có thể là thời gian để đi dọc con đường đó, hoặc là chi phí khi đi hết con đường đó,... Bởi vậy, ta có thể sử dụng thuật toán giải quyết bài toán gốc về bài toán tìm đường đi ngắn nhất đề giải quyết bài toán tìm đường đi nhanh nhất hoặc đường đi có chi phí rẻ nhất,....

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

Những tình huống đơn giản liên quan đến đồ thị có trọng số, liên thông:

1) Tất cả các đỉnh của đồ thị đều có bậc chẵn.

Cách giải: Khi đó đồ thị có chu trình Euler và chu trình Euler đó chính là một đường đi yêu cầu.

2) Chỉ có đúng hai đỉnh của đồ thị có bậc lẻ.

Cách giải: Tìm đường Euler từ đỉnh bậc lẻ này đến đỉnh bậc lẻ khác, sau đó sử dụng thuật toán Mục 1 để tìm đường ngắn nhất trở về đỉnh xuất phát, kết hợp hai đường đi để có lời giải cho bài toán.

Ví dụ 2:Cho đồ thị có trọng số như Hình 2.30. Chứng tỏ rằng đồ thị có chu trình Euler và hãy tìm một chu trình Euler xuất phát từ đỉnh A.

Giải:

Vì đồ thị là liên thông và các đỉnh đều có bậc chẵn (ở đây đều là 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à ABCBECDEADA.

Chú ý: Nếu đồ thị có chu trình Euler thì độ dài quãng đường phải đi trong lời giải của bài toán người đưa thư chính là tổng các trọng số gắn trên các cạnh của đồ thị.

Ví dụ 3:Cho một đồ thị có trọng số như Hình 2.31. Tìm một chu trình xuất phát từ đỉnh A của đồ thị, có tổng trọng số nhỏ nhất và chứa mỗi cạnh ít nhất một lần.

Giải:

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

Một đường đi Euler từ A đến D là AEABEDBCD và tổng độ dài của nó là 

Để 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à DBA và có độ dài là 4 + 1 = 5.

Vậy một chu trình cần tìm là AEABEDBCDBA và có độ dài là 36 + 5 = 41.

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:

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

Một đường đi Euler từ A đến D là AFEABEDBCD và tổng độ dài của nó là

10 + 9 + 7 + 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 gắn nhãn vĩnh viễn.

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

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

LUYỆN 

           TẬP

--------------- Còn tiếp ---------------