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

1

Câu hỏi mở đầu trang 41

Trong lí thuyết đồ thị, bài toán Bảy câu cầu ở Königsberg (nay là thành phố Kaliningrad, nước Nga) Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Trong lí thuyết đồ thị, bài toán Bảy câu cầu ở Königsberg (nay là thành phố Kaliningrad, nước Nga) được phát biểu như sau: Thành phố có 7 cây cầu bắc qua sông như Hình 2.15a dưới đây, có thể nào đi dạo qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần không? Nếu ta coi mỗi khu vực A, B,...

Xem chi tiết →

2

Câu hỏi mục 1 trang 41, 42

Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Hoạt động 1 Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.  Phương pháp giải:Quan sát hình 2.16 để làmLời giải chi tiết:Ta có thể vẽ mỗi hình trên Hình 2.16 bằng một nét liền. - Đối với Hình 2.16 a), ta có thể vẽ một nét liền theo thứ tự 123451. - Đối với Hình 2.16 b), ta có thể vẽ một nét liền theo thứ tự ABCDAEFB.   Luyện tập 1 Đồ...

Xem chi tiết →

3

Câu hỏi mục 2 trang 43, 44

Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20 Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Hoạt động 2 Có 5 thành phố du lịch A, B, C, D, E và các con đường nối các thành phố này như Hình 2.20. Hãy chỉ ra một cách để đi tham quan cả 5 thành phố đó, mà không cần đến địa điểm nào quá một lần. Phương pháp giải:Quan sát hình 2.20 để làm.Lời giải chi tiết:Một cách để đi tham quan cả 5 thành phố đó, mà...

Xem chi tiết →

4

Bài 2.7 trang 44

Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Mỗi đồ thị sau có một chu trình Euler hoặc một chu trình Hamilton hay không? Hãy vẽ một chu trình Euler hoặc một chu trình Hamilton khi có thể. 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...

Xem chi tiết →

5

Bài 2.8 trang 44

Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần? Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Có thể nào đi dạo chơi qua các cây cầu trong Hình 2.25, mỗi cây cầu vừa đúng một lần? Phương pháp giải - Xem chi tiết Quan sát hình 2.25 để làm Lời giải chi tiết Bằng cách loaị bỏ tất cả các chi tiết ngoại trừ các vùng đất và các cây cầu, sau đó thay thế mỗi vùng đất bằng một điểm và thay thế mỗi câu cầu...

Xem chi tiết →

6

Bài 2.9 trang 44

Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Cho đồ thị G như Hình 2.26. Tìm một chu trình Hamilton xuất phát từ đỉnh S của G. 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à...

Xem chi tiết →

7

Bài 2.10 trang 44

Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R. 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...

Xem chi tiết →

8

Bài 2.11 trang 45

Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn \(\frac{n}{2}\) Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Hãy chỉ ra một ví dụ chứng tỏ rằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn \(\frac{n}{2}\) trong Định lí Dirac, không thể thay bằng điều kiện “bậc của mỗi đỉnh không nhỏ hơn \(\frac{{n - 1}}{2}\)”. Phương pháp giải - Xem chi tiết Dựa vào kiến thức vừa học để làm Lời giải...

Xem chi tiết →

9

Bài 2.12 trang 45

a) Giả sử G là một đồ thị với n đỉnh và (frac{{left( {n - 1} right)left( {n - 2} right)}}{2} + 2) cạnh. Sử dụng Định lí Ore, hãy chứng minh G có một chu trình Hamilton. Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài a) Giả sử G là một đồ thị với n đỉnh và \(\frac{{\left( {n - 1} \right)\left( {n - 2} \right)}}{2} + 2\) cạnh. Sử dụng Định lí Ore, hãy chứng minh G có một chu trình Hamilton. b) Tìm một đồ thị với n đỉnh...

Xem chi tiết →

10

Bài 2.13 trang 45

Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler? Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Euler? Có một đường đi Euler? 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...

Xem chi tiết →

11

Bài 2.14 trang 45

Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi Hamilton? Tổng hợp đề thi học kì 1 lớp 11 tất cả các môn - Kết nối tri thức Toán - Văn - Anh - Lí - Hóa - Sinh Đề bài Với giá trị nào của n thì đồ thị đầy đủ Kn có một chu trình Hamilton? Có một đường đi Hamilton? 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ì...

Xem chi tiết →