Giáo án chuyên đề Toán 11 kết nối CĐ 2 Bài 9: Đường đi Euler và đường đi Hamilton

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

NV1: Tìm hiểu khái niệm đường đi Euler

- GV triển khai HĐ1 cho HS quan sát 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 hình 2.16 bằng một nét.

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

 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.

- 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 cách thực hiện.

- GV cho HS quan sát lại hình 2.16 a) và trả lời câu hỏi: Quan sát và nhận xét về 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ó chu trình Euler.

- GV cho HS quan sát lại hình 2.16 b) và trả lời câu hỏi: Trong hình 2.16 b) có bao nhiêu đỉnh có bậc lẻ, bao nhiêu đỉnh có bậc chẵn?

 Từ đó GV trình bày cho HS về Định lí 2 của điều kiện để một đa đồ thị có chu trình Euler.

- GV lưu ý cho HS: Khi  là đơn đồ thị thì hai định lí trên cũng vẫn đúng.

- HS thực hiện Ví dụ 2 theo nhóm đôi.

+ Xác đỉnh các đỉnh và bậc của các đỉnh ở Hình a) và b) ? Áp dụng hai Định lí đã tìm hiểu để giải thích.

+ Số đỉnh có bậc lẻ ở Hình c) và d) là bao nhiêu? Có thảo mãi hai định lí đã tìm hiểu không?

 GV mời 2 HS trả lời câu hỏi và nếu đáp án cho Ví dụ.

- HS thực hiện Ví dụ 3, thảo luận theo hướng dẫn trong SGK.

• Đa đồ thị  có bao nhêu đỉnh có bậc lẻ? Bậc lẻ của các đỉnh đó là bao nhiêu?

+ GV gọi 1 HS trình bày đáp án và giải thích các bước thực hiện.

- GV cho HS thảo luận nhóm đôi thực hiện Luyện tập 1

+ Sau thảo luận, GV chỉ định 1 nhóm lên bảng trình bày bài giải.

+ HS dưới lớp nhận xét và bổ sung đáp án.

+ GV chữa bài chi tiết 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:

+ Tính chất của đường đi Euler.

+ Khái niệm đường đi Euler và chu trình Euler.

1. Đường đi Euler

a) Khái niệm đường đi Euler

HĐ1

- Ta có thể vẽ mỗi hình trên Hình 2.16 bằng một nét liền.

+ Đối với Hình 2.16 a), ta có thể vẽ một nét liền theo thứ tự .

+ Đối với Hình 2.16 b), ta có thể vẽ một nét liền theo thứ tự .

Khái niệm

Cho một đa đồ thị .

Một đường đi đơn giản từ đỉnh  đến đỉnh  và chứa mọi cạnh của  được gọi là một đường đi Euler từ  đến .

Một chu trình đơn giản chứa mọi cạnh của  được gọi là mọt chu trình Euler của .

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

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

Định lí 1(Euler)

Một đa đồ thị  có một chu trình Euler khi và chỉ khi  liên thông và mọi đỉnh của  đều có bậc chẵn.

Định lí 2

Một đa đồ thị  có một đường đi Euler từ  đến  khi và chỉ khi  liên thông và mọi đỉnh của  đều có bậc chẵn, chỉ trừ  và  có bậc lẻ.

Chú ý: Hai định lí trên cũng đúng cho trường hợp  là đơn đồ thị.

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

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

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

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

Luyện tập 1

a) Đồ thị a) liên thông, có đúng 2 đỉnh bậc lẻ là  và  nên có đường đi Euler nối  và , chẳng hạn .

b) Đồ thị b) có 4 đỉnh bậc lẻ nên không có đường đi Euler.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

- GV chia lớp thành các nhóm từ 3 – 4 HS để thực hiện HĐ2

+ Các nhóm quan sát Hình 2.20 và tìm ra tất cả các đường có thể đi qua 5 thành phố, mà mỗi thành phố chỉ đi được qua 1 lần.

+ Các nhóm cử đại diện trình bày đáp án.

+ Các nhóm khác quan sát, lắng nghe và nhận xét.

