Giải chi tiết chuyên đề Toán 11 kết nối mới bài 9 Đường đi Euler và đường đi Hamilton
Giải bài 9 Đường đi Euler và đường đi Hamilton sách chuyên đề Toán 11 kết nối. Phần đáp án chuẩn, hướng dẫn giải chi tiết cho từng bài tập có trong chương trình học của sách giáo khoa. Hi vọng, các em học sinh hiểu và nắm vững kiến thức bài học.
MỞ ĐẦU
Trong lí thuyết đồ thị, bài toán Bảy cây cầu ở Konigsberg (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 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, C, D của thành phố là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì bản đồ thành phố Konigsberg là một đa đồ thị như Hình 2.15b. Vấn đề đặt ra chính là: Có thể vẽ được Hình 2.15b bằng một nét liền hay không?
Hướng dẫn trả lời:
Không thể nào đi qua khắp các cây cầu nhưng mỗi cầu chỉ đi qua một lần và cũng không thể vẽ được bằng một nét liền ở Hình 2.15b.
1. ĐƯỜNG ĐI EULER
a) Khái niệm đường đi Euler
Hoạt động 1: Nhận biết đường đi Euler
Hãy thử vẽ mỗi hình trên Hình 2.16 bằng một nét liền.
Hướng dẫn trả lời:
a) Xuất phát từ điểm đỏ, đi theo mũi tên xanh và quay lại điểm đỏ.
b) Xuất phát từ A, đi theo mũi tên xanh và kết thúc tại B.
Luyện tập 1: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.
Hướng dẫn trả lời:
Đồ thị 2.19a liên thông, chỉ có hai đỉnh A và B có bậc lẻ (bậc bằng 3), các đỉnh còn lại đều bậc chẵn. Do đó đồ thị có đường đi Euler. Đường đi Euler trong đồ thị: ACBEADB.
Đồ thị 2.19b liên thông nhưng tất cả các đỉnh đều có bậc lẻ nên đồ thị không có đường đi Euler.
2. ĐƯỜNG ĐI HAMILTON
Hoạt động 2: Nhận biết đường đi Hamilton
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.
Hướng dẫn trả lời:
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: EABCD.
Luyện tập 2: Đồ thị nào trong Hình 2.23 có đường đi Hamilton? Hãy chỉ ra một đường đi Hamilton của nó.
Hướng dẫn trả lời:
Đồ thị 2.23a có 5 đỉnh. Đỉnh A và B có bậc 3 (lớn hơn $\frac{5-1}{2}$), đỉnh C, D, E có bậc 2 (bằng $\frac{5-1}{2}$). Do đó, theo định lí Dirac, đồ thị có đường đi Hamilton. Một đường đi Hamilton: DAEBC.
Đồ thị 2.23b có 4 đỉnh. Tất cả các đỉnh đều có bậc 3 (lớn hơn $\frac{4-1}{2}$). Do đó, theo định lí Dirac, đồ thị có đường đi Hamilton. Một đường đi Hamilton: DABC.
BÀI TẬP
2.7. 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ể.
Hướng dẫn trả lời:
Hình 2.24a không có chu trình Euler, cũng không có chu trình Hamilton.
Hình 2.24b có chu trình Euler và có chu trình Hamilton. Chu trình Euler: ABCDEADBECA; chu trình Hamilton: ABCDEA.
Hình 2.24c không có chu trình Euler nhưng có chu trình Hamilton: EFGHDCBAE.
Hình 2.24d không có chu trình Euler, cũng không có chu trình Hamilton.
2.8. 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?
Hướng dẫn trả lời:
Nếu ta coi mỗi khu vực A, B, C, D, E, F là một đỉnh, mỗi cầu qua lại hai khu vực như một cạnh nối hai đỉnh, thì đây là một đa đồ thị. Ta có hình vẽ:
2.9. 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.
Hướng dẫn trả lời:
Một chu trình Hamilton xuất phát từ đỉnh S là: SUKTRNHOMS.
2.10. Cho đồ thị G như Hình 2.27. Tìm một đường đi Hamilton từ S đến R.
Hướng dẫn trả lời:
Một đường đi Hamilton từ S đến R là: SABEFDCR.
2.11. 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}$".
Hướng dẫn trả lời:
Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$ thì đồ thị G có một chu trình Hamilton.
Điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị G có một đường đi Hamilton.
Nếu thay điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$ bằng điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$ thì đồ thị sẽ chỉ có đường đi Hamilton.
Tuy nhiên ta có ví dụ:
Ta thấy bậc của mỗi đỉnh thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n-1}{2}$
Nhưng đồ thị trên có một chu trình Hamilton, ví dụ ABCFDEA. Do đó, đồ thị thỏa mãn điều kiện bậc của mỗi đỉnh của đồ thị G không nhỏ hơn $\frac{n}{2}$
Vậy đ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}$".
2.12. a) Giả sử G là một đồ thị với n đỉnh và $\frac{(n-1)(n-2)}{2}+2$ cạnh. Sử dụng Định lí Ore, hãy chứng minh rằng G có một chu trình Hamilton.
b) Tìm một đồ thị với n đỉnh và $\frac{(n-1)(n-2)}{2}+1$ cạnh mà không có chu trình Hamilton.
Hướng dẫn trả lời:
a) Định lí Ore: Nếu G là đơn đồ thị có n đỉnh (n ≥ 3) và mỗi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn n thì G có một chu trình Hamilton.
Ta có lí thuyết: Giả sử G là đồ thị đơn gồm n đỉnh và m cạnh. Nếu m ≥ $\frac{n^{2}-3n+6}{2}$ thì G là đồ thị có chu trình Hamilton.
Áp dụng vào bài toán ta được điều phải chứng minh.
b) Ta có đồ thị sau có 5 đỉnh, 7 cạnh và đồ thị không có chu trình Hamilton.
2.13. Với giá trị nào của n thì đồ thị đầy đủ $K_{n}$ có một chu trình Euler? Có một đường đi Euler?
Hướng dẫn trả lời:
Ta có đồ thị đầy đủ $K_{n}$ có n đỉnh và bậc của mọi đỉnh là n - 1
- Theo Định lí 1, đồ thị G có chu trình Euler khi và chỉ khi đồ thị liên thông và mọi đỉnh của đồ thị đều có bậc chẵn.
Do đó để đồ thị đầy đủ $K_{n}$ có một chu trình Euler khi và chỉ khi n - 1 phải là số chẵn. Suy ra n là số lẻ.
- Theo Định lí 2, đồ thị G có đường đi Euler từ A đến B khi và chỉ khi G liên thông và mọi đỉnh của G đều có bậc chẵn, chỉ trừ A và B có bậc lẻ.
Tuy nhiên, với đồ thị đầy đủ $K_{n}$, bậc của mọi đỉnh đều là n - 1 nên nếu có hai đỉnh có bậc lẻ thì các đỉnh còn lại đều có bậc lẻ.
Do đó, đồ thị đầy đủ $K_{n}$ không có đường đi Euler với mọi n.
2.14. Với giá trị nào của n thì đồ thị đầy đủ $K_{n}$ có một chu trình Hamilton? Có một đường đi Hamilton?
Hướng dẫn trả lời:
Đồ thị đầy đủ luôn là đồ thị có chu trình Hamilton với mọi n. Đồ thị có chu trình Hamilton thì chắc chắn sẽ có đường đi Hamilton.