Giáo án chuyên đề Toán 11 cánh diều CĐ 2 Bài 1: Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton (P2)

Hoạt động 2: Đường đi Euler. Đường đi Hamilton trên đồ thị

1. a) Mục tiêu:

- HS nhận biết: đường đi Euler, đường đi Hamilton.

- HS phát biểu được định lí Euler,

- HS phát biểu được định lí Dirac và định lí Ore.

- HS vận dụng khái niệm đồ thị, đường đi Euler, đường đi Hamilton, các định lí vào giải quyết vấn đề toán học.

10. b) Nội dung: HS đọc 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 hoạt động HĐ 7, 8, ví dụ, Luyện tập 7, 8, 9, 10.
11. 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 nhận biết được đường đi Euler, đường đi Hamilton, sử dụng khái niệm và định lí chứng minh các nhận định, chứng minh bài toán.
12. d) Tổ chức thực hiện:

1. HOẠT ĐỘNG LUYỆN TẬP
2. a) Mục tiêu: Học sinh củng cố lại kiến thức đã học.
3. 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 tập 1, 2, 3, 4 (SGK – tr.43).
4. c) Sản phẩm học tập: Câu trả lời của HS. HS vẽ đồ thị theo mô tả, tìm bậc của đỉnh, chỉ ra chu trình Euler, chu trình Hamilton của đồ thị.
5. d) Tổ chức thực hiện:

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

- GV tổ chức cho HS hoạt động thực hiện Bài 1, 2, 3, 4 (SGK – tr.43).

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, hoàn thành các bài tập GV yêu cầu.

- GV quan sát và hỗ trợ.

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

- 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ài trên bảng.

Bước 4: Kết luận, nhận định:

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

Kết quả:

Bài 1.

Bài 2.

1. a) Hai đỉnh bậc 1 là A và D.
2. b) Hai đỉnh bậc 2 là B và C

Hoặc cách khác:

Bài 3.

Bậc của các đỉnh :

d(A) = 4, d(B) = 2, d(C) = 4, d(F) = 2, d( E) = 4, d(D) = 2.

Chu trình Euler : ADEFCAECBA.

Bài 4.

Bậc của các đỉnh:

d(A) = 3, d(B) = 3, d(C) = 4, d(D) = 4, d( E) = 2.

Chu trình Hamilton: ADECBA.

1. HOẠT ĐỘNG VẬN DỤNG
2. 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.

1. b) Nội dung: HS sử dụng SGK và vận dụng kiến thức đã học để làm bài tập 5 (SGK – tr.43) và bài tập thêm.

Bài 1.

Trước khi vào một hội nghị, các đại biểu bắt tay nhau (hai người bắt tay nhau nhiều nhất 1 lần). Có một đại biểu không bắt tay ai hết và thấy rằng có 4 người bắt tay 4 lần, 5 người bắt tay 5 lần và 6 người bắt tay 6 lần. Nếu hội nghị có đúng 16 đại biểu thì ông ta đã đếm nhầm. Giải thích vì sao?

Bài 2.

Có 10 đội bóng thi đấu với nhau, mỗi đội phải đấu một trận với các đội khác. Chứng minh rằng vào bất cứ lúc nào cũng có hai đội đã đấu được một số trận như nhau.

1. c) Sản phẩm: Kết quả thực hiện các bài tập. HS vận dụng các khái niệm cơ bản của đồ thị vào giải quyết các bài toán thực tiễn.
2. d) Tổ chức thực hiện:

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

- GV yêu cầu HS hoạt động hoàn thành bài tập 5 (SGK – tr.43) và bài tập thêm.

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

- HS suy nghĩ, trao đổi, thảo luận thực hiện nhiệm vụ.

- GV điều hành, quan sát, hỗ trợ.

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

- Bài tập: đại diện HS trình bày kết quả, các HS khác theo dõi, đưa ý kiến.

Bước 4: Kết luận, nhận định

