Giáo án Chuyên đề 2 - Bài 9: Đường đi Euler và đường đi Hamilton - Toán 11 Bộ Sách Kết nối tri thức

 KẾ HOẠCH BÀI DẠY 2023-2024
Trường:. Họ và tên giáo viên:
Tổ: Nhóm Toán
 BÀI 9: ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON
 Môn học/Hoạt động giáo dục: Toán .; lớp: 11
 Thời gian thực hiện: (..)
I. MỤC TIÊU:
1. Kiến thức: Học xong bài này, HS đạt các yêu cầu sau:
 • Nhận biết được đường đi Euler, đường đi Hamilton
 • Vận dụng các định lý để giải thích được đâu là đường đi Euler, đường đi Hamilton.
 •Vận dụng được kiến thức vào giải quyết bài toán tính toán và bài toán thực tiễn.
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 tìm ra mối liên hệ giữa các đối tượng đã cho 
 và nội dung bài học về đường đi Euler, đường đi Hamilton, từ đó có thể áp dụng kiến thức đã học 
 để giải quyết các bài toán.
 • Mô hình hóa toán học, giải quyết vấn đề toán học thông qua các bài toán thực tiễn.
 • Giao tiếp toán học.
 • Sử dụng công cụ, phương tiện học toán.
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: Sách chuyên đề, Tài liệu giảng dạy, giáo án, đồ dùng dạy học.
2. Đối với HS: Sách chuyên đề, 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
 1. Hoạt động 1: Mở đầu
a) Mục tiêu: 
- HS bước đầu nhận biết được đường đi Euler thông qua tình huống trong đời sống.
b) Nội dung: HS nghiên cứu tình huống mở đầu, suy nghĩ trả lời câu hỏi.
 Trang | 1 KẾ HOẠCH BÀI DẠY 2023-2024
c) Sản phẩm: 
HS hình thành được kiến thức bài học, nhận biết được đường đi Euler, nắm được các định lý (điều kiện 
cần và đủ) để một đa đồ thị có chu trình 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
 Nhiệm vụ 1: nhận biết đường đi Euler HĐ1: Vẽ mội hình trên Hình 2.16 bằng 1 nét liền:
 - GV yêu cầu HS thảo luận nhóm đôi, hoàn 
 thành HĐ1.
 + Giới thiệu các hình trong HĐ1 được gọi 
 là đường đi Euler.
 + Từ đó khái quát thế nào là đường đi 
 Euler. Định nghĩa:
 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 
 đường đi Euler từ A đến B.
 Một chu trình đơn giản chứa mọi cạnh của G được 
 gọi là một chu trình Euler của G.
 - GV hướng dẫn HS làm Ví dụ 1. Ví dụ 1 (SGK – tr 41)
 Nhiệm vụ 2: Điều kiện cần và đủ để một 2. Các định lý
 đa đồ thị có chu trình Euler Định lý 1:
 Một đa đồ thị G có một chu trình Euler khi và chỉ 
 khi G liên thông và mọi đỉnh của G đều có 
 bậc chẵn.
 Định lý 2: 
 Một đa đồ thị G có một đường đi Euler từ A đến 
 B khi và chỉ khi G liên thông và mọi đỉnh 
 của G đều có bậc chẵn, chỉ trừ A và B có 
 bậc lẻ.
 Chú ý:
 Hai định lý trên cũng đúng cho trường hợp G là 
 đơn đồ thị
 Ví dụ 2 (SGK – tr 42)
 Trang | 3 KẾ HOẠCH BÀI DẠY 2023-2024
 2 Nhận biết đường đi Hamilton
