Giải chi tiết chuyên đề Toán 11 chân trời mới bài 2 Đường đi Euler và đường đi Hamilton

1. ĐƯỜNG ĐI EULER

Khám phá 1: 

a) Nếu coi mỗi vùng đất của thành phố Konigberg là một đỉnh, mỗi cây cầu là một cạnh nối hai đỉnh thì ta được một đồ thi G như Hình 1.

Câu hỏi của người dân thành phố trở thành: có hay không cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát?

Hãy thử vẽ và đưa ra dự đoán của mình.

b) Nếu không có cây cầu nối giữa A và D nhưng có thêm một cây cầu nối B và C thì ta có đồ thị H như Hình 2. 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 không?

Hướng dẫn trả lời:

a) Không có cách vẽ bằng một nét bút liền (không nhấc bút) đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần, sao cho điểm kết thúc trùng với điểm xuất phát.

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

Khám phá 2: 

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?

Hướng dẫn trả lời:

a) Chu trình Euler: abBAEDCB. Đồ thị G không có đỉnh bậc lẻ.

b) Đồ thị S không liên thông vì đỉnh D không có đường đi đến đỉnh A và B nên không có chu trình Euler. Đồ thị S có đỉnh bậc lẻ.

Đồ thị T không liên thông vì đỉnh D không có đường đi đến đỉnh B nên không có chu trình Euler. Đồ thị T có đỉnh bậc lẻ.

Khám phá 3: 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ẻ?

Hướng dẫn trả lời:

a) Đường đi Euler: baACBD. Đồ thị G có 2 đỉnh bậc lẻ là đỉnh A và D.

b) Đường đi Euler: EFBADCF. Đồ thị H có 2 đỉnh bậc lẻ là đỉnh E và F.

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.

Hướng dẫn trả lời:

a) Đồ thị có chu trình Euler vì đồ thị liên thông và không có đỉnh bậc lẻ. Chu trình Euler: CADBECBAEDC

b) Đồ thị không có chu trình Euler vì có đỉnh bậc lẻ.

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.

Hướng dẫn trả lời:

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

Đường đi Euler là EFCDCBABEADF

Vận dụng 1: Hãy giải đáp câu hỏi của người dân Konigsberg ở Hoạt động khởi động (còn gọi là bài toán Bảy cây cầu).

Hướng dẫn trả lời:

Không có cách đi nào như vậy.

2. ĐƯỜNG ĐI HAMILTON

Khám phá 4: Đồ thị ở Hình 15b biểu diễn các điểm vui chơi trong một công viên với những con đường nối giữa chúng như Hình 15a. Có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần hay không? Nếu có, chỉ ra ít nhất một đường đi như vậy.

Hướng dẫn trả lời:

Có thể đi theo những con đường này để thăm tất cả các điểm vui chơi mỗi điểm đúng một lần.

Một đường đi theo cách trên là: ADPCBMN.

Thực hành 3: Hãy chỉ ra rằng mỗi đồ thị sau đây có chu trình Hamilton.

Hướng dẫn trả lời:

a) Chu trình Hamilton là DABCF

b) Chu trình Hamilton là ABFEDCIA

Vận dụng 2: Các đỉnh của đồ thị ở Hình 22 biểu thị các điểm du lịch trong một thành phố, các cạnh biểu thị đường đi giữa các điểm du lịch này. Có hay không một cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch?

Hướng dẫn trả lời:

Có cách đi tham quan tất cả các điểm du lịch của thành phố, mỗi điểm qua đúng một lần, xuất phát và kết thúc tại cùng một điểm du lịch.

Chẳng hạn chu trình ABCDFEIKA.

BÀI TẬP

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

Hướng dẫn trả lời:

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

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

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

Hướng dẫn trả lời:

Đồ thị H không liên thông vì đỉnh A không có đường đi đến đỉnh B và F, do đó đồ thị không có đường đi Euler.

3. Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25. 

Hướng dẫn trả lời:

Chu trình Hamilton ở đồ thị G là DCEBAD.

4. Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26.

Hướng dẫn trả lời:

Đường đi Hamilton ở đồ thị H là PAEDQCFBNM.

5. Có bốn khu phố A, B, C và D được nối với nhau bằng những cây cầu như Hình 27. Có hay không 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, rồi quay trở lại nơi xuất phát? Nếu có, hãy chỉ ra một cách đi như vậy.

Hướng dẫn trả lời:

Chẳng hạn xuất phát từ cây cầu có chấm xanh, ta được một chu trình như sau.

6. Có năm vùng đất A, B, C, D và E được nối với nhau bằng những cây cầu như Hình 28.

a) Có hay không 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, rồi quay trở lại nơi xuất phát?

b) Nếu không yêu cầu quay lại nơi bắt đầu thì có cách đi như vậy không? Nếu có, hãy chỉ ra một cách đi. 

Hướng dẫn trả lời:

a) Không có 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, rồi quay trở lại nơi xuất phát.

b) Giả sử điểm xuất phát từ cây cầu có chấm xanh lá và kết thúc tại cây cầu có chấm xanh dương, ta được chu trình như sau: