Đường đi Euler và đường đi Hamilton

1

Câu hỏi khởi động trang 49

Thành phố Königsberg thuộc Phổ (nay là Kaliningrad thuộc Nga) Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài 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ây 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...

Xem chi tiết →

2

Câu hỏi mục 1 trang 50, 51, 52, 53, 54

Nếu coi mỗi vùng đất của thành phố Königsberg là một đỉnh, mỗi cây cầu là một cạnh nối hai đỉnh thì ta được một đồ thị G như Hình 1. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Khám phá 1 a) Nếu coi mỗi vùng đất của thành phố Königsberg là một đỉnh, mỗi cây cầu là một cạnh nối hai đỉnh thì ta được một đồ thị 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...

Xem chi tiết →

3

Câu hỏi mục 2 trang 54, 55, 56, 57, 58

Đồ 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. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh 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. Phương...

Xem chi tiết →

4

Bài 1 trang 58

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. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài 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. Phương pháp giải - Xem chi tiết Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình...

Xem chi tiết →

5

Bài 2 trang 58

Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Đồ thị ở Hình 24 có đường đi Euler không? Nếu có hãy chỉ ra một đường đi như vậy. Phương pháp giải - Xem chi tiết Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu...

Xem chi tiết →

6

Bài 3 trang 58

Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Chỉ ra một chu trình Hamilton của đồ thị ở Hình 25. Phương pháp giải - Xem chi tiết Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton. Lời giải chi tiết Một số chu trình...

Xem chi tiết →

7

Bài 4 trang 58

Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài  Chỉ ra một đường đi Hamilton của đồ thị ở Hình 26. Phương pháp giải - Xem chi tiết Trong đồ thị, một đường đi được gọi là đường đi Hamilton nếu đường đi đó đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng 1 lần. Nếu chu trình là đường đi Hamilton thì chu trình đó được gọi là chu trình Hamilton. Lời giải chi tiết Một số đường đi...

Xem chi tiết →

8

Bài 5 trang 59

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. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài 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. Phương pháp giải - Xem chi tiết Quan sát hình vẽ, dựa vào kiến thức: Trong đồ thị, một...

Xem chi tiết →

9

Bài 6 trang 59

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. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Chân trời sáng tạo Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài 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. Phương pháp...

Xem chi tiết →