Với giải Bài 2.13 trang 45 Chuyên đề Toán 11 Kết nối tri thức chi tiết trong Bài 9: Đường đi Euler và đường đi Hamilton giúp học sinh dễ dàng xem và so sánh lời giải, từ đó biết cách làm bài tập Chuyên đề Toán 11. Mời các bạn đón xem:
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
Bài 2.13 trang 45 Chuyên đề Toán 11: 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?
Lời giải:
Đồ thị đầy đủ Kn có n ≥ 2, n ∈ ℕ.
Đồ thị đầy đủ Kn là đồ thị liên thông.
Mỗi đỉnh của Kn đều có bậc là n – 1.
+) Theo định lí Euler, Kn có chu trình Euler khi Kn liên thông (đã thỏa mãn) và mọi đỉnh của Kn đều có bậc chẵn, điều này có nghĩa để Kn có một chu trình Euler thì n – 1 phải là số chẵn hay n phải là số lẻ, tức là n = 2k + 1 (k ∈ ℕ*). Vậy với n = 2k + 1 (k ∈ ℕ*) thì đồ thị đầy đủ Kn có một chu trình Euler.
+) Đồ thị Kn có một đường đi Euler từ A đến B khi và chỉ khi Kn liên thông và mọi đỉnh của Kn đều có bậc chẵn, chỉ trừ A và B có bậc lẻ. Mà mọi đỉnh của Kn đều có bậc là n – 1, nghĩa là mọi đỉnh của Kn đều có bậc chẵn hoặc đều có bậc lẻ.
- Với n = 2, ta có K2 có 2 đỉnh đều có bậc là 1 (là bậc lẻ) nên ta có đường đi Euler từ đỉnh này qua đỉnh còn lại.
- Với n > 2, n ∈ ℕ* thì mọi đỉnh của Kn đều có bậc cùng chẵn hoặc cùng lẻ lớn hơn 2, do đó không thỏa mãn điều kiện để Kn có đường đi Euler.
Vậy đồ thị đầy đủ Kn có một đường đi Euler khi n = 2.
Xem thêm các bài giải Chuyên đề Toán 11 Kết nối tri thức hay, chi tiết khác:
HĐ1 trang 41 Chuyên đề Toán 11: Nhận biết đường đi Euler
HĐ2 trang 43 Chuyên đề Toán 11: Nhận biết đường đi Hamilton
Bài 2.10 trang 44 Chuyên đề Toán 11: Cho đồ thị G như Hình 27. Tìm một đường đi Hamilton từ S đến R.
CÔNG TY TNHH ĐẦU TƯ VÀ DỊCH VỤ GIÁO DỤC VIETJACK
- Người đại diện: Nguyễn Thanh Tuyền
- Số giấy chứng nhận đăng ký kinh doanh: 0108307822, ngày cấp: 04/06/2018, nơi cấp: Sở Kế hoạch và Đầu tư thành phố Hà Nội.
2021 © All Rights Reserved.
