Giáo án chuyên đề Toán 11 cánh diều CĐ 2 Bài 2: Một vài ứng dụng của lí thuyết đồ thị (P1)

Lí thuyết đồ thị có thể giải quyết những vấn đề thực tiễn nào?

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: Chuyển giao nhiệm vụ:

Nhiệm vụ 1: Tìm hiểu đồ thị có trọng số

- GV triển khai HĐ1, cho HS thực hiện nhóm đôi thực hiện yêu cầu.

+ GV chỉ định 1 HS nhắc lại khái niệm đồ thị đã học ở bà trước.

+ GV mời 2 HS lên bảng vẽ đồ thị mô tả tình huống.

+ HS dưới lớp nhận xét bài làm của bạn.

 GV dẫn dắt: Những đồ thị mà mỗi cạnh có gắn với số thực như hình 22 được gọi là đồ thị có trọng số.

+ GV mời 1 HS đọc phần Định nghĩa trong SGK.

- HS thực hiện đọc – hiểu Ví dụ 1 theo hướng dẫn của SGk và trình bày lại đáp án.

- GV cho HS suy nghĩ thực hiện Luyện tập 1 theo từng bàn.

+ GV chỉ định 2 HS lên bảng thực hiện yêu cầu.

+ GV nhận xét và chốt đáp án cho HS.

Nhiện vụ 2: Tìm hiểu thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số.

- GV triển khai HĐ2 cho HS đọc yêu cầu của HĐ và quan sát Hình 24.

+ GV có thể phân tích và gợi ý:

• Vì mỗi đoạn nối 2 điểm trên đồ thị sẽ có một độ dài riêng nên ta có thể xét điểm xuất phát là điểm .

• Từ điểm  đi đến điểm nào là ngắn nhất? Cứ liên tiếp tương tự như vậy ta sẽ tìm được đường đi thỏa mãn yêu cầu đề bài.

+ GV chỉ định 1 HS đứng tai chỗ trình bày đáp án. HS khác nhận xét.

 GV chốt đáp án và trình bày ngắn gọn phần Nhận xét cho HS nắm được phương pháp giải các kiểu bài toán như HĐ2.

- GV giảng giải cho HS cách xây dựng một thuật toán láng giềng gần nhất thì trước hết cần chứng minh đồ thị có chu trình Hamilton.

+ GV chỉ định 2 HS nhắc lại về chu trình Hamilton và các định lí của nó.

- GV lưu ý cách tìm chu trình “tốt nhất” thông qua thuật toán láng riềng gần nhất cho HS.

- GV cho HS thực hiện Ví dụ 2 theo hướng dẫn của SGK.

+ Trình bày các chu trình xuất phát từ các đỉnh trong Hình 25?

+ Những đường đi nào là ngắn nhất?

- GV triển khai Luyện tập 2 cho HS thảo luận nhóm 3 thực hiện yêu cầu.

+ GV mời 1 HS đứng tại chỗ chứng minh Hình 24 có chu trình Hamilton.

+ Các nhóm vận dụng phương pháp đã thực hiện trong Ví dụ 2 để thực hiện.

+ GV chỉ định 2 HS lên bảng thực hiện bài giải.

+ GV chữa bài chi tiết cho HS và rút ra kinh nghiệm làm vài cho HS.

Bước 2: Thực hiện nhiệm vụ:

- HS theo dõi SGK, chú ý nghe, tiếp nhận kiến thức, hoàn thành các yêu cầu, thảo luận nhóm.

- GV quan sát hỗ trợ.

Bước 3: Báo cáo, thảo luận:

- HS giơ tay phát biểu, lên bảng trình bày

- Một số HS khác nhận xét, bổ sung cho bạn.

Bước 4: Kết luận, nhận định: GV tổng quát lưu ý lại kiến thức trọng tâm:

+ Khái niệm đồ thị có trọng số.

+ Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số.

+ Các bước chứng minh đồ thị có chu trình Hamilton.

I. Vận dụng đồ thị để giải quyết những vấn đề về tìm đường đi ngắn nhất trong những trường hợp đơn giản

1. Đồ thị có trọng số

HĐ1

Đồ thị mô tả tình huống:

Định nghĩa

Nếu mỗi cạnh của đồ thị  được gắn với một số thực (có thể là độ dài của đường đi trên mỗi cạnh, hay chi phí vận chuyển trên mỗi cạnh đó,…) thì đồ thị  được gọi là đồ thị có trọng số.

Ví dụ 1: (SGK – tr.44)

Hướng dẫn giải (SGK – tr.44)

Luyện tập 1

Có 4 trạm xe bus  được nối với nhau theo những con đường  với độ dài lần lượt là . Ta có đồ thị mô tả tình huống trên như sau.

Mô tả:

2. Thuật toán tìm đường đi ngắn nhất trên đồ thị có trọng số

HĐ2

Đường đi ngắn nhất và thỏa mãn yêu cầu đề bài:  với tổng quãng đường đi là .

Nhận xét

- Những bài toán như HĐ2 được gọi là bài toán về tìm đường có trọng số.

- Người ta sử dụng thuật toán Láng giềng gần nhất và thuật toán các nhà tóa học Dijkstra, Whiting và Hillier.

Các bước thực hiện xây dựng thuật toán

+ Bước 1. Chọn một đỉnh bắt đầu, ta gọi là đỉnh .

+ Bước 2. Xuất phát từ đỉnh hiện hành, chọn cạnh có độ dài nhỏ nhất nối đến một trong các đỉnh của đến. Đánh dầu đỉnh cuối của cạnh vừa chọn.

+ Bước 3. Xuất phát từ đỉnh vừa đánh dấu, nếu còn đỉnh chưa đến thì quay lại Bước 2.

+ Bước 4. Quay lại đỉnh .

Chú ý

Để tìm đường đi ngắn nhất trên đồ thị có trọng số, ta áp dụng thuật toán láng riềng gần nhất để tìm tất cả các chu trình xuất pát từ 1 đỉnh ban đầu.

Sau đó so sánh độ dài của các chu trình để tìm ra chu trình “tốt nhất” thỏa mãn yêu cầu đề bài.

Ví dụ 2: (SGK – tr.46)

Hướng dẫn giải (SGK – tr.46+47)

Luyện tập 2

Ta thấy đồ thị hình 24 có chu trình Hamilton. Áp dụng thuật toán láng giềng gần nhất

Từ  đỉnh gần nhất là .

Từ , đỉnh chưa đến gần nhất là

Từ , đỉnh chưa đến gần nhất là ;

Từ , đỉnh chưa đến gần nhất là  ;

Từ , đỉnh chưa đến gần nhất là ;

Đến đây không còn đỉnh chưa đến, vì vậy quay về .

Tổng quãng đường theo chu trình  là:

* Tương tự với các đỉnh khác, ta có bảng sau:

=> Vậy người giao hàng chọn 1 đường đi trong 7 đường đi trên thì quãng đường phải di chuyển là ngắn nhất.