Chuyên đề Toán 11 KNTT 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 có đáp án

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.

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.

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.

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.