a) Mục tiêu: 
- HS nhận biết và thể hiện được đường đi Hamilton.
- HS nắm được các định lý (điều kiện đủ) cho sự tổn tại của chu trình Hamilton.
b) Nội dung: HS quan sát SGK để tìm hiểu nội dung kiến thức theo yêu cầu của GV, chú ý nghe giảng, 
thực hiện các HĐ 2, đọc hiểu các Ví dụ.
c) Sản phẩm: HS hình thành được kiến thức bài học, nhận biết được đường đi Hamilton, nắm được các 
định lý (điều kiện đủ) cho sự tổn tại của chu trình Hamilton.
d) Tổ chức thực hiện:
 HOẠT ĐỘNG CỦA GV VÀ HS SẢN PHẨM DỰ KIẾN
 Bước 1: Chuyển giao nhiệm vụ: 2. Đường đi Hamilton
 Nhiệm vụ 1: Định nghĩa đường đi HĐ2: Nhận biết đường đi Hamilton
 Hamilton Giải:
 - GV yêu cầu HS thảo luận nhóm đôi, Ta có thể bắt đầu từ D →A→E→C→B hoặc
 hoàn thành HĐ2 D→A→B→C→E, ...
 Có 5 thành phố du lịch A, B,C, D, E và 
 các con đường nối thành phố này 
 như Hình 2.20. Hãy chỉ ra một 
 cách để đi tham quan cả 5 thành 
 phố đó, mà không cần đến địa 
 điểm nào quá một lần
 Định nghĩa:
 Một đường đi sơ cấp từ đỉnh A đến đỉnh B và qua 
 mọi đỉnh của đồ thị G được gọi là một 
 đường đi Hamilton từ A đến B .
 Một chu trình sơ cấp chứa mọi đỉnh của G được gọi 
 - GV cho HS đọc, nghiên cứu Ví dụ 4. là một chu trình Hamilton của G
 Ví dụ 4 (SGK – tr 43)
 Nhiệm vụ 2: Điều kiện đủ cho sự tồn tại 
 của chu trình Hamilton
 Định lí 3 (Ore)
 Nếu G là đơn đồ thị có n đỉnh n 3 và mỗi cặp 
 đỉnh không kề nhau đều có tổng bậc không 
 nhỏ hơn n thì G có một chu trình Hamilton.
 Hệ quả (Định lí Dirac). Nếu G là đơn đồ thị có n 
 đỉnh n 3 và mỗi đỉnh có bậc không nhỏ 
 n
 hơn thì G có một chu trình Hamilton.
 2
 Từ định lí Dirac ta chứng minh được:
 Định lý 4: 
 Trang | 5 KẾ HOẠCH BÀI DẠY 2023-2024
 Bước 4: Kết luận, nhận định: GV tổng đường đi Hamilton, đường đi Hamilton của 
 quát lưu ý lại kiến thức trọng tâm hình là CDAB hoặc ADBC hoặc....
 và yêu cầu HS ghi chép đầy đủ vào 
 vở.
 3. Hoạt động 3: Luyện tập
a) Mục tiêu: Học sinh củng cố lại kiến thức của bài học.
b) Nội dung: HS vận dụng các kiến thức của bài học làm Bài 2.7, 2.8 (SGK – tr44).
c) Sản phẩm học tập: 
- HS nhận biết được đường đi Euler, đường Hamilton.
- Lời giải các bài tập
Bài 2.7 (SGK – tr44).
Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler 
hoặc một chu trình Hamilton khi có thể.
Lời giải:
+) Đồ thị Hình 2.24 a) có các đỉnh đều có bậc là 3 nên theo định lí Euler 
đồ thị này không có chu trình Euler.
Lại có đồ thị a) có 4 đỉnh, tổng số bậc của hai đỉnh không kề nhau luôn 
không nhỏ hơn 4 nên theo định lí Ore, đồ thị a) có một chu trình 
Hamilton. 
Một chu trình Hamiltol của đồ thị a) là ABCDA. 
+) Đồ thị Hình 2.24 b) liên thông và có các đỉnh đều có bậc chẵn (ở đây là bậc 
4) nên theo định lí Euler, đồ thị này có một chu trình Euler. Một chu trình 
Euler của đồ thị này là ABCDEADBECA.
 Trang | 7 KẾ HOẠCH BÀI DẠY 2023-2024
 - GV tổng hợp các kiến thức cần ghi nhớ cho HS
 Chuyển giao
 - GV tổ chức cho HS hoạt động làm Bài 2.7, 2.8 (SGK – tr44).
 HS quan sát và chú ý lắng nghe, suy nghĩ, hoàn thành các bài tập GV yêu cầu.
 Thực hiện
 - GV quan sát và hỗ trợ.
 - Mỗi bài tập GV mời HS trình bày. Các HS khác chú ý chữa bài, theo dõi nhận xét 
 Báo cáo thảo luận
 bài trên bảng.
 Đánh giá, nhận - GV chữa bài, chốt đáp án, tuyên dương các hoạt động tốt, nhanh và chính xác.
 xét, tổng hợp - GV chú ý cho HS các lỗi sai hay mắc phải.
 4. Hoạt động 4: Vận dụng 
a) Mục tiêu: 
- Học sinh thực hiện làm bài tập vận dụng để nắm vững kiến thức.
b) Nội dung: HS sử dụng SGK và vận dụng kiến thức đã học để làm bài Bài 2.11 (SGK – tr45).
c) Sản phẩm: 
- HS áp dụng được các định lý để chứng minh được chu trình Hamilton.
- Dự kiến lời giải
Bài 2.11 (SGK – tr45). Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không 
 푛 푛 1
nhỏ hơn 2 trong Định lí Dirac, không thể thay bằng điều kiện "bậc của mỗi đỉnh không nhỏ hơn 2 ”
Lời giải:
Ta có ví dụ:
 푛 1
 Ta thấy bậc của mỗi đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2
Nhưng đồ thị trên có một chu trình Hamilton, ví dụ ABCFDEA. Do đó, đồ thị thỏa mãn điều kiện bậc của 
 푛
mỗi đỉnh của đồ thị G không nhỏ hơn 2.
 푛
Vậy điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn 2 trong Định lí Dirac, không thể thay bằng 
 푛 1
điều kiện "bậc của mỗi đỉnh không nhỏ hơn 2 ".
Gợi ý đáp án bài thêm:
Bài 1.
 Trang | 9