Tả1 bản chuẩn giáo án chuyên đề Toán 11 CTST CĐ 2 bài 2: Đường đi Euler và đường đi Hamilton (P1)

HĐ CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

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

- GV triển khai HĐKP1 cho HS quan sát Hình 1, Hình 2 và đọc các yêu cầu.

a) HS thực hiện thảo luận với bạn cùng bàn.

+ GV mời 2 – 3 HS thử vẽ và đưa ra dự đoán kết quả của mình.

b) GV vẽ hình và đặt tên các mỗi cạnh như hình vẽ bên.

+ GV cho HS thảo luận và chỉ định 2 – 3 HS lên bảng thử vẽ và nêu kết luận.

+ GV chốt đáp án cho HS.

 GV khái quát giới thiệu cho HS biết khái niệm đường đi từ đỉnh này đến đỉnh kia và một đường đi gọi là một chu trình của một đồ thị .

- GV cho HS thực hiện Ví dụ 1

+ GV mời 3 HS trả lời câu a) và 3 HS khác trả lời câu b).

- GV đặt câu hỏi: Trong đồ thị Hình 3, có cặp đỉnh nào mà không có đường đi đến nhau hay không?

 GV trình bày, giảng giải cho HS về một đồ thị được gọi là liên thông theo Khung kiến thức SGK.

- HS quan sát Hình 4 và thực hiện Ví dụ 2

+ GV chỉ đỉnh 1 HS đứng tại chỗ nhận xét đồ thị  và 1 HS nhận xét đồ thị  có liên thông không ?

- GV cho HS quan sát lại Đồ thị  (Hình 2) và dẫn dắt: Ở đồ thị  (hình 2) ta thấy có thể vẽ được bằng 1 nét mà đi qua hết các cạnh của đồ thị, với mỗi cạnh chỉ đi qua 1 lần. Cách vẽ đó chính là một đường đi Euler.

 GV trình chiếu hoặc ghi bảng Khái niệm đường đi Euler cho HS.

- GV lưu ý cho HS thấy khi đồ thị liên thông thì mọi đường đi Euler sẽ đi qua mọi đỉnh của đồ thị.

- GV triển khai HĐKP2 cho HS thực hiện thảo luận nhóm đôi và hoàn thiện HĐ.

a) GV mời 1 – 2 HS lên bảng viết ra chu trình Euler cho đồ thị .

+ HS đó nhận xét về bậc của các đỉnh của đồ thị .

b) GV mời 2 HS nhắc lại về Khái niệm chu trình Euler ? và lên bảng chứng minh rằng Đồ thị  và  không có chu trình Euler.

+ Ở đồ thị , để đi qua tất cả các cạnh thì  phải đi qua cạnh  mấy lần?

+ Ở đồ thị , để đi qua tất cả các cạnh thì phải đi qua đỉnh  mấy lần?

+ Đồ thị  và  có chu trình Euler hay không?

+ HS nhận xét về số đỉnh có bậc lẻ của mỗi đồ thị.

 Từ kết quả của HĐ, GV nhận xét và dẫn: Ta thấy đồ thị  có chu trình Euler và các đỉnh của đồ thị này đều chẵn; hai đồ thị  và  có đỉnh bậc lẻ và chúng không có chu trình Euler. Vậy điều kiện để một đồ thị có chu trình Euler là gì?

 GV giới thiệu Định lí 1 theo SGK cho HS

- HS thực hiện Ví dụ 3 và chỉ ra đồ thị nào có chu trình Euler và giải thích.

+ GV mời 1 HS đứng tại chỗ trình bày và giải thích lại cách thực hiện.

- GV triển khai HĐKP3 cho HS thảo luận nhóm 3 và tìm các đường đi Euler trong hai đồ thị Hình 9

+ GV chỉ định 1 – 2 nhóm nêu đáp án của mình.

+ Các HS khác lắng nghe và nhận xét câu trả lời của bạn

+ GV mời 1 HS đứng tại chỗ xác định số bậc lẻ của mỗi đồ thị.

 GV khái quát kết quả của HĐ và trình bày Định lí 2 về điều kiện để đồ thị có đường đi Euler nhưng không có chu trình Euler.

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

- GV hướng dẫn cho HS thực hiện Ví dụ 5

+ GV vẽ biểu thị lại cây cầu Hình 11 thành Hình 12 cho HS quan sát.

+ GV hỏi: Các đỉnh của đồ thị có bậc chẵn hay lẻ ? Vậy nó có chu trình Euler không?

