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.
Bài Làm:
Đồ 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.
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 đó.
Luyện tập, vận dụng 2: Cho hai ví dụ về đồ thị đơn.
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?
Luyện tập, vận dụng 4: Cho ví dụ về một đồ thị có số lẻ đỉnh bậc chẵn.
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.
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.
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.
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.
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.
Bài tập 1 trang 43 chuyên đề Toán 11 Cánh diều: 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 đó.
Bài tập 2 trang 43 chuyên đề Toán 11 Cánh diều: 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.
Bài tập 3 trang 43 chuyên đề Toán 11 Cánh diều: 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.
Bài tập 4 trang 43 chuyên đề Toán 11 Cánh diều: 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.
Bài tập 5 trang 43 chuyên đề Toán 11 Cánh diều: 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.
Xem thêm các bài Giải chuyên đề toán 11 cánh diều được biên soạn cho Học kì 1 & Học kì 2 theo mẫu chuẩn của Bộ Giáo dục theo sát chương trình Lớp 11 giúp bạn học tốt hơn.
Giải bài tập SGK, SBT, VBT và Trắc nghiệm các môn học Lớp 11, dưới đây là mục lục các bài giải bài tập sách giáo khoa và Đề thi chi tiết với câu hỏi bài tập, đề kiểm tra 15 phút, 45 phút (1 tiết), đề thi học kì 1 và 2 (đề kiểm tra học kì 1 và 2) các môn trong chương trình Lớp 11 giúp bạn học tốt hơn.
