Giáo án chuyên đề Đường đi Euler và đường đi Hamilton Toán 11 Kết nối tri thức

Ngày soạn: .../.../... Ngày dạy: .../.../...
CHUYÊN ĐỀ 2: LÀM QUEN VỚI MỘT VÀI KHÁI NIỆM CỦA LÍ THUYẾT ĐỒ THỊ
BÀI 9: ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON (3 tiết) I. MỤC TIÊU:
1. Kiến thức, kĩ năng: Học xong bài này, HS đạt các yêu cầu sau:
- Nhận biết được đường đi Euler và đường đi Hamilton từ đồ thị. 2. Năng lực
Năng lực chung:
- Năng lực tự chủ và tự học trong tìm tòi khám phá
- Năng lực giao tiếp và hợp tác trong trình bày, thảo luận và làm việc nhóm
- Năng lực giải quyết vấn đề và sáng tạo trong thực hành, vận dụng.
Năng lực riêng:
- Tư duy và lập luận toán học: So sánh, phân tích dữ liệu, phân tích, lập luận
để giải thích được các Khái niệm và tính chất của đường đi Euler và đường đi Hamilton.
- Mô hình hóa toán học: mô tả các dữ kiện bài toán thực tế, giải quyết bài toán
gắn với đường đi Euler và đường đi Hamilton.
- Giải quyết vấn đề toán học: sử dụng các tính chất của đường đi Euler và
đường đi Hamilton để giải quyết các bài toán đi qua các cây cầu (mỗi cây
cầu chỉ đi 1 lần), tìm các đường Euler và Hamilton trong đồ thị hay đa đồ thị,.....
- Giao tiếp toán học: đọc, hiểu thông tin toán học. 3. Phẩm chất
- Có ý thức học tập, ý thức tìm tòi, khám phá và sáng tạo, có ý thức làm việc
nhóm, tôn trọng ý kiến các thành viên khi hợp tác.
- Chăm chỉ tích cực xây dựng bài, có trách nhiệm, chủ động chiếm lĩnh kiến
thức theo sự hướng dẫn của GV.
II. THIẾT BỊ DẠY HỌC VÀ HỌC LIỆU
1. Đối với GV: SGK, Tài liệu giảng dạy, giáo án, đồ dùng dạy học.
2. Đối với HS: SGK, SBT, vở ghi, giấy nháp, đồ dùng học tập (bút, thước...), bảng
nhóm, bút viết bảng nhóm.
III. TIẾN TRÌNH DẠY HỌC
A. HOẠT ĐỘNG KHỞI ĐỘNG (MỞ ĐẦU) a) Mục tiêu:
- Tạo hứng thú, thu hút HS tìm hiểu nội dung bài học.
b) Nội dung: HS đọc tình huống mở đầu, suy nghĩ trả lời câu hỏi.
c) Sản phẩm: HS đưa ra được nhận định ban đầu về câu hỏi mở đầu.
d) Tổ chức thực hiện:
Bước 1: Chuyển giao nhiệm vụ:
- GV yêu cầu HS đọc tình huống mở đầu:
Trong lí thuyết đồ thị, bài toán Bảy cây cầu ở Konigsberg (nay là thành phố
Kaliningrad, ngước Nga) được phát biểu như sau: Thành phố có 7 cây cầu bắc qua
sông như Hình 2.15a dưới đây; có thể nào đi dạo qua khắp các cây cầu mà mỗi cầu
chỉ đi qua một lần không?
Nếu ta coi mỗi khu vực A , B ,C , D của thành phố là một đỉnh, mỗi cầu qua lại hai
khu vực như một cạnh nối hai đỉnh, thì bản đồ thành phố Konigsberg là một đa đồ
thị như Hình 2.15b. Vấn đề đặt ra chính là: Có thể vẽ được Hình 2.15b bằng 1 nét liền hay không?
Bước 2: Thực hiện nhiệm vụ: HS quan sát và chú ý lắng nghe, thảo luận nhóm đôi hoàn thành yêu cầu.
Bước 3: Báo cáo, thảo luận: GV gọi một số HS trả lời, HS khác nhận xét, bổ sung.
Bước 4: Kết luận, nhận định: GV đánh giá kết quả của HS, trên cơ sở đó dẫn dắt
HS vào bài học mới: “Hôm nay chúng ta sẽ cùng tìm hiểu về hai khái niệm quan
trọng trong lý thuyết đồ thị: đường đi Euler và đường đi Hamilton. Đây là hai khái
niệm có nhiều ứng dụng trong thực tế, chẳng hạn như trong việc tổ chức các
chuyến tham quan, trong việc thiết kế các mạng lưới giao thông, hoặc trong việc
xây dựng các robot có thể di chuyển qua tất cả các khu vực trong một môi trường”.
Bài mới: Đường đi euler và đường đi hamilton
B. HÌNH THÀNH KIẾN THỨC MỚI
TIẾT 1: ĐƯỜNG ĐI EULER
Hoạt động 1: Đường đi Euler a) Mục tiêu:
- HS nhận biết và trình bày được khái niệm đường đi Euler và chu trình Euler.
- HS nắm được các tính chất của đường đi Euler.
- Vận dụng khái niệm và tính chất của đường đi Euler để nhận biết đồ thị có một
đường đi Euler, và giải thích có thể vẽ hình được bằng 1 nét liền,… b) Nội dung:
HS đọc SGK, nghe giảng, thực hiện các nhiệm vụ được giao, suy nghĩ trả lời câu
hỏi, thực hiện các HĐ 1, Luyện tập 1, đọc và giải thích các Ví dụ 1, 2, 3.
c) Sản phẩm: HS hình thành được kiến thức bài học, câu trả lời của HS cho các
câu hỏi. HS khái niệm đường đi Euler và chu trình Euler; tính chất của đường đi Euler.
d) Tổ chức thực hiện: HĐ CỦA GV VÀ HS
SẢN PHẨM DỰ KIẾN
Bước 1: Chuyển giao nhiệm vụ: 1. Đường đi Euler
NV1: Tìm hiểu khái niệm đường đi a) Khái niệm đường đi Euler Euler HĐ1
- GV triển khai HĐ1 cho HS quan sát - Ta có thể vẽ mỗi hình trên Hình 2.16 bằng
hình 2.16 và đọc yêu cầu của HĐ.
+ GV mời một số HS lên bảng vẽ các một nét liền. hình 2.16 bằng một nét.
+ Đối với Hình 2.16 a), ta có thể vẽ một nét
+ GV nhận xét và chốt đáp án. liền theo thứ tự 123451.
+ Đối với Hình 2.16 b), ta có thể vẽ một nét
liền theo thứ tự ABCDAEFB.
→ GV khái quát đáp án, giới thiệu cho
HS về Khái niệm đường đi Euler trong khung kiến thức SGK. Khái niệm
Cho một đa đồ thị G.
Một đường đi đơn giản từ đỉnh A đến đỉnh B
và chứa mọi cạnh của G được gọi là một
- HS thực hiện đọc – hiểu Ví dụ 1 theo đường đi Euler từ A đến B.
hướng dẫn của SGK và trình bày lại Một chu trình đơn giản chứa mọi cạnh của G cách thực hiện.
được gọi là mọt chu trình Euler của G.
- GV cho HS quan sát lại hình 2.16 a) và Ví dụ 1: (SGK – tr.41)
trả lời câu hỏi: Quan sát và nhận xét về Hướng dẫn giải (SGK – tr.41)
bậc của các đỉnh trong hình 2.16 ?
→ Từ đó GV giảng giải cho HS về Định
lí 1 của điều kiện để một đa đồ thị có Định lí 1(Euler) chu trình Euler.
Một đa đồ thị G có một chu trình Euler khi