Giáo án điện tử chuyên đề Toán 11 chân trời Bài 3: Bài toán tìm đường đi ngắn nhất

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Í THUYẾT ĐỒ THỊ

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

NỘI DUNG BÀI HỌC 

...........................................

Thực hành 1

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

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

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

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

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

Giải:

a) Trọng số của cạnh lần lượt là .

b) Độ dài đường đi là: .

Độ dài đường đi là: .

c) Đường đi có độ dài là: .

Đường đi có độ dài là: .

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

d) Đường đi có độ dài là: .

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

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

2. THUẬT TOÁN TÌM ĐƯỜNG NGẮN NHẤT

HĐKP2

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

a) Tìm tất cả các đường đi từ A đến T (đi qua mỗi đỉnh nhiều nhất một lần) và tính độ dài của mỗi đường đi đó.

b) Từ đó, tìm đường đi ngắn nhất từ A đến T.

Giải:

a) 

có độ dài là:

có độ dài là: .

có độ dài là:

có độ dài là:

có độ dài là:

có độ dài là:

có độ dài là

b) Đường đi ngắn nhất từ đến là với độ dài bằng 11.

Nguyên lí

Tìm lần lượt các đỉnh (khác A) gần A nhất, gần A thứ hai, gần A thứ ba, … (tức là độ dài đường đi ngắn nhất từ A đến lần lượt các đỉnh bé nhất, bé thứ hai, bé thứ ba,…) cho đến khi T là một trong các đỉnh đó.

Ví dụ 3:Tìm đường đi ngắn nhất từ đỉnh P đến đỉnh Q trong đồ thị có trọng số ở Hình 12.

Giải:

Gán nhãn cho P bằng 0 (), các đỉnh khác bằng . Khoanh tròn đỉnh P.

Tại các đỉnh kề với P, gồm A, B và C, lần lượt ghi các nhãn 3, 1 và 5 (lần lượt bằng ). Trong các đỉnh khác P, đỉnh có nhãn bé nhất là B. Khoanh tròn đỉnh B (đỉnh gần đỉnh P nhất, chỉ tính các đỉnh khác đỉnh P).

Giải:

Trong các đỉnh chưa khoanh tròn, đỉnh kề với B gồm A, L và C. Tại A giữ nguyên nhãn 3, do . Tại L, ghi nhãn 16 (bằng ). Tại C, đổi nhãn 5 thành 4 (bằng ). Lúc này, trong các đỉnh chưa khoanh tròn, đỉnh A có nhãn nhỏ nhất. Khoanh tròn đỉnh A (đỉnh khác P gần đỉnh P thứ hai).

Trong các đỉnh chưa khoanh tròn, đỉnh kề với A chỉ có L. Tại L, giữ nguyên nhãn 16, do . Trong các đỉnh chưa khoanh tròn, đỉnh C có nhãn nhỏ nhất. Khoanh tròn đỉnh C (đỉnh gần đỉnh P thứ ba).

Trong các đỉnh chưa khoanh tròn, đỉnh kề với C gồm M và N. Tại M, ghi nhãn 8 (bằng ). Tại N, ghi nhãn 11 (bằng ). Trong các đỉnh chưa khoanh tròn, đỉnh M có nhãn nhỏ nhất. Khoanh tròn đỉnh M (đỉnh gần đỉnh P thứ tư).

Trong các đỉnh chưa khoanh tròn, đỉnh kề với M gồm L, N và Q. Tại L, giữ nguyên nhãn 16, do . Tại N, đổi nhãn 11 thành 10 (bằng ). Tại Q, ghi nhãn 15 (bằng ). Trong các đỉnh chưa khoanh tròn, đỉnh N có nhãn nhỏ nhất. Khoanh tròn đỉnh N (đỉnh gần đỉnh P thứ năm). 

Trong các đỉnh chưa khoanh tròn, đỉnh kề với N chỉ có Q. Tại Q, đổi nhãn 15 thành 14 (bằng ). Chỉ còn hai đỉnh L và Q chưa khoanh tròn, đỉnh Q có nhãn nhỏ hơn. Khoanh tròn đỉnh Q (đỉnh gần đỉnh P thứ sáu). 

Nhìn ngược lại các bước ở trên, ta thấy

Suy ra là đường đi ngắn nhất từ đến , với độ dài bằng 14 (xem Hình 13).

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