- GV nhận xét, đánh giá, đưa ra đáp án đúng, chú ý các lỗi sai của học sinh hay mắc phải.

Gợi ý đáp án:

Bài 5.

Vẽ một đồ thị với 6 đỉnh tương ứng với 6 người tham dự. Nếu hai người quen nhau thì nối với nhau bằng 1 đoạn thẳng nét liền giữa hai đỉnh, nếu hai người không quen nhau thì nối nét đứt.

Xét 6 điểm O, A, B, C, D, E. Lấy điểm O.

Trong 5 điểm còn lại, ta thấy 2 người bất kì hoặc quen nhau hoặc không. Theo nguyên lí Dirichlet thì tồn tại ít nhất 3 đoạn thẳng nét liền từ O đến 5 điểm A, B, C, D, E hoặc 3 đường nối nét đứt.

Xét trường hợp 3 đoạn thẳng nét liền.

Nếu trong 3 điểm A, B, C có hai điểm nối nét liền lại với nhau thì ta được 1 tam giác có đỉnh là O  Thỏa mãn bài toán (3 người đôi một quen nhau).

Nếu không có điểm nào trong 3 điểm A, B, C nối liền với nhau được thì tức là A, B, C đôi một không quen nhau  Thỏa mãn yêu cầu bài toán (3 người đôi 1 không quen nhau).

Vậy luôn tìm được 3 người đôi một quen nhau hoặc không quen nhau.

(Nguyên lí Dirichlet: Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì chắc chắn có ít nhất một ngăn có nhiều hơn một con chim.

Nếu đưa n vật thể vào m chuồng bồ câu với n > m, thì luôn có ít nhất 1 chuồng bồ câu sẽ

Đáp án bài thêm:

Bài 1.

Vẽ một đồ thị với 16 đỉnh tương ứng với 16 đại biểu tham dự hội nghị. Nếu hai đại biểu nào bắt tay nhau thì ta nối hai đỉnh tương ứng bằng một cạnh.

Theo số liệu : ta có một đồ thị có 16 đỉnh, trong đó có 1 đỉnh bậc 0, 4 đỉnh bậc 4, 5 đỉnh bậc 5 và 6 đỉnh bậc 6.

Số đỉnh bậc 5 là 5, là một số lẻ, Mâu thuẫn với hệ quả của định lí đã được học.

Vậy đại biểu đã đếm sai.

Bài 2.

Ta chuyển qua bài toán về đồ thị: Cho tương ứng mỗi đội bóng với một đỉnh của đồ thị; khi hai đội đã đấu với nhau thì ta nối hai đỉnh tương ứng bằng một cạnh; bậc của mỗi đỉnh bằng số trận mà đội tương ứng đã thi đấu. Ta phải giải bài toán sau:

Cho đồ thị với 10 đỉnh. Chứng minh rằng bao giờ cũng có hai đỉnh có cùng bậc.

Thật vậy, trong một đồ thị có 10 đỉnh, không thể có đồng thời một đỉnh (A chẳng hạn) bậc 0 và một đỉnh (B chẳng hạn) bậc 9. Bởi vì nếu B có bậc 9 thì B là đầu mút của 9 cạnh nối B với 9 đỉnh còn lại, trong đó có A, do đó A không thể có bậc 0;

Ngược lại, nếu A có bậc 0 thì B nhiều lắm cũng chỉ có bậc 8. Có 10 đỉnh, mà mỗi đỉnh chỉ có thể có một trong 9 bậc (từ 0 đến 8, hoặc từ 1 đến 9), vì vậy theo nguyên tắc Dirichlet phải có ít nhất hai đỉnh có cùng bậc (điều phải chứng minh).

* HƯỚNG DẪN VỀ NHÀ

• Ghi nhớ kiến thức trong bài.
• Hoàn thành các bài tập trong SBT
• Chuẩn bị bài mới: “Một vài ứng dụng của lí thuyết đồ thị”.