+ GV vẽ một chu trình Euler cho HS quan sát và mời 2 – 3 HS lên bảng tìm thêm về chu trình Euler khác.

- GV triển khai HĐTH1 cho HS thảo luận nhóm đôi theo bàn để hoàn thành đáp án.

+ GV chỉ định 1 HS đứng tại chỗ nhắc lại điều kiện để một đồ thị có chu trình Euler là gì?

+ GV chỉ định 2 HS lên bảng thực hiện xác định chu trình Euler cho mỗi đồ thị.

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

+ GV chốt đáp án.

- HS thực hiện độc lập HĐTH2

+ GV mời 1 HS nhắc lại khi nào thì một đồ thị có đường đi Euler ?

+ GV mời 1 HS khác lên bảng thực hiện yêu cầu của bài toán.

+ GV chỉ định 2 – 3 HS khác tìm các đường đi Euler khác.

- GV cho HS đọc yêu cầu của HĐVD1

+ Hình 1 có đỉnh nào có bậc lẻ hay không? Là những đỉnh nào?

+ Từ đó giải đáp câu hỏi của người dân

+ GV chỉ định 1 HS nêu câu trả lời.

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 đường đi và chu trình Euler. + Tính chất và định lí của đường đi Euler.

1. Đường đi Euler

HĐKP 1

a) - Thử vẽ nhiều lần, không tìm ra cách vẽ như vậy

- Dự đoán: Không tồn tại cách vẽ như vậy.

b) Ta có thể vẽ một nét liền đi qua tất cả các cạnh của đồ thị này, mỗi cạnh đúng một lần bằng cách lần lượt vẽ các cạnh

Khái niệm

Trong đồ thị , một dãy cạnh nối tiếp (hai cạnh nối tiếp là hai cạnh có chung một đỉnh)  được gọi là một đường đi từ đỉnh  đến đỉnh , kí hiệu .

Ta cũng nói đường đi  bắt đầu từ đỉnh , đi qua các cạnh  và kết thức tại đỉnh

Một đường đi được gọi là một chu trình nếu nó bắt đầu (hoặc xuất phát) và kết thức tại cùng một đỉnh.

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

Hướng dẫn giải (SGk – tr.50)

Khái niệm

Một đồ thị được gọi là liên thông nếu mọi cặp đỉnh phân biệt của nó đều có đường đi từ đỉnh này đến đỉnh kia.

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

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

Khái miệm

Cho  là một đồ thị liên thông

Trong đồ thị , một đường đi tư đỉnh  đến đỉnh , đi qua tất cả các cạnh của , mỗi cạnh đúng một lần, được gọi là đường đi Euler từ  đến .

Một chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, được gọi là chu trình Euler.

Chú ý: Khi  là đồ thị liên thông thì mọi đường đi Euler trên  (nếu có) đi qua mọi đỉnh của .

HĐKP2

a)

- Chu trình Euler: . Các đỉnh của đồ thị  đều là bậc chẵn.

b)

- Đồ thị  không thể chó chu trình Euler, do một chu trình đi qua cạnh  thì phải đi qua cạnh này ít nhất 2 lần.

- Đồ thị  không có chu trình Euler, vì mỗi một chu trình đi qua các cạnh của đồ thị thì phải đi qua đỉnh  ít nhất 2 lần.

- Ta có: Đồ thị  có  và  là đỉnh bậc lẻ. Đồ thị  có  và  là đỉnh bậc lẻ.

Định lí 1

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

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

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

HĐKP3

- Đường đi Euler của đồ thị :

- Đường đi Euler của đồ thị :

- Mỗi đồ thị có 2 đỉnh bậc lẻ (bậc 3).

Định lí 2

Đồ thị liên thông  có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu nó có đúng hai đỉnh bậc lẻ.

Khi đó, đường đi Euler đi từ đỉnh bậc lẻ này đến đỉnh bậc lẻ kia.

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

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

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

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

HĐTH1

- Đồ thị  có chu trình Euler vì tất cả các đỉnh đều có bậc chẵn (bằng 4)

Một chu trình Euler của đồ thị  là:

- Đồ thị  không có chu trình Euler, vì đỉnh  và đỉnh  có bậc lẻ (bằng 3).

HĐTH2

Đồ thị  có đường đi Euler, vì có đúng hai đỉnh bậc lẻ là  và . Chẳng hạn, có đường đi Euler: .

HĐVD1

Không có cách đi như vậy, vì đồ thị ở Hình 1 không có chu trình Euler do có đỉnh  và đỉnh  là bậc lẻ.