Giải Thực hành 1 Bài 2. Đường đi Euler và đường đi Hamilton (trang 50, 51, 52, 53, 54) – Chuyên đề học tập Toán 11 Chân trời sáng tạo. Tham khảo: Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả.
Câu hỏi/Đề bài:
Mỗi đồ thị sau đây có chu trình Euler không? Nếu có, hãy chỉ ra một chu trình như vậy.
Hướng dẫn:
Trong đồ thị, một đường đi được gọi là đường đi Euler nếu đường đi đó đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng 1 lần. Nếu chu trình là đường đi Euler thì chu trình đo được gọi là chu trình Euler.
Lời giải:
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ẻ.