Giải Luyện tập 1 trang 42 Chuyên đề Toán 11
Đề bài
Đồ 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ình 2.19 gồm hai đồ thị:
a) Đồ thị có 5 đỉnh A, B ở hàng trên và C, D, E ở hàng dưới. Các cạnh: A–C, A–D, A–E, B–C, B–D (các cạnh nối chéo tạo hình zic-zắc giữa hai hàng đỉnh).
b) Đồ thị có 4 đỉnh: A ở trên, C và B ở dưới, D ở giữa trong tam giác. Các cạnh: A–C, A–B, C–B, A–D, C–D, D–B (tam giác ABC với D là điểm trong nối tới cả ba đỉnh A, C, B).
Lời giải
Nhắc lại kiến thức (SGK): Một đồ thị liên thông có *đường đi Euler* khi và chỉ khi nó có đúng hoặc đỉnh bậc lẻ.
- Nếu có đỉnh bậc lẻ thì tồn tại *chu trình Euler*.
- Nếu có đúng đỉnh bậc lẻ thì tồn tại *đường đi Euler*, và đường đi đó nhận hai đỉnh bậc lẻ làm điểm đầu và điểm cuối.
a) Xét đồ thị a) với các cạnh .
Tính bậc của mỗi đỉnh:
- (nối với )
- (nối với )
- (nối với )
- (nối với )
- (nối với )
Đồ thị liên thông và có đúng hai đỉnh bậc lẻ là (bậc ) và (bậc ). Do đó đồ thị a) có đường đi Euler, với điểm đầu và điểm cuối là hai đỉnh và .
Một đường đi Euler: xuất phát từ , đi lần lượt qua tất cả các cạnh một lần:
Kiểm tra: đường đi dùng các cạnh — đúng cạnh, mỗi cạnh đúng một lần. Vậy đây là một đường đi Euler (kết thúc tại ).
b) Xét đồ thị b) là tam giác với nằm trong nối tới cả ba đỉnh, gồm các cạnh . Đây chính là đồ thị đầy đủ .
Tính bậc của mỗi đỉnh:
- (nối với )
- (nối với )
- (nối với )
- (nối với )
Đồ thị có cả bốn đỉnh đều bậc lẻ, tức là có đỉnh bậc lẻ (nhiều hơn ). Theo điều kiện trên, đồ thị
b) không có đường đi Euler.
Kết luận: Chỉ có đồ thị a) có đường đi Euler, chẳng hạn .
Đáp số
Lời giải do Thư viện nhà trường biên soạn, giải và kiểm chéo độc lập theo SGK 2026-2027.