Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
Thực hành 2 trang 54 Chuyên đề Toán 11: Đồ thị sau có đường đi Euler không? Nếu có, hãy chỉ ra một đường đi như vậy.
a) Đồ thị G:
Ta có d(A) = d(B) = d(C) = d(D) = d(E) = 4.
Vậy đồ thị G có chu trình Euler vì các đỉnh của đồ thị G đều có bậc chẵn.
Chẳng hạn, bắt đầu từ đỉnh A, ta có thể đi theo chu trình Euler: ABECAEDCBDA.
b) Đồ thị H:
Ta có d(A) = d(D) = 4; d(B) = d(C) = 3; d(E) = 2.
Vậy đồ thị H không có chu trình Euler vì hai đỉnh B, C có bậc lẻ.
Xem thêm các bài giải Chuyên đề Toán 11 Chân trời sáng tạo hay, chi tiết khác:
Bài 2: Đường đi Euler và đường đi Hamilton