Luyện tập 1 trang 41 Chuyên đề học tập Toán 11 Kết nối tri thức

1. Nội dung câu hỏ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ó.

2. Phương pháp giải 

3. Lời giải chi tiết

- Đồ 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).