Giải chi tiết chuyên đề Toán 11 cánh diều mới chuyên đề 1 Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton
Giải bài 1 Một vài yếu tố của lí thuyết đồ thị. Đường đi Euler và đường đi Hamilton sách chuyên đề Toán 11 cánh diều. 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.
II. MỘT SỐ KHÁI NIỆM CƠ BẢN
1. Khái niệm đồ thị
Luyện tập, vận dụng 1: Có năm thành phố A, B, C, D, E sao cho hai thành phố bất kì trong chúng đều có đúng một đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Hướng dẫn trả lời:
Luyện tập, vận dụng 2: Cho hai ví dụ về đồ thị đơn.
Hướng dẫn trả lời:
2. Bậc của đỉnh
Luyện tập, vận dụng 3: Có bao nhiêu đỉnh bậc lẻ trong đồ thị ở Hình 5a?
Hướng dẫn trả lời:
Ta có: d(A) = 2; d(B) = 3; d(C) = 2; d(D) = 2; d(E) = 3
Do đó: Có hai đỉnh bậc lẻ trong Hình 5a là đỉnh B và E.
Luyện tập, vận dụng 4: Cho ví dụ về một đồ thị có số lẻ đỉnh bậc chẵn.
Hướng dẫn trả lời:
Đồ thị có 5 đỉnh A, B, C, D, E và d(A) = d(B) = d(C) = d(D) = d(E) = 2.
3. Đường đi trên đồ thị
Luyện tập, vận dụng 5: Trong đồ thị ở Hình 8, hãy tìm:
a) Một đường đi từ đỉnh A đến đỉnh F;
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối.
Hướng dẫn trả lời:
a) Một đường đi từ đỉnh A đến đỉnh F: ADF
b) Một chu trình có đỉnh E là đỉnh đầu và đỉnh cuối: ECDFE.
Luyện tập, vận dụng 6: Cho ví dụ về một đồ thị liên thông và một đồ thị không liên thông.
Hướng dẫn trả lời:
Đồ thị liên thông:
Đồ thị không liên thông:
III. ĐƯỜNG ĐI EULER. ĐƯỜNG ĐI HAMILTON TRÊN ĐỒ THỊ
1. Đường đi Euler trên đồ thị
Luyện tập, vận dụng 7: Hãy chỉ ra hai đường đi Euler trong đồ thị ở Hình 11a.
Hướng dẫn trả lời:
Hai dường đi Euler trong đồ thị Hình 11a là: BACDEBDA và BEDBADCA.
Luyện tập, vận dụng 8: Chứng minh rằng đồ thị ở Hình 11a không có chu trình Euler.
Hướng dẫn trả lời:
Đồ thị ở Hình 11a có đỉnh A là đỉnh bậc lẻ.
Theo định lí Euler: Đồ thị có chu trình Euler khi và chỉ khi đồ thị liên thông và không có đỉnh bậc lẻ.
Do đó: Đồ thị ở Hình 11a không có chu trình Euler.
2. Đường đi Hamilton trên đồ thị
Luyện tập, vận dụng 9: Tìm hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15.
Hướng dẫn trả lời:
Hai đường đi Hamilton bắt đầu từ đỉnh E của đồ thị trong Hình 15: EACDB và ECADB.
Luyện tập, vận dụng 10: Chứng minh rằng đồ thị G ở Hình 17 có ít nhất một chu trình Hamilton.
Hướng dẫn trả lời:
Đồ thị G gồm 5 đỉnh, mỗi đỉnh của đồ thị G có bậc lớn hơn $\frac{5}{2}$. Do đó, theo định lí Dirac, đồ thị có ít nhất một chu trình Hamilton.
Luyện tập, vận dụng 11: Chứng minh rằng đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
Hướng dẫn trả lời:
Đồ thị G gồm 6 đỉnh, trong đó: d(A) = 4, d(C) = 5
Mà d(A) + d(C) = 9 > 6
Do đó, theo định lí Ore, đồ thị G ở Hình 19 có ít nhất một chu trình Hamilton.
BÀI TẬP
Bài 1: Có sáu thành phố A, B, C, D, E, G sao cho hai thành phố bất kì trong chúng đều có đường nối với nhau. Sử dụng đồ thị để mô tả tình huống đó.
Hướng dẫn trả lời:
Bài 2: Hãy vẽ một đồ thị có bốn đỉnh sao cho chỉ có đúng:
a) Hai đỉnh cùng có bậc là 1;
b) Hai đỉnh cùng có bậc là 2.
Hướng dẫn trả lời:
a) Đồ thị có bốn đỉnh, chỉ có đúng hai đỉnh cùng có bậc 1:
b) Đồ thị có bốn đỉnh, chỉ có đúng hai đỉnh cùng có bậc 2:
Bài 3: Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Euler (nếu có) của đồ thị ở Hình 20.
Hướng dẫn trả lời:
Ta có: d(A) = 4; d(B) = 2; d(C) = 4; d(D) = 2; d(E) = 4; d(F) = 2.
Vì đồ thị không có đỉnh bậc lẻ nên có chu trình Euler.
Chu trình Euler: EDAECABCFE.
Bài 4: Tìm bậc của mỗi đỉnh và chỉ ra một chu trình Hamilton (nếu có) của đồ thị ở Hình 21.
Hướng dẫn trả lời:
Ta có: d(A) = 3; d(B) = 3; d(C) = 4; d(D) = 4; d(E) = 2.
Đồ thị có 5 đỉnh, trong đó: d(A) + d(C) = 7 > 5. Do đó, theo định lí Ore, đồ thị có chu trình Hamilton.
Chu trình Hamilton: ABCED.
Bài 5: Một cuộc họp có 6 người tham dự. Hai người bất kì trong họ hoặc quen nhau hoặc không quen nhau. Chứng minh rằng có 3 người trong 6 người đó đôi một quen nhau hoặc đôi một không quen nhau.
Hướng dẫn trả lời:
Gọi 6 người bất kì là A, B, C, D, E, G.
Trong 6 người đó ta chọn ra một người A.Trong 5 người còn lại ta chia thành 2 nhóm:
- Nhóm 1 gồm những người quen A
- Nhóm 2 gồm những người ko quen A
Có 5 người mà chỉ có 2 nhóm. Do đó, tồn tại ít nhất 3 người thuộc cùng một nhóm. Tức là tồn tại ít nhất 3 người quen A hoặc tồn tại ít nhất 3 người ko quen A.
- Nếu tồn tại ít nhất 3 người quen A. Gọi 3 người đó là B, C, D:
+ Nếu trong 3 người B, C, D có 2 người nào đó quen nhau. Giả sử 2 người đó là B và C thì ta có 3 người A, B, C là 3 người đôi một quen nhau.
+ Nếu trong 3 người B, C, D ko có 2 người nào đó quen nhau thì 3 người B, C, D là 3 người đôi một ko quen nhau.
- Nếu tồn tại 3 người ko quen A. Giả sử 3 người đó là D, E, G:
+ Trong 3 người D, E, G nếu có 2 người nào đó ko quen nhau. Giả sử 2 người đó là D và E thì 3 người A, D, E là 3 người đôi một ko quen nhau.
+ Nếu trong 3 người D, E, G ko có 2 người nào ko quen nhau thì 3 người D, E, G là 3 người đôi một quen nhau.
Vậy trong 6 người bất kì luôn tồn tại 3 người đôi một quen nhau hoặc 3 người đôi một ko quen nhau (đpcm).