Giải chuyên đề Toán 11 (Kết nối tri thức) Bài 10: Bài toán tìm đường tối ưu trong một vài trường hợp đơn giản

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

1. Bài toán tìm đường đi ngắn nhất

HĐ trang 46 Chuyên đề Toán 11: 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. 

Lời giải:

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

Độ dài của đường đi ABEF là AB + BE + EF = 3 + 2 + 8 = 13.

Độ dài của đường đi ACEF là AC + CE + EF = 1 + 5 + 8 = 14.

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

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

Ta có I(B) = AB = 3, I(C) = AC = 1.

2. Bài toán người đưa thư

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

Lời 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.

Bài tập

Bài 2.15 trang 49 Chuyên đề Toán 11: Tìm đường đi ngắn nhất từ A đến D trong đồ thị có trọng số trên Hình 2.33.

Lời giải:

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

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

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à C và E. Ta gắn cho đỉnh C nhãn tạm thời là I(B) + 11 (hiện C có hai nhãn tạm thời là 8 và 15), gắn cho đỉnh E nhãn tạm thời là I(B) + 9 (E hiện có hai nhãn tạm thời là 18 và 13. Nhãn tạm thời nhỏ nhất bây giờ là 8 (tại C), do đó ta viết I(C) = 8.

Bây giờ ta xét các đỉnh kề với C (mà chưa được gắn nhãn vĩnh viễn) là E và D. Ta gắn nhãn cho đỉnh E tạm thời là I(C) + 2 (hiện E có ba nhãn tạm thời là 18, 13 và 10), gắn cho đỉnh D nhãn tạm thời là I(C) + 10. Nhãn tạm thời nhỏ nhất bây giờ là 10 (tại E), do đó ta viết I(E) = 10.

Xét đỉnh kề với E là D, ta gắn cho D nhãn tạm thời I(E) + 7 (hiện D có hai nhãn tạm thời là 18 và 17). Vậy đỉnh D sẽ được gắn nhãn vĩnh viễn là 17 hay I(D) = 17.

Vì I(D) = 17 nên đường đi ngắn nhất từ A đến D có độ dài là 17.

Để tìm một đường đi ngắn nhất từ A đến D như vậy, ta sẽ lần ngược từ điểm cuối D. 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 đầu các mút của nó, đó là DE, EC, CF và FA (do I(D) – I(E) = 17 = 10 = 7, I(E) – I(C) = 10 – 8 = 2, I(C) – I(F) = 8 – 3 = 5 và I(F) – I(A) = 3 – 0 = 3).

Khi đó ta có thể kết luận, đường đi ngắn nhất từ A đến D phải đi qua các cạnh DE, EC, CF và FA.

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

A → F → C → E → D.

Bài 2.16 trang 49 Chuyên đề Toán 11: 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.

Lời giải:

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

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

Bây giờ ta xét các đỉnh kề với A 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(A) + 5 (hiện D có hai nhãn tạm thời là 13 và 7), gắn cho đỉnh E nhãn tạm thời I(A) + 8 (hiện E có hai nhãn tạm thời là 16 và 10). Nhãn tạm thời nhỏ nhất trong các nhãn đã gắn (tại D và E) là 7 (tại D), nên ta viết I(D) = 7. Đỉnh D được gắn nhãn vĩnh viễn là 7.

Ta xét đỉnh E (chưa được gắn nhãn vĩnh viễn) kề với D, ta gắn nhãn tạm thời I(D) + 2 (hiện E có ba nhãn tạm thời là 16, 10 và 9). Vậy đỉnh E sẽ được gắn nhãn vĩnh viễn là 9 hay I(E) = 9.

Tiếp tục ta xét các đỉnh kề với E mà chưa được gắn nhãn vĩnh viễn là C và F. Ta gắn cho đỉnh C nhãn tạm thời I(E) + 10 (hiện C có ba nhãn tạm thời là 7, 6 và 19), gắn cho F nhãn tạm thời I(E) + 6 (hiện F có hai nhãn tạm thời là 10 và 15). Nhãn tạm thời nhỏ nhất trong các nhãn đã gắn (ở C, F) hiện nay là 6 (tại C), nên ta viết I(C) = 6. Đỉnh C được gắn nhãn vĩnh viễn là 6.

Xét đỉnh kề với C là F, ta gắn cho F nhãn tạm thời I(C) + 14 (hiện F có ba nhãn tạm thời là 10, 15 và 20) nên I(F) = 10. Đỉnh F được gắn nhãn vĩnh viễn là 10.

Vậy, đường đi ngắn nhất từ đỉnh S đến đỉnh A là SA = 2.

Đường đi ngắn nhất từ đỉnh S đến đỉnh B là SB = 1.

Đường đi ngắn nhất từ đỉnh S đến đỉnh C có độ dài là I(C) = 6 và có đường đi là

S → B → C.

Đường đi ngắn nhất từ đỉnh S đến đỉnh D có độ dài là I(D) = 7 và đường đi là

S → A → D.

Đường đi ngắn nhất từ đỉnh S đến đỉnh E có độ dài là I(E) = 9 và đường đi là

S → A → D → E.

Đường đi ngắn nhất từ đỉnh S đến đỉnh F có độ dài là I(F) = 10 và đường đi là

S → B → F.

Bài 2.17 trang 49 Chuyên đề Toán 11: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.35.

Lời giải:

Vì đồ thị Hình 2.35 là liên thông và các đỉnh đều có bậc chẵn (ở đây chỉ có đỉnh A và đỉnh F có bậc là 2, các đỉnh còn lại đều có bậc 4) nên đồ thị này có chu trình Euler.

Một chu trình Euler xuất phát từ đỉnh A là ABCDBEDFECA và tổng độ dài của nó là

3 + 5 + 8 + 6 + 4 + 2 + 3 + 9 + 7 + 4 = 51.

Vậy một chu trình cần tìm là ABCDBEDFECA và có độ dài là 51.

Bài 2.18 trang 49 Chuyên đề Toán 11: Giải bài toán người đưa thư đối với đồ thị có trọng số trên Hình 2.36.

Lời giải:

Đồ thị Hình 2.36 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ừ đỉnh C đến đỉnh E là CABCEBDE và tổng độ dài của nó là

2 + 1 + 4 + 10 + 5 + 3 + 6 = 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 gắn nhãn vĩnh viễn.

Đườ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à CABCEBDEBAC và có độ dài là 31 + 8 = 39.