+ GV chốt đáp án.

 Từ kết quả của HDD2, GV giưới thiệu cho HS Khái niệm đường đi Hamnilton và chu trình Hamilton theo khung kiến thức SGK.

- GV mời một số HS tìm một chu trình Hamilton của hình 2.21 để thực hiện Ví dụ 4

- GV cho HS quan sát lại Hình 2.20 và 2.21 và đặt câu hỏi:

+ Xác định số đỉnh của mỗi hình 2.20 và 2.21?

+ Xác định tổng bậc của các đỉnh không kề nhau ở hình 2.20 và 2.21 ?

 GV chỉ định 2 HS trả lời câu hỏi và từ đó GV giới thiệu cho HS về Định lí 3 và 4 là điều kiện cần và đủ cho sự tồn tại của một chu trình Hamilton.

+ GV cùng giới thiệu và giảng giải cho HS Hệ quả (Định lí Dirac).

- GV gợi ý cho HS thực hiện Ví dụ 5

+ Đồ thị Hình 2.22 có bao nhiêu đỉnh, mỗi đỉnh có bao nhiêu bậc? Có thỏa mãn Định lí Dirac hay không?

+ GV mời 2 – 3 HS phát biểu kết quả của mình về một chu trình Hamilton xuất phát từ đỉnh .

- GV lưu ý cho HS về tìm đường đi Hamilton của  hoặc chứng minh  không có đường đi Hamilton.

- GV cho HS thảo luận nhóm 3, thực hiện Luyện tập 2

+ Các nhóm cần xác định: số đỉnh, bậc của đỉnh và điều này có thỏa mãn Định lí 3, 4 hay không.

+ Từ đó xác định đường đi (chu trình ) Hamilton của từng hình.

+ GV mời 2 HS lên bảng trình bày đáp án.

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

+ GV chữa bài chi tiết, chốt đáp án.

- GV chú ý thêm:

a) Đồ thị không có chu trình Hamilton. Vì: đỉnh E, D, C là bậc 2, do đó nếu tồn tại chu trình Hamilton thì nó phải đu qua các cạnh EA, EB, DA, DB, CA, CB. Điều đó mâu thuẫn do chu trình này đã qua ba cạnh của đỉnh A có bậc lớn hơn 2.

b) Theo định lí Dirac, đồ thị b) cũng có một chu trình Hamilton, ví dụ: ABDCA.

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:

+ Khái niệm đường đi Hamilton và chu trình Hamilton.

+ Tính chất của đường đi Hamilton.

2. Đường đi Hamilton

HĐ2: Nhận biết đường đi Hamilton

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 là ta có thể đi theo thứ tự  (hoặc có thể chọn , hoặc ,...).

Khái niệm

Một đường đi sơ cấp từ đỉnh  đến đỉnh  và qua mọi đỉnh của đồ thị  được gọi là một đường đi Hamilton từ  đến .

Một chu trình sơ cấp chứa mọi đỉnh của  được gọi là một chu trình Hamilton của .

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

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

Định lí 3 (Ore)

Nếu  là đơn đồ thị có  đỉnh  và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn  thì  có một chu trình Hamilton.

Hệ quả (Định lí Dirac): Nếu  là đơn đồ thị có  đỉnh  và mỗi đỉnh có bậc nhỏ hơn  thì  có một chu trình Hamilton.

Định lí 4:

Nếu đơn đồ thị  có  đỉnh  và mỗi đỉnh có bậc không nhỏ hơn  thì  có một đường đi Hamilton.

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

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

Chú ý

Đường đi (chu trình) Hamilton phải đi qua các cạnh có đầu mút tại những đỉnh có bậc 2 (nếu những đỉnh này không phải là đầu đường hoặc cuối đường).

Luyện tập 2

a) Đồ thị a) có 5 đỉnh và mỗi đỉnh có bậc không nhỏ hơn 2 nên theo định lí 4, đồ thị có đường Hamilton, ví dụ: .

b) Đồ thị b) có 4 đỉnh, trong đó các đỉnh có bậc là 3. Do đó b) thỏa mãn điều kiện của Định lí 4, tức là có một đường đi Hamilton, ví dụ: