Kênh giáo viên » Giáo án powerpoint chuyên đề toán 11 chân trời sáng tạo

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

Tải giáo án điện tử Chuyên đề học tập Toán 11 chân trời sáng tạo Bài 3: Bài toán tìm đường đi ngắn nhất. Bộ giáo án chuyên đề được thiết kế sinh động, đẹp mắt. Thao tác tải về đơn giản, dễ dàng sử dụng và chỉnh sửa. Thầy, cô kéo xuống để xem chi tiết.

Xem: => Giáo án toán 11 chân trời sáng tạo

Click vào ảnh dưới đây để xem 1 phần giáo án rõ nét

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

Hướng dẫn tải giáo án

Xem toàn bộ: Giáo án điện tử chuyên đề Toán 11 chân trời sáng tạo

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:

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).