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ị (P2)

HOẠT ĐỘNG 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 liên hệ của đồ thị với khoa học tự nhiên

- GV trình chiếu Hình 26 a) và b), và chỉ cho HS thấy bằng cách vận dụng đồ thị thì các vấn đề khoa học tự nhiên sẽ được giải quyết dễ dạng hơn.

- GV cho HS quan sát Ví dụ 3 và hướng dẫn HS minh họa đồ thị của Methanol và Propane như hướng dẫn của SGK.

+ GV đặt câu hỏi:

+ Đỉnh của đồ thị là nguyên tử nào?

+ Cạnh của đồ thị là liên kết nào?

- HS thực hiện Luyện tập 3 theo nhóm đôi.

+ GV mời 5 HS lên bảng viết các đồng phân của .

+ GV đặt câu hỏi, mời 1 HS trả lời:

Các nguyên tử nào là đỉnh của đồ thị ?

Các liên kết nào là cạnh của đồ thị?

+ GV mời 5 HS khác lên biểu diễn đồ thị minh họa cho 5 đồng phân đó.

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

- HS thực hiện đọc  - hiểu Ví dụ 4 và trình bày lại đáp án vào vở.

- GV giới thiệu đồ thị minh họa Định luật Kirchhoff của cường độ dòng điện hướng vào và ra tại một nút ở Ví dụ 5

+ GV trình bày theo hướng dẫn của SGK.

Nhiệm vụ 2: Tìm hiểu liên hệ giữa đồ thị và công nghệ.

- GV giới thiệu về sự liên hệ của đồ thị với công nghệ, ví dụ với một robot tự hành chúng có thể tránh được các vật cản và tìm đường đi ngắn nhất như thế nào.

- GV có thể cho HS tìm hiểu thêm các Ví dụ khác thông qua các công cụ Internet.

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, suy nghĩ trả lời câu hỏi, hoàn thành các yêu cầu.

- GV: quan sát và trợ giúp HS.

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 và yêu cầu HS ghi chép đầy đủ vào vở.

II. Vận dụng đồ thị để giải quyết những vấn đề liên quan đến khoa học tự nhiên và công nghệ.

1. Liên hệ với khoa học tự nhiên

Đồ thị Hình 26b minh họa một phần của hệ thống điện ở Hình 26a.

Ví dụ 3: (SGK – tr.47)

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

Luyện tập 3

Minh họa bằng đồ thị

Ví dụ 4: (SGK – tr.48)

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

Ví dụ 5: (SGK – tr.48)

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

2. Liên hệ với công nghệ

- Bài toán tìm đường cho robot tự hành là tìm đường dẫn tốt nhất từ điểm bắt đầu đến điểm kết thúc trong môi trường có vật cản.

- Các tiêu chí tối ưu thường được sử dụng là ngắn nhất về mặt khoảng cách, ngắn nhất về mặt thời gian, hoặc tiêu tốn năng lượng ít nhất.

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.