Giải bài tập 2 trang 58 chuyên đề Toán 11 Chân trời sáng tạo

1. ĐƯỜNG ĐI EULER

Hoạt động 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?

Xem lời giải

Hoạt động 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?

Xem lời giải

Hoạt động 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ẻ?

Xem lời giải

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.

Xem lời giải

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.

Xem lời giải

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

Xem lời giải

2. ĐƯỜNG ĐI HAMILTON

Hoạt động 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.

Xem lời giải

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

Xem lời giải

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?

Xem lời giải

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.

Xem lời giải

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

Xem lời giải

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

Xem lời giải

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.

Xem lời giải

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. 

Xem lời giải