Giáo án điện tử chuyên đề Toán 11 chân trời Bài 2: Đường đi Euler và đường đi Hamilton

CHÀO MỪNG CÁC EM 
ĐẾN VỚI TIẾT HỌC!

KHỞI ĐỘNG

Thành phố Königsberg thuộc Phổ (nay là kaliningrad thuộc Nga) có bảy cây cầu nối bốn vùng đất được chia bởi các nhánh sông Pregel như ở hình dưới.

Vào mỗi sáng Chủ Nhật, người dân thành phố thường đi dạo qua các câu cầu. Họ tự hỏi không biết có thể bắt đầu từ một điểm nào đó trong thành phố, đi qua khắp các cây cầu, mỗi cầu chỉ đi qua một lần, rồi quay về điểm xuất phát.

Theo em, có hay không một cách đi như vậy?

CHUYÊN ĐỀ 2: 

LÍ THUYẾT ĐỒ THỊ

BÀI 2: ĐƯỜNG ĐI EULER VÀ ĐƯỜNG ĐI HAMILTON

NỘI DUNG BÀI HỌC 

...........................................

HĐKP2

                    a) Chỉ ra một chu trình Euler của đồ thị G ở Hình 5. Đồ thị này có đỉnh nào bậc lẻ không? 

b) Chỉ ra rằng các đồ thị S và T sau đây không có chu trình Euler. Các đồ thị này có đỉnh bậc lẻ không?

Giải:

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

b) 

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

- Đồ thị T 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 A ít nhất 2 lần.

- Ta có: Đồ thị S có C và D là đỉnh bậc lẻ. Đồ thị T có A và C là đỉnh bậc lẻ.

ĐỊNH LÍ 1

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

Ví dụ 3:Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.

Giải:

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

b) Ta thấy tất cả các đình của đồ thị H đều có bậc chẵn nên H có chu trình Euler, chẳng hạn, AEBCDFCABDA.

HĐKP3

Hãy chỉ ra một đường đi Euler trên mỗi đồ thị sau. Mỗi đồ thị có bao nhiêu đỉnh bậc lẻ?

Giải:

• Đường đi Euler của đồ thị G: ACBDab
• Đường đi Euler của đồ thị H: EABFEDCF
• Mỗi đồ thị có 2 đỉnh bậc lẻ (bậc 3).

Định lí 2

Đồ thị liên thông G 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:Mỗi đồ thị trong Hình 10 có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.

Giải:

a) Đồ thị G không có đường đi Euler, có đến 4 đỉnh bậc lẻ là A, B, C, D.

b) Đồ thị H có đúng hai đỉnh bậc lẻ là B và C nên nó có đường đi Euler. Chẳng hạn, đường đi BAEabEDCBFC là một đường đi Euler trên H.

Ví dụ 5:Có năm vùng đất A, B, C, D và E được nối với nhau bởi những cây cầu như Hình 11. Có hay không một cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ qua một lần và quay trở lại nơi xuất phát ban đầu? Nếu có, hãy chỉ ra một cách đi như vậy.

Giải:

Biểu thị mỗi vùng đất bằng một đỉnh, mỗi cây cầu bằng một cạnh nối hai đỉnh, ta được đồ thị như Hình 12. 

Ta thấy các đỉnh của đồ thị đều có bậc chẵn. 

Do đó, đồ thị có chu trình Euler. 

Nói cách khác, có cách đi qua tất cả các cây cầu, mỗi cây cầu chỉ đi qua một lần và quay trở lại nơi xuất phát ban đầu. 

Chẳng hạn, bắt đầu từ D, ta có thể đi theo chu trình Euler: DAabACBED.

THỰC HÀNH 1

Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.

Giải:

- Đồ thị G 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ị G là: ADBECABCDEA

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

THỰC HÀNH 2

Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.

Giải:

Đồ thị H có đường đi Euler, vì có đúng hai đỉnh bậc lẻ là E và F. 

Chẳng hạn, có đường đi Euler: EBabBCcdCFDAEF.

--------------- Còn tiếp ---------------