Anonymous
0
0
Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó
- asked 4 months agoVotes
0Answers
0Views
Giải Chuyên đề Toán 11 Kết nối tri thức Bài 9: Đường đi Euler và đường đi Hamilton
Luyện tập 1 trang 41 Chuyên đề Toán 11: Đồ thị nào dưới đây có một đường đi Euler? Hãy chỉ ra một đường đi Euler của nó.
Lời giải:
- Đồ thị Hình 2.19a có đường đi Euler từ A đến B vì đồ thị này liên thông và các đỉnh A, B có bậc 3 (bậc lẻ), còn các đỉnh C, D, E đều có bậc 2 (bậc chẵn). Một đường đi Euler của đồ thị này là ACBDAEB.
- Đồ thị Hình 2.19b không có đường đi Euler vì đồ thị này có bốn đỉnh bậc lẻ (ở đây là bậc bằng 3).